Change Password

Please enter the password.
Please enter the password. Between 8-64 characters. Not identical to your email address. Contain at least 3 of: uppercase, lowercase, numbers, and special characters.
Please enter the password.
Submit

Change Nickname

Current Nickname:
Submit

Apply New License

License Detail

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

The MAC address of the server you want to deploy.

Please complete this required field.

Please complete this required field.

Cancel
Apply
ID
Product
Status
Cores
Applied Validity Period(days)
Effective Date
Excpired Date
Mac Address
Apply Comment
Review Comment
Close
Profile
  • Full Name:
  • Phone:
  • Company:
  • Company Email:
  • Country:
  • Language:
Change Password
Apply

You have no license application record.

Apply
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

Product Created On ID Amount (USD) Invoice
Product Created On ID Amount (USD) Invoice

No Invoice

v5.0
Search
    English
    v5.0

      Minimum Spanning Tree

      ✓ File Writeback ✕ Property Writeback ✓ Direct Return ✓ Stream Return ✕ Stats

      Overview

      The Minimum Spanning Tree (MST) algorithm computes the spanning tree with the minimum sum of edge weights for each connected component in a graph.

      The MST has various applications, such as network design, clustering, and optimization problems where minimizing the total cost or weight is important.

      Concepts

      Spanning Tree

      A spanning tree is a connected subgraph that all nodes of a connected graph G= = (V, E) (or a connected component) and forms a tree (i.e., no circles). There may exist multiple spanning trees for a graph, and each spanning tree must have (|V| - 1) edges.

      The 11 nodes in the graph below, along with the 10 edges highlighted in red, form a spanning tree of this graph:

      Minimum Spanning Tree (MST)

      The MST is the spanning tree that has the minimum sum of edge weights. The construction of the MST starts from a given start node. The choice of the start node does not impact the correctness of the MST algorithm, but it can affect the structure of the MST and the order in which edges are added. Different start nodes may result in different MSTs, but all of them will be valid MSTs for the given graph.

      After assigning edge weights to the above example, the three possible MSTs with different start nodes are highlighted in red below:

      Regarding the selection of start nodes:

      • Each connected component requires only one start node. If multiple start nodes are specified, the first one will be considered valid.
      • No MST will be computed for connected components that do not have a specified start node.
      • Isolated nodes are not considered valid start nodes for computing the MST.

      Considerations

      • The MST algorithm ignores the direction of edges but calculates them as undirected edges.

      Syntax

      • Command: algo(mst)
      • Parameters:
      Name
      Type
      Spec
      Default
      Optional
      Description
      ids / uuids []_id / []_uuid / / Yes ID/UUID of the start nodes; the system chooses the start node for each connected component if not set
      edge_schema_property []@<schema>?.<property> Numeric type, must LTE / No Edge properties to use as weights; for each edge, the specified property with the smallest value is considered as its weight; edges without any specified property will not be included in any MST
      limit int ≥-1 -1 Yes Number of results to return, -1 to return all results

      Examples

      The example graph is as below, node A is an electric center, node B~H are the surrounding villages. Each edge is labeled with its UUID and the distance between the connected locations, which represents the required cable length:

      File Writeback

      Spec
      Content
      Description
      filename _id--[_uuid]--_id One-step path in the MST:
      (start node)--(edge)--(end node)
      algo(mst).params({
        uuids: [1],
        edge_schema_property: 'distance'
      }).write({
        file:{
          filename: 'solution'
          }
      })
      

      Results: File solution

      A--[107]--H
      A--[108]--E
      E--[111]--G
      F--[113]--G
      A--[101]--B
      A--[104]--D
      C--[103]--D
      

      Direct Return

      Alias Ordinal
      Type
      Description
      0 []path One-step path in the MST:
      _uuid (start node) -- [_uuid] (edge) -- _uuid (end node)
      algo(mst).params({
        ids: 'A',
        edge_schema_property: '@connect.distance'
      }) as mst 
      return mst
      

      Results: mst

      1--[107]--8
      1--[108]--5
      5--[111]--7
      6--[113]--7
      1--[101]--2
      1--[104]--4
      3--[103]--4

      Stream Return

      Alias Ordinal
      Type
      Description
      0 []path One-step path in the MST:
      _uuid (start node) -- [_uuid] (edge) -- _uuid (end node)
      algo(mst).params({
        uuids: [1],
        edge_schema_property: 'distance'
      }).stream() as mst
      with pedges(mst) as mstUUID
      find().edges(mstUUID) as edges
      return sum(edges.distance)
      

      Results: 5.65

      Please complete the following information to download this book
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写