rust_igraph/algorithms/properties/
is_cluster.rs

1//! Cluster graph predicate (ALGO-PR-077).
2//!
3//! A cluster graph (disjoint union of cliques) is a graph where every
4//! connected component is a complete graph. Equivalently, the graph
5//! is P3-free (no induced path on 3 vertices).
6//!
7//! Recognition: decompose into connected components and verify that
8//! each component with k vertices has exactly k(k-1)/2 edges.
9//!
10//! Unlike block graph, cluster graph does NOT require overall
11//! connectivity — a disconnected graph can be a cluster graph.
12
13use crate::algorithms::connectivity::components::connected_components;
14use crate::core::{Graph, IgraphResult};
15
16/// Check whether a graph is a cluster graph (disjoint union of cliques).
17///
18/// Every connected component must be a complete graph. This is
19/// equivalent to the graph being P3-free.
20///
21/// Returns `false` for directed graphs (the concept is defined for
22/// undirected graphs). Also returns `false` if the graph has
23/// self-loops or parallel edges, since components would not be
24/// simple cliques.
25///
26/// An empty graph (0 vertices) is a cluster graph (vacuously).
27/// An edgeless graph is a cluster graph (each vertex is K1).
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::{Graph, is_cluster_graph};
33///
34/// // K3 + K2 + isolated vertex
35/// let mut g = Graph::with_vertices(6);
36/// g.add_edge(0, 1).unwrap();
37/// g.add_edge(1, 2).unwrap();
38/// g.add_edge(2, 0).unwrap();
39/// g.add_edge(3, 4).unwrap();
40/// assert!(is_cluster_graph(&g).unwrap());
41///
42/// // Path P3 is NOT a cluster graph (contains induced P3)
43/// let mut g = Graph::with_vertices(3);
44/// g.add_edge(0, 1).unwrap();
45/// g.add_edge(1, 2).unwrap();
46/// assert!(!is_cluster_graph(&g).unwrap());
47/// ```
48pub fn is_cluster_graph(graph: &Graph) -> IgraphResult<bool> {
49    if graph.is_directed() {
50        return Ok(false);
51    }
52
53    let n = graph.vcount();
54    if n == 0 {
55        return Ok(true);
56    }
57
58    let cc = connected_components(graph)?;
59    let comp_count = cc.count as usize;
60
61    let mut comp_verts = vec![0u64; comp_count];
62    let mut comp_edges = vec![0u64; comp_count];
63
64    for v in 0..n {
65        let c = cc.membership[v as usize] as usize;
66        comp_verts[c] = comp_verts[c].saturating_add(1);
67    }
68
69    let ecount = graph.ecount();
70    for eid in 0..ecount {
71        let eid_u32 = u32::try_from(eid).unwrap_or(u32::MAX);
72        let (u, v) = graph.edge(eid_u32)?;
73        if u == v {
74            return Ok(false);
75        }
76        let c = cc.membership[u as usize] as usize;
77        comp_edges[c] = comp_edges[c].saturating_add(1);
78    }
79
80    for c in 0..comp_count {
81        let k = comp_verts[c];
82        let expected = k.saturating_mul(k.saturating_sub(1)) / 2;
83        if comp_edges[c] != expected {
84            return Ok(false);
85        }
86    }
87
88    Ok(true)
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    #[test]
96    fn empty_graph() {
97        let g = Graph::with_vertices(0);
98        assert!(is_cluster_graph(&g).unwrap());
99    }
100
101    #[test]
102    fn single_vertex() {
103        let g = Graph::with_vertices(1);
104        assert!(is_cluster_graph(&g).unwrap());
105    }
106
107    #[test]
108    fn edgeless_graph() {
109        let g = Graph::with_vertices(5);
110        assert!(is_cluster_graph(&g).unwrap());
111    }
112
113    #[test]
114    fn single_edge() {
115        let mut g = Graph::with_vertices(2);
116        g.add_edge(0, 1).unwrap();
117        assert!(is_cluster_graph(&g).unwrap());
118    }
119
120    #[test]
121    fn triangle() {
122        let mut g = Graph::with_vertices(3);
123        g.add_edge(0, 1).unwrap();
124        g.add_edge(1, 2).unwrap();
125        g.add_edge(2, 0).unwrap();
126        assert!(is_cluster_graph(&g).unwrap());
127    }
128
129    #[test]
130    fn k4() {
131        let mut g = Graph::with_vertices(4);
132        for u in 0..4u32 {
133            for v in (u + 1)..4 {
134                g.add_edge(u, v).unwrap();
135            }
136        }
137        assert!(is_cluster_graph(&g).unwrap());
138    }
139
140    #[test]
141    fn k3_plus_k2_plus_isolated() {
142        let mut g = Graph::with_vertices(6);
143        g.add_edge(0, 1).unwrap();
144        g.add_edge(1, 2).unwrap();
145        g.add_edge(2, 0).unwrap();
146        g.add_edge(3, 4).unwrap();
147        assert!(is_cluster_graph(&g).unwrap());
148    }
149
150    #[test]
151    fn two_disjoint_k3() {
152        let mut g = Graph::with_vertices(6);
153        g.add_edge(0, 1).unwrap();
154        g.add_edge(1, 2).unwrap();
155        g.add_edge(2, 0).unwrap();
156        g.add_edge(3, 4).unwrap();
157        g.add_edge(4, 5).unwrap();
158        g.add_edge(5, 3).unwrap();
159        assert!(is_cluster_graph(&g).unwrap());
160    }
161
162    #[test]
163    fn path_3_not_cluster() {
164        let mut g = Graph::with_vertices(3);
165        g.add_edge(0, 1).unwrap();
166        g.add_edge(1, 2).unwrap();
167        assert!(!is_cluster_graph(&g).unwrap());
168    }
169
170    #[test]
171    fn path_4_not_cluster() {
172        let mut g = Graph::with_vertices(4);
173        g.add_edge(0, 1).unwrap();
174        g.add_edge(1, 2).unwrap();
175        g.add_edge(2, 3).unwrap();
176        assert!(!is_cluster_graph(&g).unwrap());
177    }
178
179    #[test]
180    fn star_not_cluster() {
181        let mut g = Graph::with_vertices(4);
182        g.add_edge(0, 1).unwrap();
183        g.add_edge(0, 2).unwrap();
184        g.add_edge(0, 3).unwrap();
185        assert!(!is_cluster_graph(&g).unwrap());
186    }
187
188    #[test]
189    fn cycle_4_not_cluster() {
190        let mut g = Graph::with_vertices(4);
191        g.add_edge(0, 1).unwrap();
192        g.add_edge(1, 2).unwrap();
193        g.add_edge(2, 3).unwrap();
194        g.add_edge(3, 0).unwrap();
195        assert!(!is_cluster_graph(&g).unwrap());
196    }
197
198    #[test]
199    fn k4_minus_edge_not_cluster() {
200        let mut g = Graph::with_vertices(4);
201        g.add_edge(0, 1).unwrap();
202        g.add_edge(0, 2).unwrap();
203        g.add_edge(0, 3).unwrap();
204        g.add_edge(1, 2).unwrap();
205        g.add_edge(1, 3).unwrap();
206        assert!(!is_cluster_graph(&g).unwrap());
207    }
208
209    #[test]
210    fn directed_returns_false() {
211        let mut g = Graph::new(3, true).unwrap();
212        g.add_edge(0, 1).unwrap();
213        g.add_edge(1, 2).unwrap();
214        g.add_edge(2, 0).unwrap();
215        assert!(!is_cluster_graph(&g).unwrap());
216    }
217
218    #[test]
219    fn self_loop_returns_false() {
220        let mut g = Graph::with_vertices(1);
221        g.add_edge(0, 0).unwrap();
222        assert!(!is_cluster_graph(&g).unwrap());
223    }
224
225    #[test]
226    fn parallel_edges_returns_false() {
227        let mut g = Graph::with_vertices(2);
228        g.add_edge(0, 1).unwrap();
229        g.add_edge(0, 1).unwrap();
230        assert!(!is_cluster_graph(&g).unwrap());
231    }
232}
rust_igraph/algorithms/properties/is_cluster.rs

rust_igraph/algorithms/properties/
is_cluster.rs
