yog/mst

Minimum Spanning Tree (MST) algorithms for finding optimal network connections.

A Minimum Spanning Tree connects all nodes in a weighted undirected graph with the minimum possible total edge weight. MSTs have applications in network design, clustering, and optimization problems.

Available Algorithms

Algorithm	Function	Best For
Kruskal’s	`kruskal/4`	Sparse graphs, edge lists
Prim’s	`prim/4`	Dense graphs, adjacency-based
Borůvka’s	`boruvka/4`	Parallel/distributed MST
Chu-Liu/Edmonds	`edmonds/6`	Directed MSA (arborescence)
Wilson’s	`wilson/2`	Uniform random spanning tree

Properties of MSTs

Connects all nodes with exactly V - 1 edges (for a graph with V nodes)
Contains no cycles
Minimizes the sum of edge weights
May not be unique if multiple edges have the same weight

Maximum Spanning Trees

While these functions are named for Minimum Spanning Trees, they are fully generic. To find a Maximum Spanning Tree, simply provide a comparator that reverses the natural order of your weights (e.g., using order.reverse(int.compare)). This will cause the algorithms to prioritize the largest weights first, yielding the maximum possible total weight.

Widest Path Problem: In an undirected graph, the unique path between two nodes in a Maximum Spanning Tree is also a widest path (or maximum capacity path). If you need to find a path that maximizes the bottleneck capacity between two nodes, you can calculate the MaxST and then find the path in that tree.

Example Use Cases

Network Design: Minimizing cable length to connect buildings
Cluster Analysis: Hierarchical clustering via MST
Approximation: Traveling Salesman Problem approximations
Image Segmentation: Computer vision applications

References

Types

Algorithm

</>

Algorithm used to compute the spanning tree result.

pub type Algorithm {
  Kruskal
  Prim
  Boruvka
  ChuLiuEdmonds
  Wilson
}

Constructors

```
Kruskal
```
```
Prim
```
```
Boruvka
```
```
ChuLiuEdmonds
```
```
Wilson
```

Edge

</>

Represents an edge in the minimum spanning tree.

pub type Edge(e) {
  Edge(from: Int, to: Int, weight: e)
}

Constructors

```
Edge(from: Int, to: Int, weight: e)
```

MstResult

</>

Result of a Minimum Spanning Tree computation.

pub type MstResult(e) {
  MstResult(
    edges: List(Edge(e)),
    total_weight: e,
    node_count: Int,
    edge_count: Int,
    algorithm: Algorithm,
    root: option.Option(Int),
  )
}

Constructors

MstResult(
  edges: List(Edge(e)),
  total_weight: e,
  node_count: Int,
  edge_count: Int,
  algorithm: Algorithm,
  root: option.Option(Int),
)

Values

boruvka

</>

pub fn boruvka(
  in graph: model.Graph(n, e),
  with_compare compare: fn(e, e) -> order.Order,
  with_add add: fn(e, e) -> e,
  with_zero zero: e,
) -> MstResult(e)

Finds the Minimum Spanning Tree (MST) using Borůvka’s algorithm.

Time Complexity: O(E log V)

boruvka_float

</>

pub fn boruvka_float(
  in graph: model.Graph(n, Float),
) -> MstResult(Float)

Borůvka for Float weights.

boruvka_int

</>

pub fn boruvka_int(
  in graph: model.Graph(n, Int),
) -> MstResult(Int)

Borůvka for Int weights.

edmonds

</>

pub fn edmonds(
  in graph: model.Graph(n, e),
  root root: Int,
  with_compare compare: fn(e, e) -> order.Order,
  with_add add: fn(e, e) -> e,
  with_subtract subtract: fn(e, e) -> e,
  with_zero zero: e,
) -> Result(MstResult(e), String)

Finds the Minimum Spanning Arborescence (MSA) of a directed graph.

An arborescence is a directed spanning tree rooted at root. This algorithm finds the minimum-weight set of edges that connects all reachable nodes to the root.

Time Complexity: O(VE)

edmonds_float

</>

pub fn edmonds_float(
  in graph: model.Graph(n, Float),
  root root: Int,
) -> Result(MstResult(Float), String)

Edmonds for Float weights.

edmonds_int

</>

pub fn edmonds_int(
  in graph: model.Graph(n, Int),
  root root: Int,
) -> Result(MstResult(Int), String)

Edmonds for Int weights.

kruskal

</>

pub fn kruskal(
  in graph: model.Graph(n, e),
  with_compare compare: fn(e, e) -> order.Order,
  with_add add: fn(e, e) -> e,
  with_zero zero: e,
) -> MstResult(e)

Finds the Minimum Spanning Tree (MST) using Kruskal’s algorithm.

Time Complexity: O(E log E)

kruskal_float

</>

pub fn kruskal_float(
  in graph: model.Graph(n, Float),
) -> MstResult(Float)

Kruskal for Float weights.

kruskal_int

</>

pub fn kruskal_int(
  in graph: model.Graph(n, Int),
) -> MstResult(Int)

Kruskal for Int weights.

prim

</>

pub fn prim(
  in graph: model.Graph(n, e),
  with_compare compare: fn(e, e) -> order.Order,
  with_add add: fn(e, e) -> e,
  with_zero zero: e,
) -> MstResult(e)

Finds the Minimum Spanning Tree (MST) using Prim’s algorithm.

Time Complexity: O(E log V)

Disconnected Graphs: For disconnected graphs, Prim’s only returns edges for the connected component containing the starting node.

prim_float

</>

pub fn prim_float(
  in graph: model.Graph(n, Float),
) -> MstResult(Float)

Prim for Float weights.

prim_int

</>

pub fn prim_int(in graph: model.Graph(n, Int)) -> MstResult(Int)

Prim for Int weights.

wilson

</>

pub fn wilson(
  in graph: model.Graph(n, e),
  with_add add: fn(e, e) -> e,
  with_zero zero: e,
) -> MstResult(e)

Generates a Uniform Spanning Tree (UST) using Wilson’s algorithm.

Uses a random seed for non-deterministic sampling.

wilson_float

</>

pub fn wilson_float(
  in graph: model.Graph(n, Float),
) -> MstResult(Float)

Wilson for Float weights.

wilson_float_with_seed

</>

pub fn wilson_float_with_seed(
  in graph: model.Graph(n, Float),
  seed seed: Int,
) -> MstResult(Float)

Wilson with fixed seed for Float weights.

wilson_int

</>

pub fn wilson_int(
  in graph: model.Graph(n, Int),
) -> MstResult(Int)

Wilson for Int weights.

wilson_int_with_seed

</>

pub fn wilson_int_with_seed(
  in graph: model.Graph(n, Int),
  seed seed: Int,
) -> MstResult(Int)

Wilson with fixed seed for Int weights.

wilson_with_seed

</>

pub fn wilson_with_seed(
  in graph: model.Graph(n, e),
  seed seed: Int,
  with_add add: fn(e, e) -> e,
  with_zero zero: e,
) -> MstResult(e)

Generates a Uniform Spanning Tree with a fixed seed for reproducibility.