Module iea_game 

Independent Edge Allocation random multigraph generator (ALGO-GN-031).

Counterpart of igraph_iea_game() from references/igraph/src/games/erdos_renyi.c:480-542.

The IEA model generates a random multigraph on n vertices with exactly m edges. Each edge is independently assigned to an ordered vertex pair drawn uniformly at random; when loops is false the pair (u, u) is excluded from the sample space.

Because every edge is sampled independently, the model:

• Always produces exactly m edges (no rejection sampling against simplicity).
• Admits multi-edges by construction — the same vertex pair can be drawn many times.
• Optionally admits self-loops (when loops = true).

This sampler is not uniform over the space of multigraphs. As upstream’s docstring notes, the probability of a directed multigraph is proportional to 1 / Π_{i,j} A_ij! (with the usual double-factorial correction for the undirected diagonal). Two equivalent interpretations:

• It uniformly samples edge-labelled graphs in which the m edges are distinguishable.
• For the special case of simple graphs (i.e. multigraph realisations without repeated pairs) the IEA model gives every simple graph the same probability — but conditional on simplicity, the sampler is equivalent to G(n, m) without replacement.

Use crate::erdos_renyi_gnm when uniform sampling over simple graphs is required, or when avoiding multi-edges is a hard constraint.

Time complexity: O(|V| + |E|) — one PRNG draw (two for directed && loops) per edge plus the final Graph::add_edges insertion.

Scope

Direct port of igraph_iea_game. No special arguments; mirrors the upstream (n, m, directed, loops) signature plus our standard seed. The IGRAPH_EXPERIMENTAL tag upstream applies to the C API, not to the algorithm — the model itself is well-established (independent edge allocation, sometimes called “edge-labelled Erdős–Rényi” or the “random multigraph with given size”).

References

• Janson, S. “Random graphs and trees”. The independent-edge- assignment construction is the textbook starting point for many multigraph results.
• igraph C documentation for igraph_iea_game (experimental API).

Functions

iea_game

Generate a random multigraph through independent edge allocation.