Module tree 

Uniform random labelled tree generators (ALGO-GN-004).

Counterpart of igraph_tree_game() in references/igraph/src/games/tree.c. Two methods are available:

• LERW (tree_game_lerw) — Wilson’s loop-erased random walk on K_n. Supports both directed (out-rooted) and undirected trees.
• Prüfer (tree_game_prufer) — samples a random Prüfer sequence, then decodes it via from_prufer. Undirected only, matching the C upstream restriction.

Both methods produce each labelled tree with equal probability.

LERW algorithm

Wilson’s loop-erased random walk on the complete graph K_n uniformly samples spanning trees. The igraph implementation collapses the naive “walk until you hit a visited vertex, then erase the loop” formulation into a single linear pass:

1. Maintain an array vertices = [0, 1, …, n - 1] partitioned so that positions [0, k) hold the visited vertices and [k, n) hold the unvisited ones.
2. Pick an initial vertex i uniformly, mark it visited, swap it to position 0, set k = 1.
3. For each remaining step k = 1 .. n: draw j ∈ [0, n). If vertices[j] is already visited (its slot lies in [0, k)), advance the walk by setting i = vertices[j] and resample j ∈ [k, n) so the next visited vertex is guaranteed to be a fresh one. Then mark vertices[j] visited, swap it to position k, emit the edge (i, vertices[k]), and update i = vertices[k].

Each iteration produces exactly one edge, so the tree has n - 1 edges. Runtime is O(n) walk steps amortised — there is no rejection loop because step 3a covers the “already visited” branch in one shot.

Prüfer algorithm

Generate n - 2 uniform random values in [0, n), forming a Prüfer sequence, then decode it with the linear-time algorithm from from_prufer. The result is always an undirected labelled tree.

Functions

tree_game_lerw

Generate a uniformly random labelled tree on n vertices using Wilson’s loop-erased random walk.

tree_game_prufer

Generate a uniformly random labelled tree on n vertices using the Prüfer sequence method.