1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

//! This mod shows you how to determine if a graph is bipartite or not. This can be achieved in
//! linear time by coloring the visited nodes.
//!
//! - Time Complexity: O(V + E)

use crate::algo::graph::WeightedAdjacencyList;

pub const BLACK: i8 = 0b10;
pub const RED: i8 = BLACK ^ 1;
const EMPTY: i8 = 0;

#[derive(Debug)]
pub enum BipartiteCheckError {
    NotTwoColorable,
    UnreachableNodes,
}

impl WeightedAdjacencyList {
    // If the input graph is bipartite it has a two coloring which can be obtained
    // through this method. Each index in the returned vec is either RED or BLACK
    // indicating which color node i was colored.
    // If the graph is not bipartite, a `BipartiteCheckError` is returned.
    pub fn two_color(&self) -> Result<Vec<i8>, BipartiteCheckError> {
        let n = self.node_count();
        let mut colors = vec![EMPTY; n];
        // Do a depth first search coloring the nodes of the graph as we go.
        // This method returns the count of the number of nodes visited while
        // coloring the graph or -1 if this graph is not bipartite.
        fn color_graph(
            g: &WeightedAdjacencyList,
            node: usize,
            color: i8,
            colors: &mut [i8],
        ) -> usize {
            colors[node] = color;
            // Toggles the color between RED and BLACK by exploiting the binary representation
            // of the constants and flipping the least significant bit on and off.
            let next_color = color ^ 1;
            let mut visit_count = 1;
            for edge in &g[node] {
                if colors[edge.to] == color {
                    // Contradiction found. In a bipartite graph no two
                    // nodes of the same color can be next to each other!
                    return 0;
                } else if colors[edge.to] == next_color {
                    continue;
                } else {
                    let count = color_graph(g, edge.to, next_color, colors);
                    // If a contradiction is found propagate return -1
                    // otherwise keep track of the number of visited nodes.
                    if count == 0 {
                        return 0;
                    } else {
                        visit_count += count;
                    }
                }
            }
            visit_count
        }
        let visit_count = color_graph(self, 0, BLACK, &mut colors);
        if visit_count == 0 {
            Err(BipartiteCheckError::NotTwoColorable)
        } else if visit_count == n {
            Ok(colors)
        } else {
            Err(BipartiteCheckError::UnreachableNodes)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_bipartite_check() {
        // Singleton (not bipartite)
        let g = WeightedAdjacencyList::new_undirected_unweighted(1, &[[0, 0]]);
        assert!(g.two_color().is_err());

        // Two nodes one edge between them (bipartite)
        let g = WeightedAdjacencyList::new_undirected_unweighted(2, &[[0, 1]]);
        assert!(g.two_color().is_ok());

        // Triangle graph (not bipartite)
        let g = WeightedAdjacencyList::new_undirected_unweighted(3, &[[0, 1], [1, 2], [2, 0]]);
        assert!(g.two_color().is_err());

        // Disjoint graph is bipartite connected components (altogether not bipartite)
        let g = WeightedAdjacencyList::new_undirected_unweighted(4, &[[0, 1], [2, 3]]);
        assert!(g.two_color().is_err());

        // Prints:
        // Graph has 4 node(s) and the following edges:
        // 0 -> 1
        // 1 -> 0
        // 2 -> 3
        // 3 -> 2
        // This graph is bipartite: false

        // Square graph (bipartite)
        let g =
            WeightedAdjacencyList::new_undirected_unweighted(4, &[[0, 1], [1, 2], [2, 3], [3, 0]]);
        assert!(g.two_color().is_ok());

        // Square graph with additional edge (not bipartite)

        let g = WeightedAdjacencyList::new_undirected_unweighted(
            4,
            &[[0, 1], [1, 2], [2, 3], [3, 0], [0, 2]],
        );
        assert!(g.two_color().is_err());
    }
}