algorithmica 0.1.10

Rust Algorithms
Documentation 
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

pub struct Bipartite<'a> {
    is_bipartite: bool,
    edge_to: Vec<usize>,
    visited: Vec<bool>,
    color: Vec<bool>,
    graph: &'a crate::graph::Graph,
}

impl<'a> Bipartite<'a> {
    pub fn new(graph: &'a crate::graph::Graph, source: usize) -> Self {
        let mut bipartite = Self {
            is_bipartite: true,
            edge_to: vec![0; graph.v],
            visited: vec![false; graph.v],
            color: vec![false; graph.v],
            graph,
        };

        for w in graph.adj(source) {
            if !bipartite.visited[*w] {
                bipartite.dfs(*w);
            }
        }
        bipartite
    }

    pub fn is_bipartite(&self) -> bool {
        self.is_bipartite
    }

    fn dfs(&mut self, w: usize) {
        self.visited[w] = true;
        for v in self.graph.adj(w) {
            if !self.visited[*v] {
                self.edge_to[*v] = w;
                self.visited[*v] = true;
                self.color[*v] = !self.color[w];
                self.dfs(*v);
            }
            // If there is an odd cycle occur in the graph, means graph is not bipartite
            // Find the cycle
            if self.color[*v] == self.color[w] {
                self.is_bipartite = false;
            }
        }
    }
}