Module degree_sequence_configuration_simple 

Configuration-model simple-graph degree-sequence generator (ALGO-GN-027).

Counterpart of the IGRAPH_DEGSEQ_CONFIGURATION_SIMPLE branch of igraph_degree_sequence_game() in references/igraph/src/games/degree_sequence.c (configuration_simple_undirected lines 552-594, configuration_simple_directed lines 597-708).

Like the multigraph configuration model (ALGO-GN-024) the algorithm builds a flat stub bag of size Σd and pairs stubs by an incremental Fisher–Yates shuffle. The key difference is that any self-loop or multi-edge produced during the inner shuffle aborts the attempt: the adjacency tracker is cleared and the entire attempt is restarted. The resulting distribution is exactly uniform on the set of simple realisations of the prescribed sequence — at the cost of an unbounded expected restart count for sequences that are hard to realise simply.

Undirected branch

Build stubs = [v repeated d_v times] of length Σd. Then for each i ∈ [0, |E|):

1. Pick k ← RNG(2i, |stubs|−1), swap stubs[2i] with stubs[k].
2. Pick k ← RNG(2i+1, |stubs|−1), swap stubs[2i+1] with stubs[k].
3. Let from = stubs[2i], to = stubs[2i+1]. If from == to (self-loop) or the pair is already adjacent, fail the attempt, clear adjacency, restart the inner loop. Otherwise record the edge in the adjacency tracker and continue.

This mirrors the C configuration_simple_undirected_set / configuration_simple_undirected_bitset helpers; we use a single Vec<HashSet<u32>> backend, which is what _set uses internally (the _bitset variant in C is only a memory-saving alternative for vcount ≤ 1024 and offers no algorithmic advantage).

Directed branch

Build out_stubs and in_stubs separately. Only out_stubs is shuffled (one FY swap per edge) — the in-bag is consumed in construction order, so to = in_stubs[i] is monotonically non-decreasing. This allows an O(1) multi-arc test via a vertex_done_mark counter trick: whenever to advances, bump the mark; a duplicate source is detected when vertex_done[from] == current_mark.

vs. siblings

• crate::degree_sequence_game_configuration (ALGO-GN-024) — no simplicity check; faster but produces a multigraph.
• crate::degree_sequence_game_fast_heur_simple (ALGO-GN-026) — biased single-pass heuristic with back-off-and-continue; 21–54× faster but NOT uniform on the simple-graph space.
• crate::degree_sequence_game_vl (ALGO-GN-025) — Viger–Latapy uniform sampler on the simple connected subspace; trades the connectivity guarantee for an MCMC mixing phase.

Determinism

A single SplitMix64 seed drives every shuffle and every retry. The PRNG is not bitwise portable to igraph C / NumPy / R, so the three-source conformance harness asserts structural invariants only (vcount, ecount = Σd/2 or Σout, exact out/in degree match, simplicity).

Failure modes

Non-graphical input is rejected up front by Erdős–Gallai (undirected) or Fulkerson–Chen–Anstee (directed). For sequences that pass the graphicality test but happen to be hostile to the rejection sampler (very dense, near-regular sequences), the attempt-restart counter is bounded by MAX_OUTER_ATTEMPTS; the function returns InvalidArgument once exhausted.

Constants

MAX_OUTER_ATTEMPTS

Cap on attempt restarts before giving up.

Functions

degree_sequence_game_configuration_simple

Uniform random simple graph realising the given degree sequence via the configuration-model rejection sampler (ALGO-GN-027).