Minimum Spanning Tree

Algorithm introduction

Minimum spanning tree finds a tree that connects all nodes with the minimum total edge weight.

Compute a minimum spanning tree for the connected component that contains start_id in an undirected weighted graph whose node primary key is id and edge weight property is weight.

For more information, see Minimum Spanning Tree.

Data model

To implement the Minimum Spanning Tree algorithm in GQL, the following data model is used to create a graph type:

• Entities are represented by nodes of type Node, with properties id and rating.
• Relationships are represented by edges of type Link, with property weight.

For the complete definition of the graph type, see Prepare graph data.

Procedure implementation

To compute Minimum Spanning Tree results, a procedure is created.

For more information about the procedure, see Procedure implementation. The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

• start_id: INT64. ID of the starting node to grow the MST from.

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
frontier	Primitive value variable	Active set of nodes already in the growing MST.
has_next	Primitive value variable	Whether there are still crossing edges to add to the MST.
step_no	Primitive value variable	Current MST edge step counter.
total_weight	Primitive value variable	Accumulated total weight of selected MST edges.
pick_src	Primitive value variable	Source node of the selected minimum crossing edge.
pick_dst	Primitive value variable	Destination node of the selected minimum crossing edge.
pick_weight	Primitive value variable	Weight of the selected minimum crossing edge.
best_edge	Global SumAgg aggregator value variable	Global minimum-weight crossing edge in the current step.
in_tree	Node-attached SumAgg aggregator value variable	Per-node flag: node is already part of the MST.
cand	Node-attached SumAgg aggregator value variable	Per-node lightest crossing edge candidate reaching this node.
result_table	Table variable	Output table storing MST edges (step_no, src_id, dst_id, weight).

The following steps outline the logic of the procedure:

1. Start the MST with an arbitrary node; add it to the frontier (in-tree set).
2. Find the minimum-weight crossing edge from the frontier to a non-tree node using best_edge.
3. Add the selected edge and its target node to the MST; update total_weight and step_no.
4. Repeat until all nodes are in the tree or no crossing edges remain. Return the MST edge list.

Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow Prepare algorithm sample data to check where to run commands and how the directory is mounted.

1. Prepare graph data

1. Create a graph type that matches your data model.

   '''
   CREATE GRAPH TYPE IF NOT EXISTS minimum_spanning_tree_graph_type AS {
       NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
       EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
   }
   '''
   

2. Download these CSV files and save them with their original names in examples/algorithms/minimum_spanning_tree/ under your deployment directory:

   • minimum_spanning_tree_node.csv: Node data.
   • minimum_spanning_tree_edge.csv: Edge data.
   Preview the CSV files

   minimum_spanning_tree_node.csv

   id,rating
   1,0
   2,2
   3,1
   4,0
   5,0
   6,2
   7,1
   8,2
   9,0
   10,1
   11,0
   12,2
   13,1
   14,1
   15,0
   16,2
   17,0
   18,1
   19,2
   20,0
   21,2
   22,1
   23,0
   24,1
   

   minimum_spanning_tree_edge.csv

   src_id,dst_id,weight
   1,2,4
   1,3,2
   1,4,7
   1,5,9
   2,3,1
   2,4,6
   2,5,5
   2,6,2
   3,4,3
   3,5,4
   3,6,8
   4,6,2
   4,7,6
   4,8,5
   5,6,4
   5,8,7
   5,9,6
   6,8,1
   6,9,5
   6,10,6
   7,9,2
   7,10,9
   8,9,3
   8,11,6
   8,12,4
   9,10,4
   9,12,7
   9,13,2
   10,12,1
   10,13,8
   10,14,4
   11,12,2
   11,14,5
   11,15,7
   12,14,3
   12,15,6
   12,16,5
   13,15,2
   13,16,7
   14,15,4
   14,17,8
   14,18,2
   15,16,1
   15,18,5
   15,19,3
   16,18,3
   16,19,6
   17,18,2
   17,20,7
   17,21,5
   18,19,4
   18,21,9
   18,22,6
   19,21,1
   19,22,5
   20,21,3
   20,23,6
   20,24,8
   21,22,2
   21,23,4
   21,24,7
   22,24,4
   23,24,1
   

3. Create a temporary graph based on the graph type and load the data files into the temporary graph.

   CREATE TEMPORARY GRAPH IF NOT EXISTS #minimum_spanning_tree_graph TYPED minimum_spanning_tree_graph_type
   

   '''
   USE #minimum_spanning_tree_graph IMPORT INTO GRAPH {
         NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
             PATH: "file:///examples/algorithms/minimum_spanning_tree/minimum_spanning_tree_node.csv",
             FORMAT: "CSV",
             DELIMITER: ','
         },
         EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
             PATH: "file:///examples/algorithms/minimum_spanning_tree/minimum_spanning_tree_edge.csv",
             FORMAT: "CSV",
             DELIMITER: ','
         }
     }
   '''
   

   After the import succeeds, run this query in the console to check the node count:

   '''
   USE #minimum_spanning_tree_graph
   MATCH (n)
   RETURN count(n) AS node_count
   '''
   

   The expected node_count is 24. If it differs, check the files and import results before continuing.

