Module kautz 

Kautz graph constructor (ALGO-CN-013).

Counterpart of igraph_kautz() in references/igraph/src/constructors/kautz.c:61-210.

The Kautz graph K(m, n) is the directed graph whose vertices are length-n+1 strings over an alphabet of m+1 letters, with the constraint that no two consecutive letters in the string may be equal. There is an arc from v = (a_0, …, a_n) to w = (a_1, …, a_n, b) for every alphabet letter b ≠ a_n. Each vertex therefore has out-degree exactly m and in-degree exactly m; the total arc count is m · (m+1) · m^n.

Vertex count is (m+1) · m^n. Vertices are encoded as base-(m+1) integers in [0, (m+1)^(n+1)), but only those whose digit sequence avoids consecutive repeats are valid — we build two index tables (index1, index2) to map between the sparse string codes and the dense [0, vcount) vertex ids, just like the upstream C source.

Degenerate forms (match upstream order in kautz.c lines 81-86):

• n == 0 → (m+1)-vertex directed complete graph with no self-loops (K_{m+1} directed). For m == 0 ∧ n == 0 this collapses to a singleton. The C source delegates to igraph_full; we inline the emission to avoid pulling in a not-yet-ported full-graph helper.
• m == 0 ∧ n ≥ 1 → empty 0-vertex directed graph (no valid string survives the consecutive-distinct constraint when only one symbol exists).

Time complexity: O(|V| + |E|) — both the index-table construction and the arc emission are linear in the output.

Functions

kautz

Build the Kautz graph K(m, n).