Module erdos_renyi 

Erdős–Rényi random graph generators (ALGO-GN-001).

Counterpart of igraph_erdos_renyi_game_gnp() and igraph_erdos_renyi_game_gnm() from references/igraph/src/games/erdos_renyi.c:715 and :429.

Two classic models — both fix the vertex count n:

• G(n, p): every possible vertex pair is independently connected with probability p. The expected edge count is p · max_edges. Sampled via Batagelj & Brandes 2005’s geometric-skip algorithm so the cost is O(|V| + |E|) rather than O(|V|²).

• G(n, m): exactly m distinct edges are chosen uniformly at random from the max_edges possible. Sampled with Floyd’s algorithm for an O(m) distinct-pair draw, then each pair-index is decoded into a (from, to) pair using the same formulas the upstream C implementation uses.

Both functions are deterministic given the seed argument and run against the shared SplitMix64 PRNG.

Scope

MVP scope ports the most-used path: simple graphs, with loops optionally enabled. Multigraphs (multiple = true) and the edge-labeled IEA variant are out of scope for this AWU — they will land as follow-up AWUs if real users ask for them. Returning an IgraphError::Unimplemented-style variant from a hypothetical multigraph flag would be the wrong API shape (the flag could never be true), so we simply omit it from the public surface.

References

• V. Batagelj and U. Brandes, “Efficient generation of large random networks”, Phys. Rev. E 71, 036113 (2005).
• R. W. Floyd, Algorithm 489: The algorithm SELECT …, CACM (1972) — the distinct-sample technique used in G(n, m).

Functions

erdos_renyi_gnm

Generate a random graph from the G(n, m) Erdős–Rényi model.

erdos_renyi_gnp

Generate a random graph from the G(n, p) Erdős–Rényi model.