Add Erdős–Rényi random graph generators G(n,p) and G(n,m)

[sraaphorst]

Summary

Add generators for the two standard Erdős–Rényi random graph models on the labelled vertex set

{0, 1, ..., vertexCount - 1}.

The models are:

• $G(n,p)$: every possible edge is included independently with probability $p$;
• $G(n,m)$: exactly (m) edges are selected uniformly from all $m$-element subsets of the possible edge set.

Suggested public API:

fun gnpRandomGraph(
    vertexCount: Int,
    edgeProbability: Double,
    random: Random = Random.Default,
): UndirectedGraph<Int>

fun gnmRandomGraph(
    vertexCount: Int,
    edgeCount: Long,
    random: Random = Random.Default,
): UndirectedGraph<Int>

These names expose the mathematical models directly. Exact return types and default arguments should follow existing Kosmos conventions.

A possible location is:

org.vorpal.kosmos.graphs.RandomGraphs.kt

The $G(n,p)$ model

There are

$$N = \binom{n}{2}$$

possible unordered edges.

For every pair

$$\{u,v\}, \qquad 0 \leq u < v < n,$$

include the edge independently with probability $p$.

For a particular labelled graph $G$ with $k$ edges,

$$\Pr(G)=p^k(1-p)^{N-k}.$$

Consequently:

• $p=0$ produces the edgeless graph;
• $p=1$ produces the complete graph;
• $p=\frac12$ makes all labelled simple graphs on the fixed vertex set equally likely.

A direct implementation is appropriate: traverse every unordered pair exactly once and perform one Bernoulli trial. This takes $O(N)$ time.

The $G(n,m)$ model

Select an $m$-element subset of the $N$ possible edges uniformly at random.

Every graph on the fixed labelled vertex set with exactly $m$ edges must have probability

$$\frac{1}{\binom{N}{m}}.$$

It is not sufficient merely to return a graph containing $m$ random-looking edges: the resulting $m$-edge subset must be uniformly distributed.

Avoid unrestricted repeated sampling

The simplest implementation repeatedly chooses a random possible edge and inserts it into a set until the set contains $m$ distinct edges.

This is mathematically correct if every possible edge is sampled uniformly, but duplicate samples make it increasingly inefficient as the selected set fills.

The expected number of draws required to obtain $m$ distinct values from $N$ possibilities is

$$N(H_N-H_{N-m}),$$

where $H_k$ is the $k$-th harmonic number.

Repeated sampling is reasonable when $m\ll N$, but it deteriorates badly as $m$ approaches $N$. Selecting the final missing edge alone requires $N$ draws in expectation.

The implementation should therefore use an explicit sampling-without-replacement strategy.

Candidate $G(n,m)$ strategies

1. Partial Fisher–Yates shuffle

Enumerate the $N$ possible edges, shuffle sufficiently to select the first $m$, and construct the graph from them.

Advantages:

• straightforward;
• exactly uniform;
• useful as a reference implementation.

Disadvantage:

• materializing every possible edge requires $O(N)$ memory even when $m$ is small.

2. Reservoir sampling

Stream the possible edges and maintain a uniform reservoir of size $m$.

Advantages:

• exactly uniform;
• requires $O(m)$ memory;
• does not materialize the complete edge list.

Disadvantage:

• still examines all $N$ possible edges and therefore takes $O(N)$ time.

3. Floyd’s sampling algorithm

Sample (m) distinct integers from $[0,N)$, then convert the sampled indices into unordered vertex pairs.

Advantages:

• exactly uniform;
• expected $O(m)$ time;
• $O(m)$ auxiliary storage;
• does not enumerate or materialize every possible edge when $m\ll N$.

This requires a consistent bijection

edge index in [0, N)  <->  pair (u, v), where 0 <= u < v < n.

The conversion can be based on triangular-number offsets.

4. Complement sampling for dense graphs

When $m&gt;N/2$, sample the $N-m$ excluded edges and take the complement.

This replaces the sampling parameter $m$ by

$$\min(m,N-m).$$

Complement sampling remains uniform because complementation is a bijection between $m$-edge subsets and $(N-m)$-edge subsets.

A good general strategy would therefore combine Floyd’s algorithm with complement sampling.

Edge indexing

