Module watts 

Watts–Strogatz small-world model (ALGO-GN-009).

Counterpart of igraph_watts_strogatz_game() in references/igraph/src/games/watts_strogatz.c:75-118 for the dim = 1 case (1-D periodic ring) — by far the dominant use case and the original Watts & Strogatz Nature ’98 model. The upstream C entry point delegates to igraph_square_lattice plus igraph_rewire_edges; both helpers are folded directly into this module rather than ported as standalone APIs.

Model

Step 1: build a periodic 1-D ring on size vertices where every vertex is connected to the nei nearest neighbours on each side. Each vertex therefore has degree 2·nei exactly (the validation step rejects 2·nei + 1 > size, so the ring is always “wide enough” that the two sides do not overlap).

Step 2: walk the edge list and, independently for each endpoint of each edge, rewire with probability p. The new endpoint is sampled uniformly from the vertex set with the optional rejection rules:

• loops = false — a candidate equal to the other endpoint of the same edge is rejected, mirroring upstream’s “draw from [0, n-2] and remap to skip the kept endpoint” trick;
• multiple = false — a candidate that would create a duplicate of an existing edge is rejected. The C reference uses a custom linked-list adjacency for O(1) duplicate detection; we use a HashSet<(u32, u32)> of canonical pairs for the same effect.

Validation

• size ≥ 1.
• nei ≥ 0.
• 2·nei + 1 ≤ size (so the ring lattice has no overlap; for nei = 0 this collapses to size ≥ 1 which is already required).
• p ∈ [0, 1], NaN / infinity rejected.

Determinism

Fully deterministic in (size, nei, p, loops, multiple, seed) via SplitMix64.

Reference

Duncan J. Watts and Steven H. Strogatz, Collective dynamics of “small-world” networks, Nature 393, 440-442 (1998).

Functions

watts_strogatz_game

Generate a 1-D Watts–Strogatz small-world graph.