Chu-Liu/Edmonds' algorithm for finding the Minimum Spanning Arborescence (MSA).
An arborescence (also known as a directed spanning tree) is a directed counterpart to a Minimum Spanning Tree. For a given root node, it finds a set of edges that allows all other nodes to be reached from the root with minimum total weight.
The algorithm works by:
- Picking the cheapest incoming edge for every node except the root.
- If the resulting graph is acyclic, it is the MSA.
- If cycles exist, it contracts each cycle into a "super-node", adjusts the weights of remaining incoming edges, and recurses.
- Finally, it expands the contracted cycles to restore the original graph structure.
Performance
- Time Complexity: O(VE) for simple implementations like this one.
- Space Complexity: O(V + E) to store the graph and recursion metadata.
Summary
Functions
Computes the Minimum Spanning Arborescence (MSA) of a directed graph.
Functions
@spec compute(Yog.graph(), term()) :: {:ok, Yog.MST.Result.t()} | {:error, term()}
Computes the Minimum Spanning Arborescence (MSA) of a directed graph.
Returns {:ok, %Yog.MST.Result{}} containing the edges of the MSA.
Parameters
graph: The directed graph to process.root: The node ID to use as the root of the arborescence.
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.Edmonds.compute(graph, 1)
iex> result.total_weight
15
iex> result.root
1