Module de_bruijn 

De Bruijn graph constructor (ALGO-CN-012).

Counterpart of igraph_de_bruijn() in references/igraph/src/constructors/de_bruijn.c:58-113.

The De Bruijn graph B(m, n) is the directed graph on m^n vertices whose vertices are length-n strings drawn from an alphabet of m symbols. There is an arc from vertex v = (a_1, …, a_n) to vertex w = (a_2, …, a_n, b) for every alphabet symbol b — that is, w is obtained from v by dropping the first symbol and appending one. Each vertex therefore has out-degree exactly m and in-degree exactly m (when n ≥ 1); the total arc count is m^(n+1) = m · vcount.

Vertices are encoded as integers in [0, m^n) via the little-endian base-m interpretation that upstream uses. The arc-rewrite then reduces to integer arithmetic: from i, the m successors are ((i * m) mod m^n) + b for b ∈ [0, m).

Degenerate forms:

• n == 0 → exactly 1 directed vertex with no arcs (matches upstream — there is exactly one length-0 string and the rewrite has no symbol to append).
• m == 0 → exactly 0 vertices (null graph).
• m == 1, n == 1 → 1 vertex with a single self-loop (the lone string maps to itself).
• B(2, 1) is the directed graph on {0, 1} with all four arcs (including both self-loops).

Time complexity: O(|V| + |E|) = O(m^(n+1)).

Functions

de_bruijn

Build the De Bruijn graph B(m, n).