Module edge_switching_simple 

Edge-switching MCMC degree-sequence simple-graph sampler (ALGO-GN-028).

Counterpart of the IGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE branch of igraph_degree_sequence_game() in references/igraph/src/games/degree_sequence.c (edge_switching lines 712-722). The reference dispatches to igraph_realize_degree_sequence(..., IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_INDEX) for the deterministic seed, then runs igraph_rewire(graph, 10 * ecount, IGRAPH_SIMPLE_SW, NULL) for the MCMC mixing phase. We inline both phases to keep this AWU self-contained.

Phase 1 — deterministic seed via Havel–Hakimi (undirected) /

Kleitman–Wang (directed), INDEX order

• Undirected: maintain residual[v] = d_v (mutable copy). For each i ∈ [0, n), treat vertex i as the hub with residual degree r = residual[i]. Collect the r other vertices with the highest current residual degrees (skipping i). Add edges (i, spoke) and decrement each spoke’s residual. Set residual[i] = 0. If at any step fewer than r valid spokes exist the sequence is non-graphical (rejected up front by the shared Erdős–Gallai pre-check, so this is only a guard).
• Directed: same loop over vertices in index order. At step i, sort the remaining vertices by (in-residual, out-residual) descending and connect vertex i’s out_residual[i] out-stubs to the top-r distinct vertices (skipping i itself), decrementing their in-residuals. Mirrors igraph_i_kleitman_wang_index.

These seed builders are RNG-free. The Erdős–Gallai / Fulkerson–Chen–Anstee pre-checks (shared via pub(crate) helpers in crate::algorithms::games::degree_sequence_fast_heur) guarantee they always succeed when called from this entry point.

Phase 2 — degree-preserving edge-switching MCMC

The mixing kernel runs 10 · |E| trials (matches the upstream constant). Each trial:

1. Sample e1 ← RNG(0, |E|-1), then e2 ← RNG(0, |E|-1) until e1 ≠ e2.
2. Let (a,b) = edge e1, (c,d) = edge e2.
3. Undirected only: with probability 0.5, swap c and d. This is what lets the MCMC consider both rewiring orientations from one pair of edges.
4. Reject if a == c or b == d (the swap would be a no-op).
5. Reject if a == d or b == c (the swap would create a self-loop, and the simple-graph constraint forbids self-loops).
6. Reject if the rewired endpoints (a,d) or (c,b) already form an edge in the current graph (would create a multi-edge).
7. Otherwise apply the swap: replace (a,b),(c,d) with (a,d),(c,b) in both the edge list and the adjacency tracker.

Both successful and failed trials count toward the 10 · |E| budget. This is necessary for the chain to be detailed-balanced; conditioning on success would bias the stationary distribution.

vs. siblings

• crate::degree_sequence_game_configuration (ALGO-GN-024) — no simplicity guarantee; produces a multigraph.
• crate::degree_sequence_game_configuration_simple (ALGO-GN-027) — exact-uniform rejection sampler on the simple-graph space; cost grows as exp(O((Σd/n)²)). This MCMC variant trades exact uniformity for O(|E|) runtime independent of density.
• crate::degree_sequence_game_fast_heur_simple (ALGO-GN-026) — biased single-pass heuristic; fastest but not asymptotically uniform.
• crate::degree_sequence_game_vl (ALGO-GN-025) — Viger–Latapy MCMC on simple connected graphs; trades the connectivity guarantee for tighter mixing bounds.

Determinism

A single SplitMix64 seed drives both the (RNG-free) seed phase and every rewire trial. The PRNG is not bitwise portable to igraph C / NumPy / R, so the three-source conformance harness asserts structural invariants only (vcount, ecount, exact degree match, simplicity).

Failure modes

Non-graphical input is rejected up front by Erdős–Gallai (undirected) or Fulkerson–Chen–Anstee (directed). The seed builder and MCMC kernel never abort after that point: the sampler is best-effort and returns whatever simple graph the chain has reached after 10 · |E| trials, exactly mirroring upstream semantics.

Constants

REWIRE_TRIALS_PER_EDGE

Upstream constant: number of rewire trials per edge. The C reference hard-codes 10 * igraph_ecount(graph) in edge_switching() at references/igraph/src/games/degree_sequence.c:719.

Functions

degree_sequence_game_edge_switching_simple

Sample a random simple graph realising the given degree sequence via degree-preserving edge-switching MCMC (ALGO-GN-028).