Module bipartite 

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

Counterpart of igraph_bipartite_game_gnp() and igraph_bipartite_game_gnm() from references/igraph/src/misc/bipartite.c:1646-1784 and :1365-1415.

Two bipartite analogues of the classical Erdős–Rényi models. Every result graph has n1 + n2 vertices: the bottom partition occupies ids 0..n1 (types[v] = false), the top partition occupies ids n1..n1+n2 (types[v] = true). Bipartite graphs have no self-loops and no within-partition edges; that constraint is enforced structurally by the pair-index decoders.

• G(n1, n2, p): every potential cross-partition edge is included independently with probability p. Sampled with the Batagelj–Brandes 2005 geometric-skip walk so the cost is O(n1 + n2 + |E|) rather than O(n1·n2).

• G(n1, n2, m): exactly m distinct cross-partition edges drawn uniformly at random from the max_edges(n1, n2, directed, mode) possible. Sampled with Floyd’s algorithm for an O(m) distinct draw.

Edge direction (directed graphs)

BipartiteMode mirrors igraph’s IGRAPH_OUT / IGRAPH_IN / IGRAPH_ALL:

• BipartiteMode::Out — arcs go bottom → top.
• BipartiteMode::In — arcs go top → bottom.
• BipartiteMode::All — each ordered pair is sampled independently, so mutual pairs (b → t, t → b) are possible. The pair space doubles to 2·n1·n2.

For undirected graphs the mode argument is ignored; the sampler walks the same n1·n2 pair space and stores each edge canonically.

Determinism

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

Scope

gnp / gnm port the most-used path: simple bipartite graphs. bipartite_iea_game covers the IGRAPH_MULTI_SW multigraph model via independent edge assignment (edges drawn with replacement). Upstream’s IGRAPH_EDGE_LABELED variant and the gnp_bipartite_large overflow path for n1·n2 > 2^53 remain out of scope — they will land as follow-up AWUs if real users ask for them.

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).

Structs

BipartiteGraph

Result of bipartite_game_gnp / bipartite_game_gnm: the graph together with the boolean type vector that names every vertex as bottom (false) or top (true).

Enums

BipartiteMode

Edge-direction policy for the directed variants of the bipartite Erdős–Rényi models. See module docs for the mode semantics.

Functions

bipartite_game_gnm

Generate a random bipartite graph from the G(n1, n2, m) model.

bipartite_game_gnp

Generate a random bipartite graph from the G(n1, n2, p) model.

bipartite_iea_game

Generate a random bipartite multigraph through independent edge assignment (IEA).