Skip to contents

Sample a uniform random spanning tree

sample_spanning_tree.Rd

Samples a spanning tree uniformly at random from the set of all spanning trees using Wilson's (1996) loop-erased random walk algorithm.

Usage

sample_spanning_tree(graph)

Arguments

graph

An adj object representing a connected undirected graph.

Value

An adj object representing a spanning tree of graph.

References

Wilson, D.B. (1996). Generating random spanning trees more quickly than the cover time. Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 296–303. doi:10.1145/237814.237880

See also

enumerate_spanning_trees(), minimum_spanning_tree()

Examples

set.seed(1)
g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L)))
sample_spanning_tree(g)
#> <adj[3]>
#> [1] {2}    {1, 3} {2}