rust_igraph/algorithms/properties/
is_bipartite.rs

1//! Bipartiteness test and vertex partition (ALGO-PR-037).
2//!
3//! BFS-based 2-coloring to detect if a graph is bipartite.
4//! Optionally returns the bipartition (type assignment for each vertex).
5//!
6//! Counterpart of `igraph_is_bipartite` from
7//! `references/igraph/src/misc/bipartite.c`.
8
9use std::collections::VecDeque;
10
11use crate::core::{Graph, IgraphResult, VertexId};
12
13/// Result of bipartiteness check.
14#[derive(Debug, Clone, PartialEq, Eq)]
15pub struct BipartiteResult {
16    /// Whether the graph is bipartite.
17    pub is_bipartite: bool,
18    /// If bipartite, the partition assignment for each vertex.
19    /// `types[v]` is `false` for one side and `true` for the other.
20    /// Empty if `is_bipartite` is false.
21    pub types: Vec<bool>,
22}
23
24/// Check whether a graph is bipartite and optionally return the partition.
25///
26/// A graph is bipartite if its vertices can be divided into two disjoint
27/// sets such that every edge connects a vertex in one set to a vertex in
28/// the other. Equivalently, a graph is bipartite iff it contains no
29/// odd-length cycles.
30///
31/// Edge directions are ignored — the test treats the graph as undirected.
32///
33/// # Examples
34///
35/// ```
36/// use rust_igraph::{Graph, is_bipartite};
37///
38/// // Path 0-1-2-3 is bipartite
39/// let mut g = Graph::with_vertices(4);
40/// g.add_edge(0, 1).unwrap();
41/// g.add_edge(1, 2).unwrap();
42/// g.add_edge(2, 3).unwrap();
43/// let result = is_bipartite(&g).unwrap();
44/// assert!(result.is_bipartite);
45/// assert_eq!(result.types.len(), 4);
46///
47/// // Triangle is not bipartite
48/// let mut g = Graph::with_vertices(3);
49/// g.add_edge(0, 1).unwrap();
50/// g.add_edge(1, 2).unwrap();
51/// g.add_edge(2, 0).unwrap();
52/// let result = is_bipartite(&g).unwrap();
53/// assert!(!result.is_bipartite);
54/// ```
55pub fn is_bipartite(graph: &Graph) -> IgraphResult<BipartiteResult> {
56    let n = graph.vcount();
57
58    if n == 0 {
59        return Ok(BipartiteResult {
60            is_bipartite: true,
61            types: Vec::new(),
62        });
63    }
64
65    // 0 = unseen, 1 = type A, 2 = type B
66    let mut color: Vec<u8> = vec![0; n as usize];
67    let mut queue: VecDeque<VertexId> = VecDeque::new();
68    let mut bipartite = true;
69
70    'outer: for start in 0..n {
71        if color[start as usize] != 0 {
72            continue;
73        }
74
75        color[start as usize] = 1;
76        queue.push_back(start);
77
78        while let Some(v) = queue.pop_front() {
79            let v_color = color[v as usize];
80            let neighbors = get_all_neighbors(graph, v)?;
81
82            for nei in neighbors {
83                if color[nei as usize] == 0 {
84                    color[nei as usize] = 3 - v_color;
85                    queue.push_back(nei);
86                } else if color[nei as usize] == v_color {
87                    bipartite = false;
88                    break 'outer;
89                }
90            }
91        }
92    }
93
94    if bipartite {
95        let types: Vec<bool> = color.iter().map(|&c| c == 2).collect();
96        Ok(BipartiteResult {
97            is_bipartite: true,
98            types,
99        })
100    } else {
101        Ok(BipartiteResult {
102            is_bipartite: false,
103            types: Vec::new(),
104        })
105    }
106}
107
108/// Get all neighbors of vertex v (ignoring direction).
109fn get_all_neighbors(graph: &Graph, v: VertexId) -> IgraphResult<Vec<VertexId>> {
110    let mut neighbors = Vec::new();
111    let out_edges = graph.incident(v)?;
112
113    for eid in &out_edges {
114        let (from, to) = graph.edge(*eid)?;
115        let nei = if from == v { to } else { from };
116        neighbors.push(nei);
117    }
118
119    if graph.is_directed() {
120        let in_edges = graph.incident_in(v)?;
121        for eid in &in_edges {
122            if !out_edges.contains(eid) {
123                let (from, to) = graph.edge(*eid)?;
124                let nei = if from == v { to } else { from };
125                neighbors.push(nei);
126            }
127        }
128    }
129
130    Ok(neighbors)
131}
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136
137    #[test]
138    fn empty_graph() {
139        let g = Graph::with_vertices(0);
140        let result = is_bipartite(&g).unwrap();
141        assert!(result.is_bipartite);
142        assert!(result.types.is_empty());
143    }
144
145    #[test]
146    fn single_vertex() {
147        let g = Graph::with_vertices(1);
148        let result = is_bipartite(&g).unwrap();
149        assert!(result.is_bipartite);
150        assert_eq!(result.types.len(), 1);
151    }
152
153    #[test]
154    fn isolated_vertices() {
155        let g = Graph::with_vertices(5);
156        let result = is_bipartite(&g).unwrap();
157        assert!(result.is_bipartite);
158        assert_eq!(result.types.len(), 5);
159    }
160
161    #[test]
162    fn single_edge() {
163        let mut g = Graph::with_vertices(2);
164        g.add_edge(0, 1).unwrap();
165        let result = is_bipartite(&g).unwrap();
166        assert!(result.is_bipartite);
167        assert_ne!(result.types[0], result.types[1]);
168    }
169
170    #[test]
171    fn path_graph() {
172        let mut g = Graph::with_vertices(5);
173        g.add_edge(0, 1).unwrap();
174        g.add_edge(1, 2).unwrap();
175        g.add_edge(2, 3).unwrap();
176        g.add_edge(3, 4).unwrap();
177        let result = is_bipartite(&g).unwrap();
178        assert!(result.is_bipartite);
179        // Adjacent vertices must have different types
180        for eid in 0..g.ecount() {
181            #[allow(clippy::cast_possible_truncation)]
182            let (from, to) = g.edge(eid as u32).unwrap();
183            assert_ne!(
184                result.types[from as usize], result.types[to as usize],
185                "edge ({from}, {to}) violates bipartiteness"
186            );
187        }
188    }
189
190    #[test]
191    fn even_cycle() {
192        let mut g = Graph::with_vertices(4);
193        g.add_edge(0, 1).unwrap();
194        g.add_edge(1, 2).unwrap();
195        g.add_edge(2, 3).unwrap();
196        g.add_edge(3, 0).unwrap();
197        let result = is_bipartite(&g).unwrap();
198        assert!(result.is_bipartite);
199    }
200
201    #[test]
202    fn odd_cycle_triangle() {
203        let mut g = Graph::with_vertices(3);
204        g.add_edge(0, 1).unwrap();
205        g.add_edge(1, 2).unwrap();
206        g.add_edge(2, 0).unwrap();
207        let result = is_bipartite(&g).unwrap();
208        assert!(!result.is_bipartite);
209        assert!(result.types.is_empty());
210    }
211
212    #[test]
213    fn odd_cycle_5() {
214        let mut g = Graph::with_vertices(5);
215        g.add_edge(0, 1).unwrap();
216        g.add_edge(1, 2).unwrap();
217        g.add_edge(2, 3).unwrap();
218        g.add_edge(3, 4).unwrap();
219        g.add_edge(4, 0).unwrap();
220        let result = is_bipartite(&g).unwrap();
221        assert!(!result.is_bipartite);
222    }
223
224    #[test]
225    fn complete_bipartite_k23() {
226        let mut g = Graph::with_vertices(5);
227        // 0,1 on one side; 2,3,4 on the other
228        g.add_edge(0, 2).unwrap();
229        g.add_edge(0, 3).unwrap();
230        g.add_edge(0, 4).unwrap();
231        g.add_edge(1, 2).unwrap();
232        g.add_edge(1, 3).unwrap();
233        g.add_edge(1, 4).unwrap();
234        let result = is_bipartite(&g).unwrap();
235        assert!(result.is_bipartite);
236        // 0 and 1 should have the same type; 2,3,4 should have the other
237        assert_eq!(result.types[0], result.types[1]);
238        assert_eq!(result.types[2], result.types[3]);
239        assert_eq!(result.types[3], result.types[4]);
240        assert_ne!(result.types[0], result.types[2]);
241    }
242
243    #[test]
244    fn disconnected_bipartite() {
245        let mut g = Graph::with_vertices(6);
246        // Component 1: path 0-1-2
247        g.add_edge(0, 1).unwrap();
248        g.add_edge(1, 2).unwrap();
249        // Component 2: edge 3-4
250        g.add_edge(3, 4).unwrap();
251        // vertex 5 isolated
252        let result = is_bipartite(&g).unwrap();
253        assert!(result.is_bipartite);
254    }
255
256    #[test]
257    fn disconnected_not_bipartite() {
258        let mut g = Graph::with_vertices(6);
259        // Component 1: triangle 0-1-2
260        g.add_edge(0, 1).unwrap();
261        g.add_edge(1, 2).unwrap();
262        g.add_edge(2, 0).unwrap();
263        // Component 2: edge 3-4 (bipartite)
264        g.add_edge(3, 4).unwrap();
265        let result = is_bipartite(&g).unwrap();
266        assert!(!result.is_bipartite);
267    }
268
269    #[test]
270    fn self_loop_not_bipartite() {
271        let mut g = Graph::with_vertices(2);
272        g.add_edge(0, 0).unwrap();
273        g.add_edge(0, 1).unwrap();
274        let result = is_bipartite(&g).unwrap();
275        assert!(!result.is_bipartite);
276    }
277
278    #[test]
279    fn directed_ignores_direction() {
280        let mut g = Graph::new(4, true).unwrap();
281        g.add_edge(0, 1).unwrap();
282        g.add_edge(2, 1).unwrap();
283        g.add_edge(2, 3).unwrap();
284        let result = is_bipartite(&g).unwrap();
285        assert!(result.is_bipartite);
286    }
287
288    #[test]
289    fn k4_not_bipartite() {
290        let mut g = Graph::with_vertices(4);
291        g.add_edge(0, 1).unwrap();
292        g.add_edge(0, 2).unwrap();
293        g.add_edge(0, 3).unwrap();
294        g.add_edge(1, 2).unwrap();
295        g.add_edge(1, 3).unwrap();
296        g.add_edge(2, 3).unwrap();
297        let result = is_bipartite(&g).unwrap();
298        assert!(!result.is_bipartite);
299    }
300
301    #[test]
302    fn star_bipartite() {
303        let mut g = Graph::with_vertices(5);
304        g.add_edge(0, 1).unwrap();
305        g.add_edge(0, 2).unwrap();
306        g.add_edge(0, 3).unwrap();
307        g.add_edge(0, 4).unwrap();
308        let result = is_bipartite(&g).unwrap();
309        assert!(result.is_bipartite);
310        // Center (0) on one side, leaves on the other
311        assert_ne!(result.types[0], result.types[1]);
312        assert_eq!(result.types[1], result.types[2]);
313        assert_eq!(result.types[2], result.types[3]);
314        assert_eq!(result.types[3], result.types[4]);
315    }
316
317    #[test]
318    fn cube_bipartite() {
319        // Cube graph Q3 is bipartite
320        let mut g = Graph::with_vertices(8);
321        g.add_edge(0, 1).unwrap();
322        g.add_edge(0, 2).unwrap();
323        g.add_edge(0, 4).unwrap();
324        g.add_edge(1, 3).unwrap();
325        g.add_edge(1, 5).unwrap();
326        g.add_edge(2, 3).unwrap();
327        g.add_edge(2, 6).unwrap();
328        g.add_edge(3, 7).unwrap();
329        g.add_edge(4, 5).unwrap();
330        g.add_edge(4, 6).unwrap();
331        g.add_edge(5, 7).unwrap();
332        g.add_edge(6, 7).unwrap();
333        let result = is_bipartite(&g).unwrap();
334        assert!(result.is_bipartite);
335    }
336}
rust_igraph/algorithms/properties/is_bipartite.rs

rust_igraph/algorithms/properties/
is_bipartite.rs
