random_unlabeled_rooted_forest(n, *, q=None, number_of_forests=None, seed=None)[source]#

Returns a forest or list of forests selected at random.

Returns one or more (depending on number_of_forests) unlabeled rooted forests with n nodes, and with no more than q nodes per tree, drawn uniformly at random. The “roots” graph attribute identifies the roots of the forest.


The number of nodes

qint or None (default)

The maximum number of nodes per tree.

number_of_forestsint or None (default)

If not None, this number of forests is generated and returned.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

networkx.Graph or list of networkx.Graph

A single networkx.Graph (or a list thereof, if number_of_forests is specified) with nodes in the set {0, …, n - 1}. The “roots” graph attribute is a set containing the roots of the trees in the forest.


If n is non-zero but q is zero.


This function implements the algorithm “Forest” of [1]. The algorithm needs to compute some counting functions that are relatively expensive: in case several trees are needed, it is advisable to use the number_of_forests optional argument to reuse the counting functions.



Wilf, Herbert S. “The uniform selection of free trees.” Journal of Algorithms 2.2 (1981): 204-207. https://doi.org/10.1016/0196-6774(81)90021-3