random_spanning_tree

random_spanning_tree(G, weight=None, *, multiplicative=True, seed=None)

Sample a random spanning tree using the edges weights of G.

This function supports two different methods for determining the probability of the graph. If multiplicative=True, the probability is based on the product of edge weights, and if multiplicative=False it is based on the sum of the edge weight. However, since it is easier to determine the total weight of all spanning trees for the multiplicative verison, that is significantly faster and should be used if possible. Additionally, setting weight to None will cause a spanning tree to be selected with uniform probability.

The function uses algorithm A8 in [1] .

Parameters:

Gnx.Graph

An undirected version of the original graph.

weightstring

The edge key for the edge attribute holding edge weight.

multiplicativebool, default=True

If True, the probability of each tree is the product of its edge weight over the sum of the product of all the spanning trees in the graph. If False, the probability is the sum of its edge weight over the sum of the sum of weights for all spanning trees in the graph.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Returns:

nx.Graph

A spanning tree using the distribution defined by the weight of the tree.

References

[1]

V. Kulkarni, Generating random combinatorial objects, Journal of Algorithms, 11 (1990), pp. 185–207