2. Create a procedure

Create a procedure to implement the Minimum Spanning Tree algorithm. For more information about the procedure, see Procedure implementation.

'''
CREATE OR REPLACE PROCEDURE minimum_spanning_tree(start_id INT64)
RETURNS (step_no INT64, src_id INT64, dst_id INT64, weight DOUBLE, total_weight DOUBLE)
COMMENT "Compute a minimum spanning tree for the connected component that contains start_id in an undirected weighted graph whose vertex primary key is id and edge weight property is weight."
AS {
  VALUE frontier ACTIVE_SET

  VALUE has_next BOOLEAN = true
  VALUE step_no INT64 = 0
  VALUE total_weight DOUBLE = 0.0
  VALUE pick_src INT64 = 0
  VALUE pick_dst INT64 = 0
  VALUE pick_weight DOUBLE = 0.0

  VALUE best_edge TopKAgg<1, weight DOUBLE ASC, src_id INT64 ASC, dst_id INT64 ASC>

  NODE VALUE in_tree OrAgg = false
  NODE VALUE cand TopKAgg<1, weight DOUBLE ASC, src_id INT64 ASC, dst_id INT64 ASC>

  TABLE result_table TYPED TABLE {step_no INT64, src_id INT64, dst_id INT64, weight DOUBLE}

  MATCH (s)
  WHERE s.id = start_id
  PER NODE (s) {
    SET s.@in_tree = true
  }

  WHILE has_next = true THEN {
    MATCH (s)
    WHERE s.@in_tree = true
    PER NODE (s) {
      SET s.@in_tree = true
    }
    FINALLY {
      SET frontier = s
    }

    MATCH (t)
    WHERE t.@in_tree = false
    PER NODE (t) {
      SET t.@cand.clear()
    }

    SET @best_edge.clear()

    MATCH (s)-[e]-(t)
    WHERE s IN frontier AND t.@in_tree = false
    PER PATH {
      SET t.@cand += RECORD{weight: e.weight, src_id: s.id, dst_id: t.id}
    }

    MATCH (t)
    WHERE t.@in_tree = false AND t.@cand.size() > 0
    PER NODE (t) {
      SET @best_edge += t.@cand.min()
    }

    IF @best_edge.size() = 0 THEN {
      SET has_next = false
    }
    ELSE {
      SET pick_weight = @best_edge.min().weight
      SET pick_src = @best_edge.min().src_id
      SET pick_dst = @best_edge.min().dst_id
      SET step_no = step_no + 1
      SET total_weight = total_weight + pick_weight

      EXPORT step_no, pick_src, pick_dst, pick_weight INTO result_table

      MATCH (t)
      WHERE t.id = pick_dst
      PER NODE (t) {
        SET t.@in_tree = true
      }
    }
  }

  FOR r IN result_table
  RETURN
    r.step_no AS step_no,
    r.src_id AS src_id,
    r.dst_id AS dst_id,
    r.weight AS weight,
    total_weight AS total_weight
  ORDER BY step_no ASC
}
'''

3. Call your procedure

Build a minimum spanning tree starting at node 1, returning the selected edges and total weight.

USE #minimum_spanning_tree_graph CALL minimum_spanning_tree(1) RETURN step_no, src_id, dst_id, weight, total_weight

Returns:

Expand to view results

+---------+--------+--------+--------+--------------+
| step_no | src_id | dst_id | weight | total_weight |
+---------+--------+--------+--------+--------------+
| 12      | 19     | 21     | 1.0    | 49.0         |
| 23      | 23     | 24     | 1.0    | 49.0         |
| 22      | 21     | 23     | 4.0    | 49.0         |
| 21      | 3      | 5      | 4.0    | 49.0         |
| 20      | 21     | 20     | 3.0    | 49.0         |
| 19      | 12     | 11     | 2.0    | 49.0         |
| 18      | 12     | 10     | 1.0    | 49.0         |
| 17      | 14     | 12     | 3.0    | 49.0         |
| 16      | 18     | 17     | 2.0    | 49.0         |
| 15      | 18     | 14     | 2.0    | 49.0         |
| 14      | 16     | 18     | 3.0    | 49.0         |
| 13      | 21     | 22     | 2.0    | 49.0         |
| 1       | 1      | 3      | 2.0    | 49.0         |
| 11      | 15     | 19     | 3.0    | 49.0         |
| 10      | 15     | 16     | 1.0    | 49.0         |
| 9       | 13     | 15     | 2.0    | 49.0         |
| 8       | 9      | 13     | 2.0    | 49.0         |
| 7       | 9      | 7      | 2.0    | 49.0         |
| 6       | 8      | 9      | 3.0    | 49.0         |
| 5       | 6      | 4      | 2.0    | 49.0         |
| 4       | 6      | 8      | 1.0    | 49.0         |
| 3       | 2      | 6      | 2.0    | 49.0         |
| 2       | 3      | 2      | 1.0    | 49.0         |
+---------+--------+--------+--------+--------------+

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see EXPORT. Match the exported fields to the returned columns and target properties.