algorithms_edu/algo/graph/bipartite_check.rs
1//! This mod shows you how to determine if a graph is bipartite or not. This can be achieved in
2//! linear time by coloring the visited nodes.
3//!
4//! - Time Complexity: O(V + E)
5
6use crate::algo::graph::WeightedAdjacencyList;
7
8pub const BLACK: i8 = 0b10;
9pub const RED: i8 = BLACK ^ 1;
10const EMPTY: i8 = 0;
11
12#[derive(Debug)]
13pub enum BipartiteCheckError {
14 NotTwoColorable,
15 UnreachableNodes,
16}
17
18impl WeightedAdjacencyList {
19 // If the input graph is bipartite it has a two coloring which can be obtained
20 // through this method. Each index in the returned vec is either RED or BLACK
21 // indicating which color node i was colored.
22 // If the graph is not bipartite, a `BipartiteCheckError` is returned.
23 pub fn two_color(&self) -> Result<Vec<i8>, BipartiteCheckError> {
24 let n = self.node_count();
25 let mut colors = vec![EMPTY; n];
26 // Do a depth first search coloring the nodes of the graph as we go.
27 // This method returns the count of the number of nodes visited while
28 // coloring the graph or -1 if this graph is not bipartite.
29 fn color_graph(
30 g: &WeightedAdjacencyList,
31 node: usize,
32 color: i8,
33 colors: &mut [i8],
34 ) -> usize {
35 colors[node] = color;
36 // Toggles the color between RED and BLACK by exploiting the binary representation
37 // of the constants and flipping the least significant bit on and off.
38 let next_color = color ^ 1;
39 let mut visit_count = 1;
40 for edge in &g[node] {
41 if colors[edge.to] == color {
42 // Contradiction found. In a bipartite graph no two
43 // nodes of the same color can be next to each other!
44 return 0;
45 } else if colors[edge.to] == next_color {
46 continue;
47 } else {
48 let count = color_graph(g, edge.to, next_color, colors);
49 // If a contradiction is found propagate return -1
50 // otherwise keep track of the number of visited nodes.
51 if count == 0 {
52 return 0;
53 } else {
54 visit_count += count;
55 }
56 }
57 }
58 visit_count
59 }
60 let visit_count = color_graph(self, 0, BLACK, &mut colors);
61 if visit_count == 0 {
62 Err(BipartiteCheckError::NotTwoColorable)
63 } else if visit_count == n {
64 Ok(colors)
65 } else {
66 Err(BipartiteCheckError::UnreachableNodes)
67 }
68 }
69}
70
71#[cfg(test)]
72mod tests {
73 use super::*;
74 #[test]
75 fn test_bipartite_check() {
76 // Singleton (not bipartite)
77 let g = WeightedAdjacencyList::new_undirected_unweighted(1, &[[0, 0]]);
78 assert!(g.two_color().is_err());
79
80 // Two nodes one edge between them (bipartite)
81 let g = WeightedAdjacencyList::new_undirected_unweighted(2, &[[0, 1]]);
82 assert!(g.two_color().is_ok());
83
84 // Triangle graph (not bipartite)
85 let g = WeightedAdjacencyList::new_undirected_unweighted(3, &[[0, 1], [1, 2], [2, 0]]);
86 assert!(g.two_color().is_err());
87
88 // Disjoint graph is bipartite connected components (altogether not bipartite)
89 let g = WeightedAdjacencyList::new_undirected_unweighted(4, &[[0, 1], [2, 3]]);
90 assert!(g.two_color().is_err());
91
92 // Prints:
93 // Graph has 4 node(s) and the following edges:
94 // 0 -> 1
95 // 1 -> 0
96 // 2 -> 3
97 // 3 -> 2
98 // This graph is bipartite: false
99
100 // Square graph (bipartite)
101 let g =
102 WeightedAdjacencyList::new_undirected_unweighted(4, &[[0, 1], [1, 2], [2, 3], [3, 0]]);
103 assert!(g.two_color().is_ok());
104
105 // Square graph with additional edge (not bipartite)
106
107 let g = WeightedAdjacencyList::new_undirected_unweighted(
108 4,
109 &[[0, 1], [1, 2], [2, 3], [3, 0], [0, 2]],
110 );
111 assert!(g.two_color().is_err());
112 }
113}