Module kary_tree 

k-ary tree constructor (ALGO-CN-004).

Counterpart of igraph_kary_tree() in references/igraph/src/constructors/regular.c:608-706.

A k-ary tree on n vertices is the rooted tree obtained by attaching children to parents in breadth-first order: vertex 0 is the root, vertex 1..=children are its kids, then vertex 1’s kids, then vertex 2’s kids, and so on. Almost every internal vertex has exactly children children — the last internal vertex may have fewer if n - 1 is not a multiple of children. Arc direction is controlled by TreeMode:

• TreeMode::Out — directed, every edge flows from parent to child (parent → child).
• TreeMode::In — directed, every edge flows from child to parent (child → parent).
• TreeMode::Undirected — undirected; raw endpoints are (parent, child) but stored as canonical (min, max) by Graph::add_edges.

Edge enumeration mirrors the upstream C loop exactly: a to pointer starts at 1 and advances once per emitted edge; an outer parent pointer starts at 0 and increments after every batch of children edges (or when n - 1 edges have been emitted in total). For n - 1 edges total, the result is always a tree (acyclic, connected when undirected, weakly connected otherwise).

Edge counts:

• n = 0 — no edges (empty graph).
• n = 1 — no edges (singleton root).
• n ≥ 2, all modes — n - 1 edges.

Time complexity: O(|V|).

Enums

TreeMode

Direction policy for kary_tree.

Functions

kary_tree

Build a k-ary tree on n vertices where each non-leaf parent has up to children kids attached in BFS order.