If edge indices are used, the index-to-pair conversion should:

• avoid floating-point arithmetic;
• avoid overflow in triangular-number calculations;
• agree with a documented edge-enumeration order;
• be tested carefully at triangular-number boundaries.

The helper need not be public unless it has independent value elsewhere in the graph API.

Parameter validation

Reject:

• vertexCount < 0;
• non-finite edgeProbability;
• edgeProbability !in 0.0..1.0;
• edgeCount < 0;
• edgeCount > binomial(vertexCount, 2).

The calculation of $\binom n2$ must not overflow intermediate Int arithmetic.

A Long edge count is sufficient for an Int vertex count. The materialized finite graph representation and available memory will impose much smaller practical limits.

Randomness and reproducibility

Both functions should accept an explicit Random so that callers and tests can control the random source.

A fixed seed should reproduce the same result for a fixed Kosmos version and edge-enumeration convention. Avoid relying on unordered-set iteration order when doing so could make seeded behavior unstable.

These generators are intended for mathematical simulation and testing, not cryptographic use.

Tests

Add deterministic tests for:

• vertexCount = 0 and vertexCount = 1;
• $G(n,0)$ being edgeless;
• $G(n,1)$ being complete;
• $G(n,m)$ always having exactly (m) edges;
• $m=0$ producing an edgeless graph;
• $m=N$ producing a complete graph;
• the vertex set being exactly 0 until vertexCount;
• absence of loops and parallel edges;
• repeatability with a seeded Random;
• rejection of invalid parameters;
• edge-index/pair round trips, if indexing is used;
• triangular-number boundary cases;
• complement sampling producing the requested edge count.

For very small graphs, add non-flaky statistical checks for:

• approximate marginal edge probability in $G(n,p)$;
• approximate uniformity over the possible $m$-edge graphs in $G(n,m)$.

Acceptance criteria

• Add a generator for $G(n,p)$.
• Add a generator for $G(n,m)$.
• Preserve independence of edge trials in $G(n,p)$.
• Sample uniformly from all $m$-edge subsets in $G(n,m)$.
• Do not use unrestricted repeated sampling as the sole $G(n,m)$ strategy.
• Avoid materializing every possible edge on the sparse $G(n,m)$ path.
• Use complement sampling, or an equivalently efficient dense strategy, when appropriate.
• Validate all parameters and avoid arithmetic overflow.
• Support deterministic seeded tests.
• Add invariant, boundary, and small distributional tests.

This issue records the mathematical requirements and viable implementation strategies without prescribing a complete implementation.

Integrate with ArbGraph

kosmos-testkit already provides:

ArbGraph.undirectedGnP(...)
ArbGraph.undirectedGnM(...)

Refactor these generators to reuse the new core Erdős–Rényi implementations rather than maintaining independent sampling algorithms in ArbGraph.kt.

The current undirectedGnM implementation constructs the complete list of unordered vertex pairs before selecting m of them. This requires $O(\binom n2)$ time and memory even for sparse graphs and would bypass the sampling improvements introduced by this issue.

For generators over arbitrary vertex types:

1. Generate n distinct vertices from the supplied Arb<V>.
2. Generate the corresponding random graph on the index set {0, ..., n - 1}.
3. Relabel each index with its corresponding generated vertex.

Because the generated vertex list contains distinct values, this relabelling is injective.

The Arb implementation should use the RandomSource supplied by Kotest:

rs.random

and pass it into the core graph generator. It should not use Random.Default, since doing so would break Kotest seed reproducibility.

Additional acceptance criteria

• Retain ArbGraph.undirectedGnP.
• Retain ArbGraph.undirectedGnM.
• Delegate their graph sampling to the corresponding core generators.
• Preserve generation over arbitrary distinct vertex values.
• Preserve Kotest seed reproducibility through RandomSource.
• Remove duplicated $G(n,p)$ and $G(n,m)$ sampling logic from the testkit.
• Ensure that sparse undirectedGnM generation no longer materializes all $\binom n2$ possible edges.
• Test that generated $G(n,m)$ graphs always contain exactly m edges.
• Test that generated $G(n,p)$ graphs preserve the requested vertex count and simple-graph invariants.

[sraaphorst]

Note that this may already be done in ArbGraph.kt. Check the overlap and refactor as necessary.