Yog.MST (YogEx v0.70.0)

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/2`	Sparse graphs, edge lists
Prim's	`prim/2`	Dense graphs, growing from a start node

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

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

Migration Note: This module was ported from Gleam to pure Elixir in v0.53.0. The API remains unchanged.

Summary

Types

edge()

Represents an edge in the minimum spanning tree.

Functions

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.

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.

Types

edge()

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

Represents an edge in the minimum spanning tree.

from: Source node ID
to: Destination node ID
weight: Edge weight

Functions

kruskal(opts)

@spec kruskal(keyword()) :: [edge()]

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

Returns a list of edges that form the MST. The total weight of these edges is minimized while ensuring all nodes are connected.

Time Complexity: O(E log E) where E is the number of edges

Options

:in - The graph to find the MST in
:compare - A comparison function that takes two weights and returns :lt, :eq, or :gt (like &Integer.compare/2 or a custom function)

Example

iex> graph =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge!(from: 1, to: 2, with: 1)
...>   |> Yog.add_edge!(from: 2, to: 3, with: 2)
...>   |> Yog.add_edge!(from: 1, to: 3, with: 3)
iex> mst_edges = Yog.MST.kruskal(in: graph, compare: fn a, b ->
...>   cond do
...>     a < b -> :lt
...>     a > b -> :gt
...>     true -> :eq
...>   end
...> end)
iex> length(mst_edges)
2
iex> Enum.reduce(mst_edges, 0, fn e, acc -> acc + e.weight end)
3

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

@spec kruskal(Yog.graph(), (term(), term() -> :lt | :eq | :gt)) :: [edge()]

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

Same as kruskal/1 but with explicit positional arguments for pipeline use.

Example

iex> graph =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge!(from: 1, to: 2, with: 1)
...>   |> Yog.add_edge!(from: 2, to: 3, with: 2)
...>   |> Yog.add_edge!(from: 1, to: 3, with: 3)
iex> mst_edges = graph |> Yog.MST.kruskal(fn a, b ->
...>   cond do
...>     a < b -> :lt
...>     a > b -> :gt
...>     true -> :eq
...>   end
...> end)
iex> length(mst_edges)
2

prim(opts)

@spec prim(keyword()) :: [edge()]

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

Returns a list of edges that form the MST. Unlike Kruskal's which processes all edges globally, Prim's grows the MST from a starting node by repeatedly adding the minimum-weight edge that connects a visited node to an unvisited node.

Time Complexity: O(E log V) where E is the number of edges and V is the number of vertices

Disconnected Graphs: For disconnected graphs, Prim's only returns edges for the connected component containing the starting node (the first node in the graph). Use Kruskal's if you need a minimum spanning forest that covers all components.

Options

:in - The graph to find the MST in
:compare - A comparison function that takes two weights and returns :lt, :eq, or :gt

Example

iex> graph =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge!(from: 1, to: 2, with: 1)
...>   |> Yog.add_edge!(from: 2, to: 3, with: 2)
...>   |> Yog.add_edge!(from: 1, to: 3, with: 3)
iex> mst_edges = Yog.MST.prim(in: graph, compare: fn a, b ->
...>   cond do
...>     a < b -> :lt
...>     a > b -> :gt
...>     true -> :eq
...>   end
...> end)
iex> length(mst_edges)
2
iex> Enum.reduce(mst_edges, 0, fn e, acc -> acc + e.weight end)
3

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

@spec prim(Yog.graph(), (term(), term() -> :lt | :eq | :gt)) :: [edge()]

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

Same as prim/1 but with explicit positional arguments for pipeline use.

Example

iex> graph =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge!(from: 1, to: 2, with: 1)
...>   |> Yog.add_edge!(from: 2, to: 3, with: 2)
...>   |> Yog.add_edge!(from: 1, to: 3, with: 3)
iex> mst_edges = graph |> Yog.MST.prim(fn a, b ->
...>   cond do
...>     a < b -> :lt
...>     a > b -> :gt
...>     true -> :eq
...>   end
...> end)
iex> length(mst_edges)
2