Module hypercube 

Hypercube constructor (ALGO-CN-007).

Counterpart of igraph_hypercube() in references/igraph/src/constructors/regular.c:983-1003.

The n-dimensional hypercube graph Q_n has 2^n vertices and 2^(n-1) * n edges. Two vertices are connected when the binary representations of their zero-based vertex IDs differ in exactly one bit.

Small cases:

• n = 0 → singleton (one vertex, zero edges)
• n = 1 → K2 (two vertices, one edge: (0, 1))
• n = 2 → 4-cycle ((0,1), (0,2), (1,3), (2,3))
• n = 3 → 8-vertex cube (12 edges)

The graph is n-regular (every vertex has degree n) and bipartite (vertices split into two classes by the parity of their popcount).

Algorithm: enumerate all 2^n vertices in id order; for each vertex v and bit i ∈ [0, n) toggle that bit to get u = v ^ (1 << i), and emit the canonical edge (v, u) only when v < u so each edge is produced exactly once. Mirrors the upstream C loop.

Time complexity: O(2^n · n) = O(|V| · log |V|) = O(|E|).

Upper bound

n is capped at 30 so that:

• vertex count 2^n fits comfortably in u32,
• edge count 2^(n-1) · n fits in usize on every supported platform (≤ ~1.6 × 10^10 on n = 30, well within 64-bit usize::MAX; this lets the edges Vec allocation succeed even on 32-bit targets where usize::MAX ≈ 4 × 10^9 — at n = 30 it would exhaust usize, but real workloads stay far below it).

Constants

MAX_HYPERCUBE_DIMENSION

Maximum dimension accepted by hypercube.

Functions

hypercube

Build the n-dimensional hypercube graph Q_n.