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}
algorithms_edu/algo/graph/bipartite_check.rs

algorithms_edu/algo/graph/
bipartite_check.rs
