rust_igraph/algorithms/constructors/
lcf.rs

1//! LCF (Lederberg-Coxeter-Frucht) cubic-graph constructor (ALGO-CN-018).
2//!
3//! Counterpart of `igraph_lcf()` in
4//! `references/igraph/src/constructors/lcf.c:52-99`.
5//!
6//! LCF notation is a compact encoding for 3-regular Hamiltonian graphs.
7//! Given `n` vertices, a shift vector `shifts` and a `repeats` count, the
8//! constructor builds a Hamilton cycle on `0..n` and then adds chord
9//! edges per shift, looping `repeats * shifts.len()` times.
10//!
11//! Many small cubic graphs admit LCF descriptions — Franklin `[5, -5]^6`
12//! on `n=12`, Truncated-tetrahedron `[2, 6, -2, -6]^3` on `n=12`,
13//! Truncated-octahedron `[3, -7, 7, -3]^6` on `n=24`, Frucht
14//! `[-5, -2, -4, 2, 5, -2, 2, 5, -2, -5, 4, 2]^1` on `n=12`, Heawood
15//! `[5, -5]^7` on `n=14`, …
16//!
17//! Per the C source, after the candidate edge list is emitted the graph
18//! is **simplified** (self-loops + parallel edges removed) before being
19//! returned. The Rust port handles this inline via a canonical `(min,
20//! max)` `BTreeSet` insert with self-loop skip so we never allocate a
21//! duplicate-bearing intermediate graph.
22//!
23//! `igraph_lcf_small` (varargs convenience) is intentionally **not**
24//! ported — Rust has no varargs; callers pass the shift slice directly.
25//!
26//! Time complexity: `O(|V| + |E|)`.
27
28use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
29use std::collections::BTreeSet;
30
31/// Construct an undirected graph from LCF notation.
32///
33/// `n` is the vertex count, `shifts` is the chord shift sequence
34/// (entries may be negative — wraparound is modular), and `repeats`
35/// controls how many full passes over `shifts` to walk.
36///
37/// The result is always undirected and always simple (self-loops and
38/// parallel edges introduced by the chord pattern are removed in place).
39///
40/// # Errors
41///
42/// * [`IgraphError::InvalidArgument`] — `n + repeats * shifts.len()`
43///   overflows the internal edge-buffer index.
44///
45/// # Examples
46///
47/// ```
48/// use rust_igraph::lcf;
49///
50/// // Franklin graph: [5, -5]^6 on n=12 — 12 vertices, 18 edges, bipartite cubic.
51/// let franklin = lcf(12, &[5, -5], 6).unwrap();
52/// assert_eq!(franklin.vcount(), 12);
53/// assert_eq!(franklin.ecount(), 18);
54/// assert!(!franklin.is_directed());
55/// ```
56pub fn lcf(n: u32, shifts: &[i64], repeats: u32) -> IgraphResult<Graph> {
57    // Overflow guard for the candidate-edge count: n + repeats * len.
58    let len = u32::try_from(shifts.len()).map_err(|_| {
59        IgraphError::InvalidArgument(format!(
60            "lcf: shifts.len() = {} exceeds u32::MAX",
61            shifts.len()
62        ))
63    })?;
64    let chord_count = repeats.checked_mul(len).ok_or_else(|| {
65        IgraphError::InvalidArgument(format!(
66            "lcf: repeats * shifts.len() = {repeats} * {len} overflows u32",
67        ))
68    })?;
69    let _total_candidates = n.checked_add(chord_count).ok_or_else(|| {
70        IgraphError::InvalidArgument(format!(
71            "lcf: n + repeats * shifts.len() = {n} + {chord_count} overflows u32",
72        ))
73    })?;
74
75    // Degenerate: n == 0 short-circuits to the empty graph regardless of
76    // shifts/repeats. This matches upstream regression test for bug #996
77    // (igraph_lcf_small(&g, 0, 0) → vcount==0 && ecount==0).
78    if n == 0 {
79        return Graph::new(0, false);
80    }
81
82    // Canonical-edge accumulator — every chord/backbone insert is
83    // canonicalised to (min, max) and deduplicated, with self-loops
84    // skipped. This collapses what the C source delegates to
85    // `igraph_simplify(loops=true, multi=true)` into a single pass.
86    let mut edge_set: BTreeSet<(VertexId, VertexId)> = BTreeSet::new();
87
88    // 1) Hamilton cycle on 0..n. Edge (n-1, 0) closes the ring; for n==1
89    //    the loop emits a single self-loop (i=0 → (0, 1 mod 1) = (0, 0))
90    //    which the self-loop skip drops. For n==2 backbone (0,1) is the
91    //    only edge that survives — chord wraparound from both endpoints
92    //    is symmetric and collapses to (0,1) again.
93    for i in 0..n {
94        let from = i;
95        let to = (i + 1) % n;
96        if from != to {
97            let (lo, hi) = if from < to { (from, to) } else { (to, from) };
98            edge_set.insert((lo, hi));
99        }
100    }
101
102    // 2) Chord pass — repeats * len candidate edges. The C source uses
103    //    `(no_of_nodes + sptr + sh) % no_of_nodes` where `sh` is signed
104    //    and `no_of_nodes + sptr` is wide enough to keep the intermediate
105    //    non-negative for sane inputs. We use `i64::rem_euclid` so even
106    //    pathologically large negative shifts wrap correctly.
107    if chord_count > 0 && !shifts.is_empty() {
108        let n_i64 = i64::from(n);
109        for sptr in 0..chord_count {
110            let shift = shifts[(sptr % len) as usize];
111            let from = sptr % n;
112            // (n + sptr + shift) mod n, computed with Euclidean modulus
113            // so a negative offset wraps positively.
114            let to_i64 = (i64::from(sptr) + shift).rem_euclid(n_i64);
115            let to = u32::try_from(to_i64).map_err(|_| {
116                IgraphError::InvalidArgument(format!("lcf: chord target {to_i64} out of u32 range"))
117            })?;
118            if from != to {
119                let (lo, hi) = if from < to { (from, to) } else { (to, from) };
120                edge_set.insert((lo, hi));
121            }
122        }
123    }
124
125    let mut graph = Graph::new(n, false)?;
126    graph.add_edges(edge_set)?;
127    Ok(graph)
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133
134    fn canonical_edges(g: &Graph) -> Vec<(VertexId, VertexId)> {
135        let m = u32::try_from(g.ecount()).expect("ecount fits u32 in tests");
136        let mut out: Vec<(VertexId, VertexId)> = (0..m)
137            .map(|e| g.edge(e).expect("edge in range"))
138            .map(|(a, b)| if a <= b { (a, b) } else { (b, a) })
139            .collect();
140        out.sort_unstable();
141        out
142    }
143
144    fn degree(g: &Graph, v: VertexId) -> usize {
145        g.neighbors(v).expect("neighbors").len()
146    }
147
148    #[test]
149    fn null_graph_regression_bug_996() {
150        let g = lcf(0, &[], 0).unwrap();
151        assert_eq!(g.vcount(), 0);
152        assert_eq!(g.ecount(), 0);
153        assert!(!g.is_directed());
154    }
155
156    #[test]
157    fn franklin_5_minus5_repeats_6() {
158        // Franklin graph: [5, -5]^6 on 12 vertices → 18 edges, cubic.
159        let g = lcf(12, &[5, -5], 6).unwrap();
160        assert_eq!(g.vcount(), 12);
161        assert_eq!(g.ecount(), 18);
162        for v in 0..12 {
163            assert_eq!(degree(&g, v), 3, "Franklin must be 3-regular at v={v}");
164        }
165    }
166
167    #[test]
168    fn three_minus2_repeats_4_n8_yields_16_edges() {
169        // Upstream: [3, -2]^4, n=8 → ecount 16.
170        let g = lcf(8, &[3, -2], 4).unwrap();
171        assert_eq!(g.vcount(), 8);
172        assert_eq!(g.ecount(), 16);
173    }
174
175    #[test]
176    fn n2_collapses_to_single_edge_two_chord_pattern() {
177        // Upstream: [2, -2]^2, n=2 → ecount 1 (all chords are self-loops).
178        let g = lcf(2, &[2, -2], 2).unwrap();
179        assert_eq!(g.vcount(), 2);
180        assert_eq!(g.ecount(), 1);
181        assert_eq!(canonical_edges(&g), vec![(0, 1)]);
182    }
183
184    #[test]
185    fn n2_collapses_to_single_edge_one_chord() {
186        // Upstream: [2]^2, n=2 → ecount 1.
187        let g = lcf(2, &[2], 2).unwrap();
188        assert_eq!(g.vcount(), 2);
189        assert_eq!(g.ecount(), 1);
190    }
191
192    #[test]
193    fn empty_shifts_yields_pure_cycle() {
194        let g = lcf(6, &[], 0).unwrap();
195        assert_eq!(g.vcount(), 6);
196        assert_eq!(g.ecount(), 6);
197        for v in 0..6 {
198            assert_eq!(degree(&g, v), 2);
199        }
200    }
201
202    #[test]
203    fn repeats_zero_yields_pure_cycle() {
204        let g = lcf(5, &[1, 2, 3], 0).unwrap();
205        assert_eq!(g.vcount(), 5);
206        assert_eq!(g.ecount(), 5);
207    }
208
209    #[test]
210    fn heawood_graph_5_minus5_repeats_7() {
211        // Heawood: [5, -5]^7 on n=14 → 21 edges, cubic, bipartite, girth 6.
212        let g = lcf(14, &[5, -5], 7).unwrap();
213        assert_eq!(g.vcount(), 14);
214        assert_eq!(g.ecount(), 21);
215        for v in 0..14 {
216            assert_eq!(degree(&g, v), 3, "Heawood must be 3-regular at v={v}");
217        }
218    }
219
220    #[test]
221    fn truncated_tetrahedron_2_6_minus2_minus6_repeats_3() {
222        // Truncated tetrahedron: [2, 6, -2, -6]^3, n=12 → 18 edges, cubic.
223        let g = lcf(12, &[2, 6, -2, -6], 3).unwrap();
224        assert_eq!(g.vcount(), 12);
225        assert_eq!(g.ecount(), 18);
226        for v in 0..12 {
227            assert_eq!(degree(&g, v), 3);
228        }
229    }
230
231    #[test]
232    fn truncated_octahedron_3_minus7_7_minus3_repeats_6() {
233        // Truncated octahedron: [3, -7, 7, -3]^6 on n=24 → 36 edges, cubic.
234        let g = lcf(24, &[3, -7, 7, -3], 6).unwrap();
235        assert_eq!(g.vcount(), 24);
236        assert_eq!(g.ecount(), 36);
237        for v in 0..24 {
238            assert_eq!(degree(&g, v), 3);
239        }
240    }
241
242    #[test]
243    fn n1_yields_singleton_no_edges() {
244        let g = lcf(1, &[3, -5], 4).unwrap();
245        assert_eq!(g.vcount(), 1);
246        assert_eq!(g.ecount(), 0);
247    }
248
249    #[test]
250    fn always_undirected_no_self_loops() {
251        let g = lcf(10, &[3, -3], 5).unwrap();
252        assert!(!g.is_directed());
253        let m = u32::try_from(g.ecount()).expect("ecount fits u32");
254        for e in 0..m {
255            let (a, b) = g.edge(e).expect("edge in range");
256            assert_ne!(a, b, "no self-loops");
257        }
258    }
259
260    #[test]
261    fn always_simple_no_parallel_edges() {
262        let g = lcf(8, &[3, -2], 4).unwrap();
263        let edges = canonical_edges(&g);
264        let mut unique = edges.clone();
265        unique.dedup();
266        assert_eq!(edges.len(), unique.len(), "no parallel edges");
267    }
268
269    #[test]
270    fn frucht_graph_full_12_shift_pattern() {
271        // Frucht: [-5, -2, -4, 2, 5, -2, 2, 5, -2, -5, 4, 2]^1, n=12 →
272        // 18 edges, cubic. Asymmetric — the only 3-regular planar graph
273        // with no non-trivial automorphisms.
274        let g = lcf(12, &[-5, -2, -4, 2, 5, -2, 2, 5, -2, -5, 4, 2], 1).unwrap();
275        assert_eq!(g.vcount(), 12);
276        assert_eq!(g.ecount(), 18);
277        for v in 0..12 {
278            assert_eq!(degree(&g, v), 3, "Frucht must be 3-regular at v={v}");
279        }
280    }
281
282    #[test]
283    fn negative_shift_larger_than_n_wraps_correctly() {
284        // shift = -100 on n=10 vertices: from sptr=0 → to = (-100) mod 10 = 0.
285        // Self-loop at vertex 0 dropped. Subsequent sptrs each produce one
286        // chord per pass, and the construction should remain simple.
287        let g = lcf(10, &[-100, 100], 5).unwrap();
288        assert_eq!(g.vcount(), 10);
289        let edges = canonical_edges(&g);
290        let mut unique = edges.clone();
291        unique.dedup();
292        assert_eq!(edges.len(), unique.len(), "no parallels");
293        for (a, b) in &edges {
294            assert_ne!(a, b);
295        }
296    }
297}
298
299#[cfg(all(test, feature = "proptest-harness"))]
300mod proptest_tests {
301    use super::*;
302    use proptest::prelude::*;
303    use std::collections::BTreeSet;
304
305    fn arb_lcf_params() -> impl Strategy<Value = (u32, Vec<i64>, u32)> {
306        // n ∈ [0, 30], shifts of length ≤ 6 with values in [-30, 30],
307        // repeats ∈ [0, 4]. Wide enough to exercise wraparound, n=0/1/2
308        // edge cases, empty-shift and zero-repeat short-circuits, while
309        // keeping fixture sizes small.
310        (
311            0u32..=30,
312            prop::collection::vec(-30i64..=30, 0..=6),
313            0u32..=4,
314        )
315    }
316
317    proptest! {
318        #[test]
319        fn always_undirected_no_self_loops_no_parallels(
320            (n, shifts, repeats) in arb_lcf_params()
321        ) {
322            let g = lcf(n, &shifts, repeats).unwrap();
323            prop_assert!(!g.is_directed());
324            prop_assert_eq!(g.vcount(), n);
325
326            let m = u32::try_from(g.ecount()).unwrap();
327            let mut seen: BTreeSet<(u32, u32)> = BTreeSet::new();
328            for e in 0..m {
329                let (a, b) = g.edge(e).unwrap();
330                prop_assert_ne!(a, b, "self-loop survived simplify");
331                let canon = if a <= b { (a, b) } else { (b, a) };
332                prop_assert!(seen.insert(canon), "duplicate edge survived simplify");
333            }
334        }
335
336        #[test]
337        fn ecount_bounded_by_candidate_count(
338            (n, shifts, repeats) in arb_lcf_params()
339        ) {
340            // After simplify, ecount ≤ Hamilton-cycle edges + chord pass.
341            let g = lcf(n, &shifts, repeats).unwrap();
342            let backbone_edges = if n >= 2 { n as usize } else { 0 };
343            let chord_edges = (repeats as usize)
344                .checked_mul(shifts.len())
345                .unwrap_or(0);
346            prop_assert!(g.ecount() <= backbone_edges + chord_edges);
347        }
348
349        #[test]
350        fn pure_cycle_when_no_chords(n in 3u32..=30, shifts_empty in any::<bool>()) {
351            // shifts.is_empty() || repeats == 0 ⇒ result is C_n: n edges
352            // each forming the Hamilton ring, every vertex degree 2.
353            let shifts: Vec<i64> = if shifts_empty { vec![] } else { vec![5, -5] };
354            let repeats: u32 = if shifts_empty { 7 } else { 0 };
355            let g = lcf(n, &shifts, repeats).unwrap();
356            prop_assert_eq!(g.vcount(), n);
357            prop_assert_eq!(g.ecount(), n as usize);
358            for v in 0..n {
359                prop_assert_eq!(g.neighbors(v).unwrap().len(), 2);
360            }
361        }
362
363        #[test]
364        fn n_zero_yields_empty_regardless_of_pattern(
365            shifts in prop::collection::vec(-30i64..=30, 0..=6),
366            repeats in 0u32..=4,
367        ) {
368            let g = lcf(0, &shifts, repeats).unwrap();
369            prop_assert_eq!(g.vcount(), 0);
370            prop_assert_eq!(g.ecount(), 0);
371            prop_assert!(!g.is_directed());
372        }
373
374        #[test]
375        fn n_one_yields_singleton_regardless_of_pattern(
376            shifts in prop::collection::vec(-30i64..=30, 0..=6),
377            repeats in 0u32..=4,
378        ) {
379            // n=1: Hamilton step (0, 0) and every chord is a self-loop, all
380            // dropped by the simplify pass.
381            let g = lcf(1, &shifts, repeats).unwrap();
382            prop_assert_eq!(g.vcount(), 1);
383            prop_assert_eq!(g.ecount(), 0);
384        }
385
386        #[test]
387        fn matches_unrolled_shifts(
388            n in 3u32..=20,
389            shifts in prop::collection::vec(-15i64..=15, 1..=4),
390            repeats in 1u32..=3,
391        ) {
392            // lcf(n, [s0, s1, ..., sk-1], repeats) must be edge-equivalent to
393            // lcf(n, [s0, s1, ..., sk-1] repeated `repeats` times, 1).
394            let g_repeated = lcf(n, &shifts, repeats).unwrap();
395            let unrolled: Vec<i64> = (0..repeats)
396                .flat_map(|_| shifts.iter().copied())
397                .collect();
398            let g_unrolled = lcf(n, &unrolled, 1).unwrap();
399            prop_assert_eq!(g_repeated.ecount(), g_unrolled.ecount());
400
401            let collect_canon = |g: &Graph| -> BTreeSet<(u32, u32)> {
402                let m = u32::try_from(g.ecount()).unwrap();
403                (0..m)
404                    .map(|e| g.edge(e).unwrap())
405                    .map(|(a, b)| if a <= b { (a, b) } else { (b, a) })
406                    .collect()
407            };
408            prop_assert_eq!(collect_canon(&g_repeated), collect_canon(&g_unrolled));
409        }
410
411        #[test]
412        fn maximum_degree_bounded(
413            (n, shifts, repeats) in arb_lcf_params()
414        ) {
415            // Every vertex appears on the Hamilton cycle (+2 degree once
416            // n ≥ 3) and as `from` exactly `chord_count.div_ceil(n)` times
417            // plus the `to`-side mirror. Hard upper bound: 2 (backbone)
418            // + 2 * chord_count / n (rounded up). Looser but cheap check.
419            let g = lcf(n, &shifts, repeats).unwrap();
420            if n == 0 {
421                return Ok(());
422            }
423            let chord_count = (repeats as usize) * shifts.len();
424            let max_deg = 2usize.saturating_add(2 * chord_count);
425            for v in 0..n {
426                prop_assert!(g.neighbors(v).unwrap().len() <= max_deg);
427            }
428        }
429    }
430}
rust_igraph/algorithms/constructors/lcf.rs

rust_igraph/algorithms/constructors/
lcf.rs
