Expand description
LCF (Lederberg-Coxeter-Frucht) cubic-graph constructor (ALGO-CN-018).
Counterpart of igraph_lcf() in
references/igraph/src/constructors/lcf.c:52-99.
LCF notation is a compact encoding for 3-regular Hamiltonian graphs.
Given n vertices, a shift vector shifts and a repeats count, the
constructor builds a Hamilton cycle on 0..n and then adds chord
edges per shift, looping repeats * shifts.len() times.
Many small cubic graphs admit LCF descriptions — Franklin [5, -5]^6
on n=12, Truncated-tetrahedron [2, 6, -2, -6]^3 on n=12,
Truncated-octahedron [3, -7, 7, -3]^6 on n=24, Frucht
[-5, -2, -4, 2, 5, -2, 2, 5, -2, -5, 4, 2]^1 on n=12, Heawood
[5, -5]^7 on n=14, …
Per the C source, after the candidate edge list is emitted the graph
is simplified (self-loops + parallel edges removed) before being
returned. The Rust port handles this inline via a canonical (min, max) BTreeSet insert with self-loop skip so we never allocate a
duplicate-bearing intermediate graph.
igraph_lcf_small (varargs convenience) is intentionally not
ported — Rust has no varargs; callers pass the shift slice directly.
Time complexity: O(|V| + |E|).
Functions§
- lcf
- Construct an undirected graph from LCF notation.