Yog.MST (YogEx v0.97.0)

Copy Markdown View Source

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

AlgorithmFunctionBest For
Kruskal'skruskal/2, kruskal_max/2Sparse graphs, edge lists
Prim'sprim/2, prim_max/2Dense graphs, growing from a start node
Borůvka'sboruvka/1Parallelized MST for large graphs
Edmonds'minimum_arborescence/2Directed MST (Minimum Spanning Arborescence)

Important: Undirected Graphs Only

MST algorithms (Kruskal, Prim, Borůvka) are only defined for undirected graphs. Passing a directed graph to these will return {:error, :undirected_only}. Use minimum_arborescence/2 for directed graphs.

Properties of MSTs

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

References

Example: Visualizing an MST

graph G { rankdir=LR; bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; A [label="A"]; B [label="B"]; C [label="C"]; D [label="D"]; E [label="E"]; // MST edges (solid, colored) A -- B [label="2", color="#6366f1", penwidth=2.5]; B -- D [label="2", color="#6366f1", penwidth=2.5]; D -- C [label="1", color="#6366f1", penwidth=2.5]; E -- A [label="4", color="#6366f1", penwidth=2.5]; // Non-MST edges (dashed, muted) B -- C [label="3", style=dashed, color="#94a3b8"]; A -- C [label="6", style=dashed, color="#94a3b8"]; D -- E [label="5", style=dashed, color="#94a3b8"]; }
iex> alias Yog.MST
iex> graph = Yog.from_edges(:undirected, [
...>   {"A", "B", 2}, {"B", "D", 2}, {"D", "C", 1}, {"E", "A", 4},
...>   {"B", "C", 3}, {"A", "C", 6}, {"D", "E", 5}
...> ])
iex> {:ok, result} = MST.kruskal(in: graph)
iex> result.total_weight
9
iex> result.edge_count
4

Summary

Types

edge()

Represents an edge in a spanning tree or arborescence.

Functions

boruvka(opts)

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

boruvka(graph, compare \\ &Yog.Utils.compare/2)

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

chu_liu_edmonds(opts_or_graph, root \\ nil)

Alias for minimum_arborescence/2.

kruskal(opts)

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

kruskal(graph, compare \\ &Yog.Utils.compare/2)

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

kruskal_max(opts)

Finds the Maximum Spanning Tree (MaxST) using Kruskal's algorithm.

maximum_spanning_tree(opts)

Facade for Maximum Spanning Tree (MaxST). Defaults to Kruskal's algorithm.

minimum_arborescence(opts)

Finds the Minimum Spanning Arborescence (MSA) using the Chu-Liu/Edmonds algorithm.

minimum_arborescence(graph, root)
prim(opts)

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

prim(graph, compare \\ &Yog.Utils.compare/2)

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

prim(graph, compare, start_node)
prim_max(opts)

Finds the Maximum Spanning Tree (MaxST) using Prim's algorithm.

uniform_spanning_tree(opts)

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

uniform_spanning_tree(graph, opts \\ [])

Types

edge()

@type edge() :: %{from: Yog.node_id(), to: Yog.node_id(), weight: term()}

Represents an edge in a spanning tree or arborescence.

Functions

boruvka(opts)

@spec boruvka(keyword()) :: {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

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

Time Complexity: O(E log V)

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edges!([{1, 2, 10}, {2, 3, 5}, {1, 3, 20}])
iex> {:ok, result} = Yog.MST.boruvka(in: graph)
iex> result.total_weight
15

boruvka(graph, compare \\ &Yog.Utils.compare/2)

@spec boruvka(Yog.graph(), (term(), term() -> :lt | :eq | :gt)) ::
  {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

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

chu_liu_edmonds(opts_or_graph, root \\ nil)

@spec chu_liu_edmonds(keyword() | Yog.graph(), term()) ::
  {:ok, Yog.MST.Result.t()} | {:error, term()}

Alias for minimum_arborescence/2.

kruskal(opts)

@spec kruskal(keyword()) :: {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

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

Time Complexity: O(E log E)

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 2}, {1, 3, 3}])
iex> {:ok, result} = Yog.MST.kruskal(in: graph)
iex> result.total_weight
3

kruskal(graph, compare \\ &Yog.Utils.compare/2)

@spec kruskal(Yog.graph(), (term(), term() -> :lt | :eq | :gt)) ::
  {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

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

kruskal_max(opts)

@spec kruskal_max(keyword()) :: {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}
@spec kruskal_max(Yog.graph()) ::
  {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

Finds the Maximum Spanning Tree (MaxST) using Kruskal's algorithm.

Time Complexity: O(E log E)

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 20}, {1, 3, 3}])
iex> {:ok, result} = Yog.MST.kruskal_max(in: graph)
iex> result.total_weight
23

maximum_spanning_tree(opts)

@spec maximum_spanning_tree(keyword() | Yog.graph()) ::
  {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

Facade for Maximum Spanning Tree (MaxST). Defaults to Kruskal's algorithm.

minimum_arborescence(opts)

@spec minimum_arborescence(keyword()) :: {:ok, Yog.MST.Result.t()} | {:error, term()}

Finds the Minimum Spanning Arborescence (MSA) using the Chu-Liu/Edmonds algorithm.

Time Complexity: O(VE)

Examples

iex> graph = Yog.directed()
...> |> Yog.add_node(1, "Root") |> Yog.add_node(2, "A") |> Yog.add_node(3, "B")
...> |> Yog.add_edges!([{1, 2, 10}, {1, 3, 20}, {2, 3, 5}])
iex> {:ok, result} = Yog.MST.minimum_arborescence(in: graph, root: 1)
iex> result.total_weight
15

minimum_arborescence(graph, root)

@spec minimum_arborescence(Yog.graph(), term()) ::
  {:ok, Yog.MST.Result.t()} | {:error, term()}

prim(opts)

@spec prim(keyword()) :: {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

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

Time Complexity: O(E log V)

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 2}, {1, 3, 3}])
iex> {:ok, result} = Yog.MST.prim(in: graph, from: 1)
iex> result.total_weight
3

prim(graph, compare \\ &Yog.Utils.compare/2)

@spec prim(Yog.graph(), (term(), term() -> :lt | :eq | :gt)) ::
  {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

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

prim(graph, compare, start_node)

@spec prim(Yog.graph(), (term(), term() -> :lt | :eq | :gt), term() | nil) ::
  {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

prim_max(opts)

@spec prim_max(keyword()) :: {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}
@spec prim_max(Yog.graph()) :: {:ok, Yog.MST.Result.t()} | {:error, :undirected_only}

Finds the Maximum Spanning Tree (MaxST) using Prim's algorithm.

Time Complexity: O(E log V)

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 20}, {1, 3, 3}])
iex> {:ok, result} = Yog.MST.prim_max(in: graph, from: 1)
iex> result.total_weight
23

uniform_spanning_tree(opts)

@spec uniform_spanning_tree(keyword()) :: {:ok, Yog.MST.Result.t()}

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

Returns {:ok, %Yog.MST.Result{}} containing the edges of the spanning tree.

Parameters

  • opts: Options including:
    • :in - The graph to sample from.
    • :root - (Optional) The node to start the tree with.

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {1, 3, 1}])
iex> {:ok, result} = Yog.MST.uniform_spanning_tree(in: graph)
iex> result.edge_count
2

uniform_spanning_tree(graph, opts \\ [])

@spec uniform_spanning_tree(
  Yog.graph(),
  keyword()
) :: {:ok, Yog.MST.Result.t()}