random_unlabeled_rooted_forest

random_unlabeled_rooted_forest(n, *, q=None, number_of_forests=None, seed=None)

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.

Parameters:

nint

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.

Returns:

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.

Raises:

ValueError

If n is non-zero but q is zero.

Notes

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.

References

[1]

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