rust_igraph/algorithms/properties/
cut_metrics.rs

1//! Graph cut quality metrics (ALGO-TR-018).
2//!
3//! Given a graph and a vertex partition (membership vector), compute
4//! standard cut quality metrics used in spectral clustering evaluation
5//! and community detection:
6//!
7//! - **Cut size**: number of edges (or sum of weights) crossing between
8//!   different partitions.
9//! - **Normalized cut (`NCut`)**: `Σ_k cut(S_k, V\S_k) / vol(S_k)` where
10//!   `vol(S)` is the sum of degrees in `S`. (Shi & Malik, 2000)
11//! - **Ratio cut**: `Σ_k cut(S_k, V\S_k) / |S_k|`. (Hagen & Kahng, 1992)
12//! - **Conductance**: For a 2-way partition, `cut(S, V\S) / min(vol(S), vol(V\S))`.
13//!   For k-way, the minimum conductance over all clusters.
14//! - **Expansion**: `cut(S, V\S) / min(|S|, |V\S|)` (isoperimetric number).
15
16#![allow(clippy::cast_possible_truncation, clippy::cast_precision_loss)]
17
18use crate::core::{Graph, IgraphError, IgraphResult};
19
20/// Compute the cut size of a partition.
21///
22/// Counts the number of edges (or sum of edge weights) that cross between
23/// different clusters.
24///
25/// # Parameters
26///
27/// - `graph` — The input graph.
28/// - `membership` — Cluster assignment for each vertex (`membership[v]` is the
29///   cluster id of vertex `v`). Length must equal `vcount`.
30/// - `weights` — Optional edge weights. If `None`, each edge has weight 1.
31///
32/// # Examples
33///
34/// ```
35/// use rust_igraph::{Graph, cut_size};
36///
37/// let g = Graph::from_edges(&[(0,1),(1,2),(2,3)], false, Some(4)).unwrap();
38/// // Partition: {0,1} vs {2,3}
39/// let membership = vec![0u32, 0, 1, 1];
40/// let cs = cut_size(&g, &membership, None).unwrap();
41/// assert!((cs - 1.0).abs() < 1e-10); // only edge 1-2 crosses
42/// ```
43pub fn cut_size(graph: &Graph, membership: &[u32], weights: Option<&[f64]>) -> IgraphResult<f64> {
44    let nv = graph.vcount() as usize;
45    let ne = graph.ecount();
46
47    if membership.len() != nv {
48        return Err(IgraphError::InvalidArgument(format!(
49            "membership length {} does not match vcount {nv}",
50            membership.len()
51        )));
52    }
53
54    if let Some(w) = weights {
55        if w.len() != ne {
56            return Err(IgraphError::InvalidArgument(format!(
57                "weights length {} does not match ecount {ne}",
58                w.len()
59            )));
60        }
61    }
62
63    let mut total_cut = 0.0_f64;
64    for (eid, (u, v)) in graph.edges().enumerate() {
65        if membership[u as usize] != membership[v as usize] {
66            let w = weights.map_or(1.0, |ws| ws[eid]);
67            total_cut += w;
68        }
69    }
70
71    Ok(total_cut)
72}
73
74/// Compute the normalized cut (`NCut`) of a partition.
75///
76/// `NCut = Σ_k cut(S_k, V\S_k) / vol(S_k)`
77///
78/// where `vol(S_k)` is the sum of (weighted) degrees of vertices in cluster `k`.
79/// Lower values indicate better balanced cuts.
80///
81/// # Examples
82///
83/// ```
84/// use rust_igraph::{Graph, normalized_cut};
85///
86/// let g = Graph::from_edges(
87///     &[(0,1),(1,2),(2,3),(3,0)], false, Some(4)
88/// ).unwrap();
89/// // Balanced partition: {0,1} vs {2,3}
90/// let membership = vec![0u32, 0, 1, 1];
91/// let nc = normalized_cut(&g, &membership, None).unwrap();
92/// assert!(nc > 0.0);
93/// ```
94pub fn normalized_cut(
95    graph: &Graph,
96    membership: &[u32],
97    weights: Option<&[f64]>,
98) -> IgraphResult<f64> {
99    let nv = graph.vcount() as usize;
100    let ne = graph.ecount();
101
102    if membership.len() != nv {
103        return Err(IgraphError::InvalidArgument(format!(
104            "membership length {} does not match vcount {nv}",
105            membership.len()
106        )));
107    }
108
109    if let Some(w) = weights {
110        if w.len() != ne {
111            return Err(IgraphError::InvalidArgument(format!(
112                "weights length {} does not match ecount {ne}",
113                w.len()
114            )));
115        }
116    }
117
118    let k = partition_count(membership);
119    if k == 0 {
120        return Ok(0.0);
121    }
122
123    // Compute volume of each cluster (sum of weighted degrees)
124    let mut vol = vec![0.0_f64; k];
125    let mut cut_per_cluster = vec![0.0_f64; k];
126
127    for (eid, (u, v)) in graph.edges().enumerate() {
128        let w = weights.map_or(1.0, |ws| ws[eid]);
129        let cu = membership[u as usize] as usize;
130        let cv = membership[v as usize] as usize;
131
132        // Each edge contributes to the volume of its endpoints' clusters
133        vol[cu] += w;
134        vol[cv] += w;
135
136        if cu != cv {
137            cut_per_cluster[cu] += w;
138            cut_per_cluster[cv] += w;
139        }
140    }
141
142    let mut ncut = 0.0_f64;
143    for c in 0..k {
144        if vol[c] > 0.0 {
145            ncut += cut_per_cluster[c] / vol[c];
146        }
147    }
148
149    Ok(ncut)
150}
151
152/// Compute the ratio cut of a partition.
153///
154/// `RatioCut = Σ_k cut(S_k, V\S_k) / |S_k|`
155///
156/// where `|S_k|` is the number of vertices in cluster `k`.
157/// Lower values indicate better balanced cuts.
158///
159/// # Examples
160///
161/// ```
162/// use rust_igraph::{Graph, ratio_cut};
163///
164/// let g = Graph::from_edges(
165///     &[(0,1),(1,2),(2,3),(3,0)], false, Some(4)
166/// ).unwrap();
167/// let membership = vec![0u32, 0, 1, 1];
168/// let rc = ratio_cut(&g, &membership, None).unwrap();
169/// assert!(rc > 0.0);
170/// ```
171pub fn ratio_cut(graph: &Graph, membership: &[u32], weights: Option<&[f64]>) -> IgraphResult<f64> {
172    let nv = graph.vcount() as usize;
173    let ne = graph.ecount();
174
175    if membership.len() != nv {
176        return Err(IgraphError::InvalidArgument(format!(
177            "membership length {} does not match vcount {nv}",
178            membership.len()
179        )));
180    }
181
182    if let Some(w) = weights {
183        if w.len() != ne {
184            return Err(IgraphError::InvalidArgument(format!(
185                "weights length {} does not match ecount {ne}",
186                w.len()
187            )));
188        }
189    }
190
191    let k = partition_count(membership);
192    if k == 0 {
193        return Ok(0.0);
194    }
195
196    let mut sizes = vec![0usize; k];
197    for &c in membership {
198        sizes[c as usize] += 1;
199    }
200
201    let mut cut_per_cluster = vec![0.0_f64; k];
202    for (eid, (u, v)) in graph.edges().enumerate() {
203        let w = weights.map_or(1.0, |ws| ws[eid]);
204        let cu = membership[u as usize] as usize;
205        let cv = membership[v as usize] as usize;
206
207        if cu != cv {
208            cut_per_cluster[cu] += w;
209            cut_per_cluster[cv] += w;
210        }
211    }
212
213    let mut rcut = 0.0_f64;
214    for c in 0..k {
215        if sizes[c] > 0 {
216            rcut += cut_per_cluster[c] / sizes[c] as f64;
217        }
218    }
219
220    Ok(rcut)
221}
222
223/// Compute the conductance of a partition.
224///
225/// For a 2-way partition: `cut(S, V\S) / min(vol(S), vol(V\S))`.
226/// For k-way: the maximum conductance (worst cluster), defined as
227/// `max_k cut(S_k, V\S_k) / vol(S_k)` over clusters with `vol > 0`.
228///
229/// Lower conductance means better separation.
230///
231/// # Examples
232///
233/// ```
234/// use rust_igraph::{Graph, conductance};
235///
236/// let g = Graph::from_edges(
237///     &[(0,1),(1,2),(2,3),(3,0),(0,2)], false, Some(4)
238/// ).unwrap();
239/// let membership = vec![0u32, 0, 1, 1];
240/// let c = conductance(&g, &membership, None).unwrap();
241/// assert!(c > 0.0 && c <= 1.0);
242/// ```
243pub fn conductance(
244    graph: &Graph,
245    membership: &[u32],
246    weights: Option<&[f64]>,
247) -> IgraphResult<f64> {
248    let nv = graph.vcount() as usize;
249    let ne = graph.ecount();
250
251    if membership.len() != nv {
252        return Err(IgraphError::InvalidArgument(format!(
253            "membership length {} does not match vcount {nv}",
254            membership.len()
255        )));
256    }
257
258    if let Some(w) = weights {
259        if w.len() != ne {
260            return Err(IgraphError::InvalidArgument(format!(
261                "weights length {} does not match ecount {ne}",
262                w.len()
263            )));
264        }
265    }
266
267    let k = partition_count(membership);
268    if k == 0 {
269        return Ok(0.0);
270    }
271
272    let mut vol = vec![0.0_f64; k];
273    let mut cut_per_cluster = vec![0.0_f64; k];
274
275    for (eid, (u, v)) in graph.edges().enumerate() {
276        let w = weights.map_or(1.0, |ws| ws[eid]);
277        let cu = membership[u as usize] as usize;
278        let cv = membership[v as usize] as usize;
279
280        vol[cu] += w;
281        vol[cv] += w;
282
283        if cu != cv {
284            cut_per_cluster[cu] += w;
285            cut_per_cluster[cv] += w;
286        }
287    }
288
289    // For 2-way partition, use the standard definition
290    if k == 2 {
291        let total_cut = cut_per_cluster[0]; // same as cut_per_cluster[1]
292        let min_vol = vol[0].min(vol[1]);
293        if min_vol > 0.0 {
294            return Ok(total_cut / min_vol);
295        }
296        return Ok(0.0);
297    }
298
299    // For k-way, return max conductance over all clusters
300    let mut max_cond = 0.0_f64;
301    for c in 0..k {
302        if vol[c] > 0.0 {
303            let cond = cut_per_cluster[c] / vol[c];
304            if cond > max_cond {
305                max_cond = cond;
306            }
307        }
308    }
309
310    Ok(max_cond)
311}
312
313/// Compute the expansion (isoperimetric number) of a partition.
314///
315/// For a 2-way partition: `cut(S, V\S) / min(|S|, |V\S|)`.
316/// For k-way: the maximum expansion over all clusters.
317///
318/// # Examples
319///
320/// ```
321/// use rust_igraph::{Graph, expansion};
322///
323/// let g = Graph::from_edges(
324///     &[(0,1),(1,2),(2,3),(3,0)], false, Some(4)
325/// ).unwrap();
326/// let membership = vec![0u32, 0, 1, 1];
327/// let e = expansion(&g, &membership, None).unwrap();
328/// assert!(e > 0.0);
329/// ```
330pub fn expansion(graph: &Graph, membership: &[u32], weights: Option<&[f64]>) -> IgraphResult<f64> {
331    let nv = graph.vcount() as usize;
332    let ne = graph.ecount();
333
334    if membership.len() != nv {
335        return Err(IgraphError::InvalidArgument(format!(
336            "membership length {} does not match vcount {nv}",
337            membership.len()
338        )));
339    }
340
341    if let Some(w) = weights {
342        if w.len() != ne {
343            return Err(IgraphError::InvalidArgument(format!(
344                "weights length {} does not match ecount {ne}",
345                w.len()
346            )));
347        }
348    }
349
350    let k = partition_count(membership);
351    if k == 0 {
352        return Ok(0.0);
353    }
354
355    let mut sizes = vec![0usize; k];
356    for &c in membership {
357        sizes[c as usize] += 1;
358    }
359
360    let mut cut_per_cluster = vec![0.0_f64; k];
361    for (eid, (u, v)) in graph.edges().enumerate() {
362        let w = weights.map_or(1.0, |ws| ws[eid]);
363        let cu = membership[u as usize] as usize;
364        let cv = membership[v as usize] as usize;
365
366        if cu != cv {
367            cut_per_cluster[cu] += w;
368            cut_per_cluster[cv] += w;
369        }
370    }
371
372    if k == 2 {
373        let total_cut = cut_per_cluster[0];
374        let min_size = sizes[0].min(sizes[1]);
375        if min_size > 0 {
376            return Ok(total_cut / min_size as f64);
377        }
378        return Ok(0.0);
379    }
380
381    let mut max_exp = 0.0_f64;
382    for c in 0..k {
383        if sizes[c] > 0 {
384            let exp_c = cut_per_cluster[c] / sizes[c] as f64;
385            if exp_c > max_exp {
386                max_exp = exp_c;
387            }
388        }
389    }
390
391    Ok(max_exp)
392}
393
394// --- Internal helpers ---
395
396fn partition_count(membership: &[u32]) -> usize {
397    if membership.is_empty() {
398        return 0;
399    }
400    membership
401        .iter()
402        .copied()
403        .max()
404        .map_or(0, |m| m as usize + 1)
405}
406
407#[cfg(test)]
408mod tests {
409    use super::*;
410
411    fn path4() -> Graph {
412        Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false, Some(4)).unwrap()
413    }
414
415    fn cycle4() -> Graph {
416        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, Some(4)).unwrap()
417    }
418
419    fn complete4() -> Graph {
420        Graph::from_edges(
421            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
422            false,
423            Some(4),
424        )
425        .unwrap()
426    }
427
428    // --- cut_size tests ---
429
430    #[test]
431    fn cut_size_path_balanced() {
432        let g = path4();
433        let m = vec![0u32, 0, 1, 1];
434        let cs = cut_size(&g, &m, None).unwrap();
435        assert!((cs - 1.0).abs() < 1e-10);
436    }
437
438    #[test]
439    fn cut_size_all_same_cluster() {
440        let g = cycle4();
441        let m = vec![0u32, 0, 0, 0];
442        let cs = cut_size(&g, &m, None).unwrap();
443        assert!(cs.abs() < 1e-10);
444    }
445
446    #[test]
447    fn cut_size_all_different() {
448        let g = cycle4();
449        let m = vec![0u32, 1, 2, 3];
450        let cs = cut_size(&g, &m, None).unwrap();
451        assert!((cs - 4.0).abs() < 1e-10);
452    }
453
454    #[test]
455    fn cut_size_weighted() {
456        let g = path4();
457        let m = vec![0u32, 0, 1, 1];
458        let w = vec![1.0, 3.0, 1.0]; // edge 1-2 has weight 3
459        let cs = cut_size(&g, &m, Some(&w)).unwrap();
460        assert!((cs - 3.0).abs() < 1e-10);
461    }
462
463    #[test]
464    fn cut_size_empty_graph() {
465        let g = Graph::with_vertices(3);
466        let m = vec![0u32, 1, 2];
467        let cs = cut_size(&g, &m, None).unwrap();
468        assert!(cs.abs() < 1e-10);
469    }
470
471    #[test]
472    fn cut_size_invalid_membership() {
473        let g = path4();
474        let m = vec![0u32, 1]; // too short
475        assert!(cut_size(&g, &m, None).is_err());
476    }
477
478    #[test]
479    fn cut_size_invalid_weights() {
480        let g = path4();
481        let m = vec![0u32, 0, 1, 1];
482        let w = vec![1.0]; // too short
483        assert!(cut_size(&g, &m, Some(&w)).is_err());
484    }
485
486    // --- normalized_cut tests ---
487
488    #[test]
489    fn ncut_cycle_balanced() {
490        let g = cycle4();
491        let m = vec![0u32, 0, 1, 1];
492        let nc = normalized_cut(&g, &m, None).unwrap();
493        // cut(S0, S1) = 2 (edges 1-2 and 3-0)
494        // vol(S0) = deg(0)+deg(1) = 2+2 = 4
495        // vol(S1) = deg(2)+deg(3) = 2+2 = 4
496        // NCut = 2/4 + 2/4 = 1.0
497        assert!((nc - 1.0).abs() < 1e-10);
498    }
499
500    #[test]
501    fn ncut_all_same_cluster() {
502        let g = cycle4();
503        let m = vec![0u32, 0, 0, 0];
504        let nc = normalized_cut(&g, &m, None).unwrap();
505        assert!(nc.abs() < 1e-10);
506    }
507
508    #[test]
509    fn ncut_complete_balanced() {
510        let g = complete4();
511        let m = vec![0u32, 0, 1, 1];
512        let nc = normalized_cut(&g, &m, None).unwrap();
513        // cut edges: 0-2, 0-3, 1-2, 1-3 = 4
514        // vol(S0) = 3+3 = 6, vol(S1) = 3+3 = 6
515        // NCut = 4/6 + 4/6 = 8/6 = 4/3
516        assert!((nc - 4.0 / 3.0).abs() < 1e-10);
517    }
518
519    // --- ratio_cut tests ---
520
521    #[test]
522    fn rcut_cycle_balanced() {
523        let g = cycle4();
524        let m = vec![0u32, 0, 1, 1];
525        let rc = ratio_cut(&g, &m, None).unwrap();
526        // cut = 2, |S0| = 2, |S1| = 2
527        // RatioCut = 2/2 + 2/2 = 2.0
528        assert!((rc - 2.0).abs() < 1e-10);
529    }
530
531    #[test]
532    fn rcut_all_same_cluster() {
533        let g = cycle4();
534        let m = vec![0u32, 0, 0, 0];
535        let rc = ratio_cut(&g, &m, None).unwrap();
536        assert!(rc.abs() < 1e-10);
537    }
538
539    #[test]
540    fn rcut_path_unbalanced() {
541        let g = path4();
542        let m = vec![0u32, 0, 0, 1]; // {0,1,2} vs {3}
543        let rc = ratio_cut(&g, &m, None).unwrap();
544        // cut = 1 (edge 2-3), |S0| = 3, |S1| = 1
545        // RatioCut = 1/3 + 1/1 = 4/3
546        assert!((rc - 4.0 / 3.0).abs() < 1e-10);
547    }
548
549    // --- conductance tests ---
550
551    #[test]
552    fn conductance_cycle_balanced() {
553        let g = cycle4();
554        let m = vec![0u32, 0, 1, 1];
555        let c = conductance(&g, &m, None).unwrap();
556        // cut = 2, vol(S0) = 4, vol(S1) = 4
557        // conductance = 2 / min(4, 4) = 0.5
558        assert!((c - 0.5).abs() < 1e-10);
559    }
560
561    #[test]
562    fn conductance_all_same() {
563        let g = cycle4();
564        let m = vec![0u32, 0, 0, 0];
565        let c = conductance(&g, &m, None).unwrap();
566        assert!(c.abs() < 1e-10);
567    }
568
569    #[test]
570    fn conductance_bounded() {
571        let g = complete4();
572        let m = vec![0u32, 0, 1, 1];
573        let c = conductance(&g, &m, None).unwrap();
574        assert!(c >= 0.0);
575        assert!(c <= 1.0);
576    }
577
578    // --- expansion tests ---
579
580    #[test]
581    fn expansion_cycle_balanced() {
582        let g = cycle4();
583        let m = vec![0u32, 0, 1, 1];
584        let e = expansion(&g, &m, None).unwrap();
585        // cut = 2, min(|S0|, |S1|) = min(2, 2) = 2
586        // expansion = 2/2 = 1.0
587        assert!((e - 1.0).abs() < 1e-10);
588    }
589
590    #[test]
591    fn expansion_path_unbalanced() {
592        let g = path4();
593        let m = vec![0u32, 0, 0, 1];
594        let e = expansion(&g, &m, None).unwrap();
595        // cut = 1, min(3, 1) = 1
596        // expansion = 1/1 = 1.0
597        assert!((e - 1.0).abs() < 1e-10);
598    }
599
600    #[test]
601    fn expansion_all_same() {
602        let g = cycle4();
603        let m = vec![0u32, 0, 0, 0];
604        let e = expansion(&g, &m, None).unwrap();
605        assert!(e.abs() < 1e-10);
606    }
607
608    // --- directed graph tests ---
609
610    #[test]
611    fn cut_size_directed() {
612        let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], true, Some(3)).unwrap();
613        let m = vec![0u32, 0, 1];
614        let cs = cut_size(&g, &m, None).unwrap();
615        // Edges crossing: 1→2 and 2→0 = 2
616        assert!((cs - 2.0).abs() < 1e-10);
617    }
618
619    // --- empty graph tests ---
620
621    #[test]
622    fn metrics_on_empty_partition() {
623        let g = Graph::with_vertices(0);
624        let m: Vec<u32> = vec![];
625        assert!((cut_size(&g, &m, None).unwrap()).abs() < 1e-10);
626        assert!((normalized_cut(&g, &m, None).unwrap()).abs() < 1e-10);
627        assert!((ratio_cut(&g, &m, None).unwrap()).abs() < 1e-10);
628        assert!((conductance(&g, &m, None).unwrap()).abs() < 1e-10);
629        assert!((expansion(&g, &m, None).unwrap()).abs() < 1e-10);
630    }
631}
rust_igraph/algorithms/properties/cut_metrics.rs

rust_igraph/algorithms/properties/
cut_metrics.rs
