Module degree_sequence_fast_heur 

Fast-heuristic simple-graph degree-sequence generator (ALGO-GN-026).

Counterpart of the IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE branch of igraph_degree_sequence_game() in references/igraph/src/games/degree_sequence.c (fast_heur_undirected lines 125-261, fast_heur_directed lines 263-402).

The routine samples a simple graph (no self-loops, no multi-edges) with a prescribed degree sequence using a one-pass stub-matching heuristic with single-cycle backtracking:

1. Build a stub bag from the residual degree sequence and shuffle it.
2. Walk pairs (stubs[2i], stubs[2i+1]); accept the edge if it would not create a self-loop and the endpoint pair is not yet incident. Otherwise bump residual degrees on both endpoints and mark them as “incomplete”.
3. If the incomplete set is empty, the attempt succeeded.
4. Else, scan the incomplete vertices for a feasible non-edge pair. If at least one exists, repeat from (1) using only the residual stubs. If none exists, restart the entire attempt from scratch.

Unlike the configuration-model generator (ALGO-GN-024), the output is guaranteed to be simple. Unlike the Viger–Latapy sampler (ALGO-GN-025), the result is not uniform on the space of simple graphs realising the sequence: the bias of the heuristic is acceptable for many applications but is the price for a single-pass attempt with O(Σd · log Σd) complexity on the median attempt.

Directed vs undirected

• Undirected (in_degrees = None): one stub bag, paired as (stubs[2i], stubs[2i+1]) after a Fisher–Yates shuffle.
• Directed (in_degrees = Some(in_seq)): two stub bags (out + in). Only the out-bag is shuffled; the in-bag is consumed in construction order, matching the C reference.

Connectivity

This generator does not enforce connectivity. For uniformly random simple connected samples use degree_sequence_game_vl (ALGO-GN-025).

Determinism

A single SplitMix64 seed drives every shuffle. 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, exact degree match, simplicity).

Failure modes

Non-graphical input is rejected up front. For sequences that pass the graphicality test but happen to be especially hostile to the heuristic (e.g. very dense, near-regular sequences with low slack), the attempt-restart counter is bounded by MAX_OUTER_ATTEMPTS (1024); the function returns InvalidArgument once exhausted.

Functions

degree_sequence_game_fast_heur_simple

Sample a simple graph realising the given degree sequence(s) via the fast-heuristic single-pass + restart algorithm.