Minimum Spanning Tree

Overview

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

The MST has a wide range of applications, including network design, clustering, and other optimization problems where minimizing overall cost or weight is essential.

Concepts

Spanning Tree

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

In the example below, the 11 nodes of the graph and the 10 edges highlighted in red form a spanning tree:

Minimum Spanning Tree (MST)

An MST is a spanning tree with the minimum total sum of edge weights. The construction of an MST begins from a given start node. While the choice of the start node does not affect the correctness of the algorithm, it can influence 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.

In the example below, after assigning weights to the edges, three valid MSTs—each starting from a different node—are highlighted in red:

Start Node Selection for MST Computation:

• Each connected component requires only one start node. If multiple start nodes are specified within the same component, only the first one will be used.
• No MST will be computed for any connected component that lacks a specified start node.
• Isolated nodes are not valid as start nodes for MST computation.

Considerations

• The MST algorithm treats all edges as undirected, ignoring their original direction.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER GRAPH CURRENT_GRAPH ADD NODE {
  electricCenter (),
  village ()
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
  connects ()-[{distance float}]->()
};
INSERT (A:electricCenter {_id: "A"}),
       (B:village {_id: "B"}),
       (C:village {_id: "C"}),
       (D:village {_id: "D"}),
       (E:village {_id: "E"}),
       (F:village {_id: "F"}),
       (G:village {_id: "G"}),
       (H:village {_id: "H"}),
       (A)-[:connects {distance: 1}]->(B),
       (A)-[:connects {distance: 2.4}]->(C),
       (A)-[:connects {distance: 1.2}]->(D),
       (A)-[:connects {distance: 0.7}]->(E),
       (A)-[:connects {distance: 2.2}]->(F),
       (A)-[:connects {distance: 1.6}]->(G),
       (A)-[:connects {distance: 0.4}]->(H),
       (B)-[:connects {distance: 1.3}]->(C),
       (C)-[:connects {distance: 1}]->(D),
       (D)-[:connects {distance: 1.65}]->(H),
       (E)-[:connects {distance: 1.27}]->(F),
       (E)-[:connects {distance: 0.9}]->(G),
       (F)-[:connects {distance: 0.45}]->(G);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: algo(mst)

File Writeback

GQLUQL
CALL algo.mst.write("my_hdc_graph", {
  return_id_uuid: "id",
  ids: ["A"],
  edge_schema_property: "distance"
}, {
  file: {
    filename: "paths"
  }
})

Result:

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

Full Return

GQLUQL
CALL algo.mst.run("my_hdc_graph", {
  ids: ["A"],
  edge_schema_property: "@connects.distance"
}) YIELD mst
RETURN mst

Result:

Stream Return

GQLUQL
CALL algo.mst.stream("my_hdc_graph", {
  ids: ["A"],
  edge_schema_property: "distance"
}) YIELD mst
FOR e1 IN pedges(mst)
MATCH ()-[e2 WHERE e2._uuid = e1._uuid]->()
RETURN sum(e2.distance)

Result: 5.65