# `Yog.MST`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/mst.ex#L1)

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

A [Minimum Spanning Tree](https://en.wikipedia.org/wiki/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`, `kruskal_max/2` | Sparse graphs, edge lists |
| Prim's | `prim/2`, `prim_max/2` | Dense graphs, growing from a start node |
| Borůvka's | `boruvka/1` | Parallelized MST for large graphs |
| Edmonds' | `minimum_arborescence/2` | Directed 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

- [Wikipedia: Minimum Spanning Tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree)
- [CP-Algorithms: MST](https://cp-algorithms.com/graph/mst_kruskal.html)

## Example: Visualizing an MST

<div class="graphviz">
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"];
}
</div>

    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

# `edge`

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

Represents an edge in a spanning tree or arborescence.

# `boruvka`

```elixir
@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`

```elixir
@spec boruvka(Yog.graph(), (term(), term() -&gt; :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`

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

Alias for `minimum_arborescence/2`.

# `kruskal`

```elixir
@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`

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

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

# `kruskal_max`

```elixir
@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`

```elixir
@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`

```elixir
@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`

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

# `prim`

```elixir
@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`

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

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

# `prim`

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

# `prim_max`

```elixir
@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`

```elixir
@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`

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

---

*Consult [api-reference.md](api-reference.md) for complete listing*