rust_igraph/algorithms/properties/
is_biclique.rs

1//! Complete bipartite graph predicate (ALGO-PR-083).
2//!
3//! A graph is a complete bipartite graph (biclique) if it is bipartite
4//! and every vertex in one part is adjacent to every vertex in the
5//! other part.
6//!
7//! For directed graphs, the function returns `false`.
8
9use crate::algorithms::properties::is_bipartite::is_bipartite;
10use crate::core::{Graph, IgraphResult};
11
12/// Check whether a graph is a complete bipartite graph (biclique).
13///
14/// Returns `false` for directed graphs.
15/// Returns `true` for the empty graph (vacuously).
16/// Returns `true` for a single vertex (trivial `K_{1,0}`).
17///
18/// Self-loops and multi-edges cause `false` (not simple bipartite).
19///
20/// # Examples
21///
22/// ```
23/// use rust_igraph::{Graph, is_biclique};
24///
25/// // K_{2,3}: complete bipartite
26/// let mut g = Graph::with_vertices(5);
27/// g.add_edge(0, 2).unwrap();
28/// g.add_edge(0, 3).unwrap();
29/// g.add_edge(0, 4).unwrap();
30/// g.add_edge(1, 2).unwrap();
31/// g.add_edge(1, 3).unwrap();
32/// g.add_edge(1, 4).unwrap();
33/// assert!(is_biclique(&g).unwrap());
34///
35/// // P4 is NOT a biclique (bipartite but not complete bipartite)
36/// let mut g = Graph::with_vertices(4);
37/// g.add_edge(0, 1).unwrap();
38/// g.add_edge(1, 2).unwrap();
39/// g.add_edge(2, 3).unwrap();
40/// assert!(!is_biclique(&g).unwrap());
41/// ```
42pub fn is_biclique(graph: &Graph) -> IgraphResult<bool> {
43    if graph.is_directed() {
44        return Ok(false);
45    }
46
47    let n = graph.vcount();
48    if n <= 1 {
49        return Ok(true);
50    }
51
52    let bp = is_bipartite(graph)?;
53    if !bp.is_bipartite {
54        return Ok(false);
55    }
56
57    let part_a: usize = bp.types.iter().filter(|&&t| !t).count();
58    let part_b: usize = bp.types.iter().filter(|&&t| t).count();
59
60    // Expected edges in a complete bipartite graph
61    let expected_edges = part_a.saturating_mul(part_b);
62    if graph.ecount() != expected_edges {
63        return Ok(false);
64    }
65
66    // Edge count match + bipartite ⟹ complete bipartite
67    // (any missing cross-edge would reduce the count, and
68    // bipartiteness ensures no intra-part edges)
69    Ok(true)
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn empty_graph() {
78        let g = Graph::with_vertices(0);
79        assert!(is_biclique(&g).unwrap());
80    }
81
82    #[test]
83    fn single_vertex() {
84        let g = Graph::with_vertices(1);
85        assert!(is_biclique(&g).unwrap());
86    }
87
88    #[test]
89    fn single_edge_k11() {
90        let mut g = Graph::with_vertices(2);
91        g.add_edge(0, 1).unwrap();
92        assert!(is_biclique(&g).unwrap());
93    }
94
95    #[test]
96    fn k13() {
97        let mut g = Graph::with_vertices(4);
98        g.add_edge(0, 1).unwrap();
99        g.add_edge(0, 2).unwrap();
100        g.add_edge(0, 3).unwrap();
101        assert!(is_biclique(&g).unwrap());
102    }
103
104    #[test]
105    fn k22() {
106        let mut g = Graph::with_vertices(4);
107        g.add_edge(0, 2).unwrap();
108        g.add_edge(0, 3).unwrap();
109        g.add_edge(1, 2).unwrap();
110        g.add_edge(1, 3).unwrap();
111        assert!(is_biclique(&g).unwrap());
112    }
113
114    #[test]
115    fn k23() {
116        let mut g = Graph::with_vertices(5);
117        g.add_edge(0, 2).unwrap();
118        g.add_edge(0, 3).unwrap();
119        g.add_edge(0, 4).unwrap();
120        g.add_edge(1, 2).unwrap();
121        g.add_edge(1, 3).unwrap();
122        g.add_edge(1, 4).unwrap();
123        assert!(is_biclique(&g).unwrap());
124    }
125
126    #[test]
127    fn k33() {
128        let mut g = Graph::with_vertices(6);
129        for u in 0..3u32 {
130            for v in 3..6u32 {
131                g.add_edge(u, v).unwrap();
132            }
133        }
134        assert!(is_biclique(&g).unwrap());
135    }
136
137    #[test]
138    fn path_p3_is_k12() {
139        // P3 = 0-1-2 is K_{1,2} (star with center 1)
140        let mut g = Graph::with_vertices(3);
141        g.add_edge(0, 1).unwrap();
142        g.add_edge(1, 2).unwrap();
143        assert!(is_biclique(&g).unwrap());
144    }
145
146    #[test]
147    fn path_p4_not_biclique() {
148        // P4 = 0-1-2-3: bipartite {0,2},{1,3} but only 3 of 4 cross-edges
149        let mut g = Graph::with_vertices(4);
150        g.add_edge(0, 1).unwrap();
151        g.add_edge(1, 2).unwrap();
152        g.add_edge(2, 3).unwrap();
153        assert!(!is_biclique(&g).unwrap());
154    }
155
156    #[test]
157    fn triangle_not_biclique() {
158        let mut g = Graph::with_vertices(3);
159        g.add_edge(0, 1).unwrap();
160        g.add_edge(1, 2).unwrap();
161        g.add_edge(2, 0).unwrap();
162        assert!(!is_biclique(&g).unwrap());
163    }
164
165    #[test]
166    fn c4_is_k22() {
167        // C4 = K_{2,2}: bipartite {0,2},{1,3}, all 4 cross-edges present
168        let mut g = Graph::with_vertices(4);
169        g.add_edge(0, 1).unwrap();
170        g.add_edge(1, 2).unwrap();
171        g.add_edge(2, 3).unwrap();
172        g.add_edge(3, 0).unwrap();
173        assert!(is_biclique(&g).unwrap());
174    }
175
176    #[test]
177    fn edgeless_two_vertices() {
178        // Edgeless 2-vertex graph: bipartite puts both in same part → K_{2,0}
179        let g = Graph::with_vertices(2);
180        assert!(is_biclique(&g).unwrap());
181    }
182
183    #[test]
184    fn star_is_biclique() {
185        // Star K_{1,4} is a complete bipartite graph
186        let mut g = Graph::with_vertices(5);
187        for i in 1..5u32 {
188            g.add_edge(0, i).unwrap();
189        }
190        assert!(is_biclique(&g).unwrap());
191    }
192
193    #[test]
194    fn directed_returns_false() {
195        let mut g = Graph::new(4, true).unwrap();
196        g.add_edge(0, 2).unwrap();
197        g.add_edge(0, 3).unwrap();
198        g.add_edge(1, 2).unwrap();
199        g.add_edge(1, 3).unwrap();
200        assert!(!is_biclique(&g).unwrap());
201    }
202
203    #[test]
204    fn disconnected_not_biclique() {
205        // Two components: each is K_{1,1}, but whole graph is not a biclique
206        let mut g = Graph::with_vertices(4);
207        g.add_edge(0, 1).unwrap();
208        g.add_edge(2, 3).unwrap();
209        assert!(!is_biclique(&g).unwrap());
210    }
211
212    #[test]
213    fn k14() {
214        let mut g = Graph::with_vertices(5);
215        g.add_edge(0, 1).unwrap();
216        g.add_edge(0, 2).unwrap();
217        g.add_edge(0, 3).unwrap();
218        g.add_edge(0, 4).unwrap();
219        assert!(is_biclique(&g).unwrap());
220    }
221}
rust_igraph/algorithms/properties/is_biclique.rs

rust_igraph/algorithms/properties/
is_biclique.rs
