Wilson's algorithm for generating a Uniform Spanning Tree (UST).
Wilson's algorithm uses loop-erased random walks to sample a spanning tree uniformly at random from the set of all possible spanning trees of a graph. Unlike Kruskal's or Prim's, it is not a "minimum" spanning tree algorithm, but a probabilistic one.
Performance
- Time Complexity: The expected time is the mean hitting time of the graph, which varies but is generally efficient for most graphs.
- Space Complexity: O(V) to store the tree and the current walk.
Summary
Functions
Generates a Uniform Spanning Tree (UST) using Wilson's algorithm.
Functions
@spec compute( Yog.graph(), 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
graph: The graph (usually undirected) to sample from.opts: Options including::root- The node to start the tree from (initially in the tree).:seed- (Optional) seed for the random number generator.
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.Wilson.compute(graph)
iex> result.edge_count
2