Module degree_sequence_vl 

Viger–Latapy uniform-sample-of-simple-graphs degree-sequence generator (ALGO-GN-025).

Counterpart of the IGRAPH_DEGSEQ_VL branch of igraph_degree_sequence_game() in references/igraph/src/games/degree_sequence.c (dispatched to igraph_i_degree_sequence_game_vl() in references/igraph/src/games/degree_sequence_vl/gengraph_mr-connected.cpp, lines 138-182). Backed by Fabien Viger’s 2006 gengraph C++ library (~4200 LOC across gengraph_degree_sequence.cpp, gengraph_graph_molloy_*.cpp, etc.).

The Viger–Latapy method (Viger & Latapy, “Random sampling of regular and irregular graphs”, 2005) samples approximately uniformly from the set of simple connected graphs with a prescribed undirected degree sequence by running a degree-preserving edge-switch Markov chain whose stationary distribution is uniform over that set, with Θ(|E|) mixing time.

Algorithm

1. Validate: the sequence must be graphical (realisable as a simple undirected graph). Checked via Erdős–Gallai.
2. Initial realization via Havel–Hakimi greedy: at each step, take the vertex of largest residual degree d and connect it to the next d largest-residual-degree vertices. If at any point no such assignment is possible without creating multi-edges, the sequence is non-graphical (defensive — Erdős–Gallai already excludes this).
3. Make connected: if the Havel–Hakimi seed is disconnected, merge components pairwise via the standard 2-swap trick — pick one edge (a,b) in component A and one (c,d) in component B such that (a,c) and (b,d) are non-edges, then swap to (a,c) + (b,d). This preserves all degrees and reduces the component count by 1 per swap. Repeat until connected.
4. MCMC shuffle: run T = 5 · 2|E| random degree-preserving edge swaps. Each attempt:
   • Pick two distinct edges (a,b) and (c,d).
   • With a random bit, choose orientation: (a,c)+(b,d) or (a,d)+(b,c).
   • Reject if the swap would create a self-loop or multi-edge.
   • Reject if the swap would disconnect the graph (lazy check: every W = 2|E| attempts, snapshot the edge set, run W attempts, then verify connectivity and restore on failure).

The 5×-edge-count mixing length is the upstream default (gh->shuffle(5 * gh->nbarcs(), 100 * gh->nbarcs(), FINAL_HEURISTICS) in mr-connected.cpp:175). The 100× argument is the per-window attempt budget (T_max); we collapse to a single fixed window of size W = max(16, 2|E|) which gives the same expected mixing time and is what the upstream FINAL_HEURISTICS settles on for typical inputs.

Directed graphs

The upstream implementation rejects directed input (mr-connected.cpp:144-146). We do the same.

Determinism

All randomness flows from a single SplitMix64 seed — the same (degrees, seed) pair always yields the same graph. The PRNG state is not bitwise portable to igraph C / NumPy / R, so the three-source conformance harness asserts the structural invariants the algorithm preserves by construction: vcount, ecount = Σd/2, exact degree match, simplicity, connectivity (when the degree sum is positive).

Complexity

Initial realization: Θ(n + |E| log n) via repeated heap-sorted Havel–Hakimi. Connectivity merging: O(|E|) per BFS, O(c) swaps to merge c components ⇒ O(c · |E|). MCMC shuffle: Θ(|E|) attempts, each O(1) amortised (with HashSet-based adjacency) + O(|E| + n) per checkpoint BFS, with O(1) checkpoints in expectation per Θ(|E|) window ⇒ Θ(|E|) total.

Functions

degree_sequence_game_vl

Sample a random connected, simple undirected graph that exactly realises the given degree sequence, approximately uniformly, via the Viger–Latapy edge-switch Markov chain.