Module k_regular 

k-regular random graph generator (ALGO-GN-008).

Counterpart of igraph_k_regular_game() in references/igraph/src/games/k_regular.c:57-83, which itself is a thin wrapper over igraph_degree_sequence_game() (see references/igraph/src/games/degree_sequence.c). We self-roll the two methods used by the wrapper rather than port the full degree-sequence machinery (~870 C lines covering eight sampling modes); that keeps the dependency footprint focused on what k-regular actually needs.

Model

Every vertex of the returned graph has degree exactly k. In the directed case both the in- and out-degree are k.

Two sampling regimes are exposed via the multiple flag, mirroring the upstream split:

• multiple = true — configuration model. Build n·k stubs (one per half-edge), pair them uniformly at random without replacement. Self-loops and parallel edges are allowed. Runtime O(n + |E|).
• multiple = false — fast-heuristic simple. Same stub bag, but reject any pair that would form a self-loop or duplicate an existing edge; failed stubs are queued into the next sweep over the residual degree sequence; if a sweep ends with no feasible pair the whole attempt is restarted from scratch. This is the sampling scheme IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE uses, and like the C reference it does not sample uniformly from the space of all simple k-regular graphs — every realisable graph appears with positive probability but not necessarily equal probability.

Validation

• k = 0 always succeeds and returns an edgeless graph.
• Undirected simple: requires k ≤ n - 1 and n·k even (handshake).
• Undirected multigraph: requires n·k even (handshake).
• Directed simple: requires k ≤ n - 1. The handshake parity constraint is automatically satisfied because in- and out-degrees match by construction.
• Directed multigraph: no degree-bound constraint, no parity constraint.
• n·k must fit in u32 (otherwise the stub vector overflows).

Determinism

Fully deterministic in (n, k, directed, multiple, seed) via SplitMix64.

Functions

k_regular_game

Generate a random k-regular graph on n vertices.