Module degree_sequence 

Configuration-model degree-sequence generator (ALGO-GN-024).

Counterpart of the IGRAPH_DEGSEQ_CONFIGURATION branch of igraph_degree_sequence_game() in references/igraph/src/games/degree_sequence.c (function configuration, lines 37-123).

The configuration model (Bender–Canfield 1978 / Bollobás 1980) builds a random graph that realises a given degree sequence by stub matching:

1. Expand each vertex i into d_i half-edge “stubs” — a flat bag of Σ d_i stubs.
2. Repeatedly pick two stubs uniformly at random and pair them into an edge.
3. Project the matched stubs to a graph by reading off vertex labels.

The result is a multigraph — self-loops and multi-edges are allowed and occur with positive probability whenever the degree sequence permits them. To sample uniformly from simple graphs with a given degree sequence, use the Viger–Latapy (VL) or EDGE_SWITCHING_SIMPLE methods instead (planned for follow-up AWUs GN-025+).

Directed vs undirected

• Undirected (in_degrees = None): single bag of size outsum = Σ out_degrees. Each iteration pops two stubs (with replacement-via-swap-pop) and emits a single edge. Requires outsum to be even so the bag fully drains.
• Directed (in_degrees = Some(in_seq)): two bags. Out-stubs are the edge sources, in-stubs the sinks. Requires Σ out_degrees == Σ in_degrees.

Determinism

All randomness flows from a single SplitMix64 seed — the same (out_degrees, in_degrees, seed) triple always yields the same graph. The PRNG state is not bitwise portable to igraph C / NumPy / R, so the three-source conformance harness asserts structural invariants only (vcount, ecount, exact degree match, directed-ness).

Complexity

Stub-bag construction: Θ(n + Σ d_i). Edge sampling: Θ(|E|) with O(1) random-access pops via Fisher-Yates–style swap-removal. Total: Θ(n + |E|) time and Θ(|E|) peak memory for the bags.

Functions

degree_sequence_game_configuration

Sample a random graph realising the given degree sequence(s) via the configuration / stub-matching model.