Module circulant 

Circulant graph constructor (ALGO-CN-011).

Counterpart of igraph_circulant() in references/igraph/src/constructors/circulant.c:51-112.

A circulant graph G(n, shifts) has n vertices v_0, …, v_{n-1} and, for every shift s in shifts, the edges (v_j, v_{(j + s) mod n}) for every j ∈ [0, n).

The constructor handles a few canonical-form rules so the same graph is built regardless of how shifts are spelled:

• Each shift is reduced modulo n into [0, n).
• In the undirected case, a shift s and its complement n − s generate the same set of edges, so a shift ≥ (n + 1) / 2 is replaced with n − s before dedup.
• shift == 0 is always dropped (it would emit n self-loops).
• Repeated shifts (after the above normalisation) are deduplicated so the result has no parallel edges.
• Special case: when n is even, the graph is undirected, and a shift equals n / 2, only the first n / 2 edges are emitted — the wrap-around would otherwise produce a duplicate of every antipodal edge.

Specializations:

• circulant(n, &[1], false) is ring_graph(n) — the cycle C_n.
• circulant(n, &[k], false) (with 0 < k < n/2) is precisely the inner layer of generalized_petersen(n, k).
• circulant(n, &[1, 2], false) is the squared cycle / Möbius ladder family.
• circulant(n, &(1..n/2).collect::<Vec<_>>(), false) is the complete graph K_n (every distinct undirected shift contributes).

Time complexity: O(|V| · |shifts|).

Functions

circulant

Build the circulant graph G(n, shifts).