Module regular_tree 

Regular tree constructor (ALGO-CN-006).

Counterpart of igraph_regular_tree() in references/igraph/src/constructors/regular.c:806-865.

A regular tree (a.k.a. Bethe lattice) of height h and degree k is a rooted tree where every non-leaf vertex has total degree exactly k. Concretely:

• the root has k children (its total degree is k),
• every internal non-root vertex has k - 1 children plus its parent, so its total degree is also k,
• leaves sit at depth h and have degree 1.

This is different from a k-ary tree (where every internal vertex — including the root — has the same number of children), and from a symmetric tree (where the branching factor varies per level).

Upstream C builds it as a thin wrapper over igraph_symmetric_tree by constructing branches = [k, k - 1, k - 1, ...] of length h and delegating. The Rust port mirrors that.

Vertex count: 1 + k * Σ_{i=0..h} (k-1)^i = 1 + k * ((k-1)^h - 1) / (k - 2) for k >= 3; 1 + h for k = 2 (degenerate linear chain).

Edge count: n - 1 (a tree).

Time complexity: O(|V|).

See also kary_tree / symmetric_tree for the related shapes.

Functions

regular_tree

Build a regular tree (Bethe lattice) of height h and degree k.