rust_igraph/algorithms/constructors/
turan.rs

1//! Turán graph constructor (ALGO-CN-027).
2//!
3//! Counterpart of `igraph_turan()` in
4//! `references/igraph/src/constructors/full.c:281-325`.
5//!
6//! The *Turán graph* `T(n, r)` is the complete `r`-partite graph on `n`
7//! vertices whose partition sizes differ by at most one — i.e. the
8//! densest graph on `n` vertices that does not contain a clique of size
9//! `r + 1` (Turán's theorem, 1941). Concretely:
10//!
11//! * Let `q = n / r` and `s = n % r`.
12//! * The first `s` partitions get size `q + 1`; the remaining `r − s`
13//!   partitions get size `q`.
14//! * The result is `full_multipartite(&[q+1; s] ++ &[q; r-s], false,
15//!   MultipartiteMode::All)`.
16//!
17//! Turán graphs are always undirected. The result bundles the graph
18//! with a `types` vector recording the partition index of every vertex
19//! (partition-major order).
20//!
21//! Degenerate cases (matching upstream):
22//!
23//! * `n == 0` → empty graph with empty `types`. The `r` argument is
24//!   ignored.
25//! * `r > n` → silently capped to `r = n`, yielding `n` singleton
26//!   partitions (i.e. the complete graph `K_n` with `types = [0, 1, …,
27//!   n − 1]`).
28//! * `r == 0` → [`IgraphError::InvalidArgument`] (the partition count
29//!   must be positive when `n > 0`).
30//!
31//! Time complexity: `O(|V| + |E|)`, dominated by the wrapped
32//! [`full_multipartite`] call.
33
34use crate::algorithms::constructors::full_multipartite::{
35    FullMultipartite, MultipartiteMode, full_multipartite,
36};
37use crate::core::{IgraphError, IgraphResult};
38
39/// Build the Turán graph `T(n, r)`.
40///
41/// `n` is the vertex count; `r` is the partition count. Returns a
42/// [`FullMultipartite`] whose `graph` is the complete `r'`-partite
43/// graph with maximally balanced partition sizes (where
44/// `r' = min(r, n)`) and whose `types` records the partition index of
45/// every vertex.
46///
47/// See the module documentation for the precise semantics and
48/// degenerate-case handling.
49///
50/// # Errors
51///
52/// * [`IgraphError::InvalidArgument`] — `r == 0` while `n > 0`. The
53///   upstream C entry returns `IGRAPH_EINVAL` in this case and we
54///   preserve that contract.
55/// * Any [`IgraphError`] surfaced by the underlying
56///   [`full_multipartite`] call (overflow when the resulting graph
57///   would have more than `u32::MAX` vertices or more than
58///   `usize::MAX` edges).
59///
60/// # Examples
61///
62/// ```
63/// use rust_igraph::turan;
64///
65/// // T(6, 3) — three balanced partitions of size 2, the cocktail-party
66/// // graph K_{2,2,2} a.k.a. the octahedron.
67/// let r = turan(6, 3).unwrap();
68/// assert_eq!(r.graph.vcount(), 6);
69/// assert_eq!(r.graph.ecount(), 12);
70/// assert_eq!(r.types, vec![0, 0, 1, 1, 2, 2]);
71///
72/// // r > n → capped at r = n, yielding K_4.
73/// let r = turan(4, 6).unwrap();
74/// assert_eq!(r.graph.vcount(), 4);
75/// assert_eq!(r.graph.ecount(), 6);
76/// assert_eq!(r.types, vec![0, 1, 2, 3]);
77///
78/// // n == 0 → empty graph regardless of r.
79/// let r = turan(0, 10).unwrap();
80/// assert_eq!(r.graph.vcount(), 0);
81/// assert!(r.types.is_empty());
82/// ```
83pub fn turan(n: u32, r: u32) -> IgraphResult<FullMultipartite> {
84    if n == 0 {
85        return full_multipartite(&[], false, MultipartiteMode::All);
86    }
87
88    if r == 0 {
89        return Err(IgraphError::InvalidArgument(
90            "turan: number of partitions must be positive when n > 0".into(),
91        ));
92    }
93
94    let r_effective = r.min(n);
95    let quotient = n / r_effective;
96    let remainder = n % r_effective;
97
98    // The first `remainder` partitions get one extra vertex (size
99    // `quotient + 1`); the remaining `r_effective − remainder`
100    // partitions get exactly `quotient`. Matches upstream's
101    // `igraph_vector_int_fill(quotient)` + per-index `++` loop.
102    let mut partitions: Vec<u32> = Vec::with_capacity(r_effective as usize);
103    let big = quotient.checked_add(1).ok_or_else(|| {
104        IgraphError::InvalidArgument("turan: partition size n/r + 1 overflows u32".into())
105    })?;
106    for i in 0..r_effective {
107        if i < remainder {
108            partitions.push(big);
109        } else {
110            partitions.push(quotient);
111        }
112    }
113
114    full_multipartite(&partitions, false, MultipartiteMode::All)
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120    use std::collections::BTreeSet;
121
122    fn canonical_edges(g: &crate::core::Graph) -> BTreeSet<(u32, u32)> {
123        let m = u32::try_from(g.ecount()).expect("ecount fits u32");
124        (0..m)
125            .map(|e| g.edge(e).expect("edge id in bounds"))
126            .map(|(u, v)| if u <= v { (u, v) } else { (v, u) })
127            .collect()
128    }
129
130    #[test]
131    fn empty_n_zero_returns_empty_graph() {
132        // Upstream `.out` test 1: igraph_turan(0, 10).
133        let r = turan(0, 10).expect("ok");
134        assert_eq!(r.graph.vcount(), 0);
135        assert_eq!(r.graph.ecount(), 0);
136        assert!(!r.graph.is_directed());
137        assert!(r.types.is_empty());
138    }
139
140    #[test]
141    fn empty_n_zero_with_r_one_also_empty() {
142        // Edge: n == 0 should ignore r entirely, even r == 1.
143        let r = turan(0, 1).expect("ok");
144        assert_eq!(r.graph.vcount(), 0);
145        assert!(r.types.is_empty());
146    }
147
148    #[test]
149    fn empty_n_zero_with_r_zero_still_empty_no_error() {
150        // n == 0 short-circuits before the r == 0 check, matching
151        // upstream's `if (n == 0)` early-return.
152        let r = turan(0, 0).expect("ok");
153        assert_eq!(r.graph.vcount(), 0);
154        assert!(r.types.is_empty());
155    }
156
157    #[test]
158    fn r_zero_with_positive_n_is_error() {
159        let err = turan(5, 0).expect_err("must reject r == 0 when n > 0");
160        match err {
161            IgraphError::InvalidArgument(_) => {}
162            other => panic!("expected InvalidArgument, got {other:?}"),
163        }
164    }
165
166    #[test]
167    fn r_eq_one_is_n_isolated_vertices() {
168        // Upstream `.out` test 2: igraph_turan(10, 1).
169        let r = turan(10, 1).expect("ok");
170        assert_eq!(r.graph.vcount(), 10);
171        assert_eq!(r.graph.ecount(), 0);
172        assert_eq!(r.types, vec![0; 10]);
173    }
174
175    #[test]
176    fn r_exceeds_n_caps_at_n_yielding_kn() {
177        // Upstream `.out` test 3: igraph_turan(4, 6) → 4 vertices, 1 partition each.
178        let r = turan(4, 6).expect("ok");
179        assert_eq!(r.graph.vcount(), 4);
180        assert_eq!(r.graph.ecount(), 6);
181        assert_eq!(r.types, vec![0, 1, 2, 3]);
182        // The full K_4 edge set.
183        let expected: BTreeSet<(u32, u32)> = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
184            .into_iter()
185            .collect();
186        assert_eq!(canonical_edges(&r.graph), expected);
187    }
188
189    #[test]
190    fn turan_13_4_matches_upstream() {
191        // Upstream `.out` test 4: igraph_turan(13, 4) — quotient 3,
192        // remainder 1 → partitions [4, 3, 3, 3]. types is exactly the
193        // .out line `0 0 0 0 1 1 1 2 2 2 3 3 3`.
194        let r = turan(13, 4).expect("ok");
195        assert_eq!(r.graph.vcount(), 13);
196        // E = ½ · (4·9 + 3·10 + 3·10 + 3·10) = ½ · 126 = 63.
197        assert_eq!(r.graph.ecount(), 63);
198        assert_eq!(r.types, vec![0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3]);
199    }
200
201    #[test]
202    fn turan_13_4_ecount_matches_closed_form() {
203        // E = ½ · Σ_i n_i · (N − n_i). N=13, sizes [4,3,3,3]:
204        //   ½ · (4·9 + 3·10 + 3·10 + 3·10) = ½ · (36 + 30 + 30 + 30) = ½ · 126 = 63.
205        let r = turan(13, 4).expect("ok");
206        let n: u32 = 13;
207        let sizes: [u32; 4] = [4, 3, 3, 3];
208        let twice_e: u32 = sizes.iter().map(|&s| s * (n - s)).sum();
209        let expected_e = (twice_e / 2) as usize;
210        assert_eq!(r.graph.ecount(), expected_e);
211    }
212
213    #[test]
214    fn turan_8_3_matches_upstream() {
215        // Upstream `.out` test 5: igraph_turan(8, 3) — quotient 2,
216        // remainder 2 → partitions [3, 3, 2]. types is exactly the
217        // .out line `0 0 0 1 1 1 2 2`.
218        let r = turan(8, 3).expect("ok");
219        assert_eq!(r.graph.vcount(), 8);
220        assert_eq!(r.types, vec![0, 0, 0, 1, 1, 1, 2, 2]);
221        // E = ½ · (3·5 + 3·5 + 2·6) = ½ · 42 = 21.
222        assert_eq!(r.graph.ecount(), 21);
223    }
224
225    #[test]
226    fn turan_6_3_matches_upstream() {
227        // Upstream `.out` test 6: igraph_turan(6, 3) — quotient 2,
228        // remainder 0 → partitions [2, 2, 2]. The octahedron / cocktail
229        // party graph K_{2,2,2}.
230        let r = turan(6, 3).expect("ok");
231        assert_eq!(r.graph.vcount(), 6);
232        assert_eq!(r.graph.ecount(), 12);
233        assert_eq!(r.types, vec![0, 0, 1, 1, 2, 2]);
234    }
235
236    #[test]
237    fn turan_balanced_when_remainder_zero() {
238        // n divisible by r → all partitions equal size.
239        let r = turan(12, 4).expect("ok");
240        assert_eq!(r.graph.vcount(), 12);
241        // partitions = [3, 3, 3, 3]; E = ½ · Σ 3·9 = ½ · 108 = 54.
242        assert_eq!(r.graph.ecount(), 54);
243        assert_eq!(r.types, vec![0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3]);
244    }
245
246    #[test]
247    fn turan_first_partitions_get_the_extras_when_remainder_nonzero() {
248        // n=14, r=4 → q=3, s=2 → partitions [4, 4, 3, 3].
249        let r = turan(14, 4).expect("ok");
250        assert_eq!(r.graph.vcount(), 14);
251        // First two partitions size 4, next two size 3.
252        assert_eq!(r.types, vec![0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3]);
253    }
254
255    #[test]
256    fn turan_no_self_loops_no_intra_partition_edges() {
257        let r = turan(15, 5).expect("ok");
258        for (u, v) in canonical_edges(&r.graph) {
259            assert_ne!(u, v, "no self-loops");
260            assert_ne!(
261                r.types[u as usize], r.types[v as usize],
262                "edge ({u}, {v}) lives inside a single partition"
263            );
264        }
265    }
266
267    #[test]
268    fn turan_is_always_undirected() {
269        for (n, r) in [(0, 1), (5, 3), (10, 4), (20, 7)] {
270            let res = turan(n, r).expect("ok");
271            assert!(!res.graph.is_directed(), "T({n}, {r}) must be undirected");
272        }
273    }
274
275    #[test]
276    fn turan_isomorphic_to_full_multipartite_balanced() {
277        // From upstream test: turan(13, 4) is isomorphic to
278        // full_multipartite([4, 3, 3, 3]). Compare canonical edge
279        // multisets — emission order should already match since we
280        // share the underlying implementation.
281        let t = turan(13, 4).expect("ok");
282        let mp = full_multipartite(&[4, 3, 3, 3], false, MultipartiteMode::All).expect("ok");
283        assert_eq!(t.graph.vcount(), mp.graph.vcount());
284        assert_eq!(t.graph.ecount(), mp.graph.ecount());
285        assert_eq!(t.types, mp.types);
286        assert_eq!(canonical_edges(&t.graph), canonical_edges(&mp.graph));
287    }
288}
289
290#[cfg(all(test, feature = "proptest-harness"))]
291mod proptest_invariants {
292    use super::*;
293    use proptest::prelude::*;
294
295    proptest! {
296        #![proptest_config(ProptestConfig::with_cases(64))]
297
298        #[test]
299        fn vcount_always_equals_n(n in 0u32..30, r in 1u32..10) {
300            let res = turan(n, r).expect("ok for valid inputs");
301            prop_assert_eq!(res.graph.vcount(), n);
302            prop_assert_eq!(u32::try_from(res.types.len()).unwrap(), n);
303        }
304
305        #[test]
306        fn always_undirected(n in 0u32..30, r in 1u32..10) {
307            let res = turan(n, r).expect("ok");
308            prop_assert!(!res.graph.is_directed());
309        }
310
311        #[test]
312        fn types_partition_major_monotone(n in 1u32..30, r in 1u32..10) {
313            let res = turan(n, r).expect("ok");
314            for w in res.types.windows(2) {
315                prop_assert!(w[0] <= w[1]);
316            }
317        }
318
319        #[test]
320        fn partition_size_differs_by_at_most_one(n in 1u32..30, r in 1u32..10) {
321            let res = turan(n, r).expect("ok");
322            // Count vertices per partition by scanning types.
323            let max_t = *res.types.iter().max().unwrap();
324            let mut sizes = vec![0u32; (max_t + 1) as usize];
325            for &t in &res.types {
326                sizes[t as usize] += 1;
327            }
328            let lo = *sizes.iter().min().unwrap();
329            let hi = *sizes.iter().max().unwrap();
330            prop_assert!(hi - lo <= 1, "partition sizes must differ by ≤ 1: {sizes:?}");
331        }
332
333        #[test]
334        fn no_intra_partition_edges(n in 0u32..20, r in 1u32..8) {
335            let res = turan(n, r).expect("ok");
336            let m = u32::try_from(res.graph.ecount()).unwrap();
337            for e in 0..m {
338                let (u, v) = res.graph.edge(e).unwrap();
339                prop_assert_ne!(res.types[u as usize], res.types[v as usize]);
340            }
341        }
342
343        #[test]
344        fn r_capped_at_n_when_oversized(n in 1u32..15, extra in 0u32..20) {
345            // T(n, n + extra) should equal T(n, n).
346            let big = turan(n, n + extra).expect("ok");
347            let cap = turan(n, n).expect("ok");
348            prop_assert_eq!(big.graph.vcount(), cap.graph.vcount());
349            prop_assert_eq!(big.graph.ecount(), cap.graph.ecount());
350            prop_assert_eq!(big.types, cap.types);
351        }
352    }
353}
rust_igraph/algorithms/constructors/turan.rs

rust_igraph/algorithms/constructors/
turan.rs
