random_labeled_rooted_forest#

random_labeled_rooted_forest(n, *, seed=None)[source]#

Returns a labeled rooted forest with n nodes.

The returned forest is chosen uniformly at random using a generalization of Prüfer sequences [1] in the form described in [2].

Parameters:

nint: The number of nodes.
seedrandom_state: See Randomness.

Returns:

networkx.Graph: A networkx.Graph with integer nodes 0 <= node <= n - 1. The “roots” graph attribute is a set of integers containing the roots.

References

[1]

Knuth, Donald E. “Another Enumeration of Trees.” Canadian Journal of Mathematics, 20 (1968): 1077-1086. https://doi.org/10.4153/CJM-1968-104-8

[2]

Rubey, Martin. “Counting Spanning Trees”. Diplomarbeit zur Erlangung des akademischen Grades Magister der Naturwissenschaften an der Formal- und Naturwissenschaftlichen Fakultät der Universität Wien. Wien, May 2000.