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
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 {
pub fn two_color(&self) -> Result<Vec<i8>, BipartiteCheckError> {
let n = self.node_count();
let mut colors = vec![EMPTY; n];
fn color_graph(
g: &WeightedAdjacencyList,
node: usize,
color: i8,
colors: &mut [i8],
) -> usize {
colors[node] = color;
let next_color = color ^ 1;
let mut visit_count = 1;
for edge in &g[node] {
if colors[edge.to] == color {
return 0;
} else if colors[edge.to] == next_color {
continue;
} else {
let count = color_graph(g, edge.to, next_color, colors);
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() {
let g = WeightedAdjacencyList::new_undirected_unweighted(1, &[[0, 0]]);
assert!(g.two_color().is_err());
let g = WeightedAdjacencyList::new_undirected_unweighted(2, &[[0, 1]]);
assert!(g.two_color().is_ok());
let g = WeightedAdjacencyList::new_undirected_unweighted(3, &[[0, 1], [1, 2], [2, 0]]);
assert!(g.two_color().is_err());
let g = WeightedAdjacencyList::new_undirected_unweighted(4, &[[0, 1], [2, 3]]);
assert!(g.two_color().is_err());
let g =
WeightedAdjacencyList::new_undirected_unweighted(4, &[[0, 1], [1, 2], [2, 3], [3, 0]]);
assert!(g.two_color().is_ok());
let g = WeightedAdjacencyList::new_undirected_unweighted(
4,
&[[0, 1], [1, 2], [2, 3], [3, 0], [0, 2]],
);
assert!(g.two_color().is_err());
}
}