graph_tool.topology.random_spanning_tree(g, weights=None, root=None, tree_map=None)[source]#

Return a random spanning tree of a given graph, which can be directed or undirected.


Graph to be used.

weightsEdgePropertyMap (optional, default: None)

The edge weights. If provided, the probability of a particular spanning tree being selected is the product of its edge weights.

rootVertex (optional, default: None)

Root of the spanning tree. If not provided, it will be selected randomly.

tree_mapEdgePropertyMap (optional, default: None)

If provided, the edge tree map will be written in this property map.


Edge property map with mark the tree edges: 1 for tree edge, 0 otherwise.


The running time for this algorithm is \(O(\tau)\), with \(\tau\) being the mean hitting time of a random walk on the graph. In the worst case, we have \(\tau \sim O(V^3)\), with \(V\) being the number of vertices in the graph. However, in much more typical cases (e.g. sparse random graphs) the running time is simply \(O(V)\).



David Bruce Wilson, “Generating random spanning trees more quickly than the cover time”, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, Pages 296-303, ACM New York, 1996, DOI: 10.1145/237814.237880 [sci-hub, @tor]


>>> from numpy.random import random
>>> g, pos = gt.triangulation(random((400, 2)), type="delaunay")
>>> weight = g.new_edge_property("double")
>>> for e in g.edges():
...    weight[e] = linalg.norm(pos[e.target()].a - pos[e.source()].a)
>>> tree = gt.random_spanning_tree(g, weights=weight)
>>> tree2 = gt.random_spanning_tree(g, weights=weight)
>>> gt.graph_draw(g, pos=pos, output="rtriang_orig.pdf")
>>> u = gt.GraphView(g, efilt=tree)
>>> gt.graph_draw(u, pos=pos, output="triang_random_span_tree.pdf")
>>> u2 = gt.GraphView(g, efilt=tree2)
>>> gt.graph_draw(u2, pos=pos, output="triang_random_span_tree2.pdf")
../_images/rtriang_orig.png ../_images/triang_random_span_tree.png ../_images/triang_random_span_tree2.png

Left: Original graph, Middle: A random spanning tree, Right: Another random spanning tree