Module grg 

Geometric random graph (ALGO-GN-005).

Counterpart of igraph_grg_game() in references/igraph/src/games/grg.c:56-174.

Model

Drop n points uniformly at random on the unit square [0, 1) × [0, 1), then connect every pair (i, j) whose Euclidean distance is strictly less than radius. With torus = true the square is identified along opposite edges (periodic boundary conditions), so distances wrap modulo 1 along each axis.

Algorithm — x-sweep with width-radius window

1. Sample 2n independent Uniform[0, 1) values to populate xs and ys. The (x, y) pairing is not preserved — upstream’s igraph_vector_sort(xx) mutates only the x array, leaving ys in generation order. The resulting (x, y) joint marginal is still uniform because the two axes were independent, but the original point identities are lost. We mirror this behaviour exactly.
2. Sort xs in ascending order. For every i in 0..n walk a forward window j = i + 1, i + 2, … while xs[j] - xs[i] < radius. Whenever the squared distance falls below radius², emit the edge (i, j).
3. Torus mode adds a wrap-around tail: once the forward window crosses j = n, continue at j = 0, 1, … for as long as the wrapped x-gap 1 - xs[i] + xs[j] is below radius. The y coordinate is wrapped with min(|Δy|, 1 - |Δy|).

Both modes run in O(n + |E|) expected time once the sort cost O(n log n) is paid up front. The window invariant means each candidate pair is inspected exactly once, regardless of how dense the graph is.

Determinism

grg_game is fully deterministic in (n, radius, torus, seed). The PRNG is SplitMix64; reusing the same seed in another generator (e.g. crate::tree_game_lerw) is safe — each call owns a fresh SplitMix64 instance.

Scope

The upstream signature accepts optional output vectors for x and y coordinates. We provide both flavours: grg_game returns the graph only, and grg_game_with_coords returns the sorted xs and the original-order ys. Both call into the same internal worker so the edge set is byte-for-byte identical for the same seed.

Functions

grg_game

Generate a geometric random graph on n uniformly placed points in the unit square, connecting pairs strictly closer than radius in Euclidean distance.

grg_game_with_coords

Same as grg_game but also returns the point coordinates.