Implement `is_bipartite_graph`
diff --git a/src/algo/mod.rs b/src/algo/mod.rs
index aa54405..ab558a6 100644
--- a/src/algo/mod.rs
+++ b/src/algo/mod.rs
@@ -791,6 +791,60 @@
Ok((distance, predecessor))
}
+/// Return `true` if the graph is bipartite. A graph is bipartite if it's nodes can be divided into
+/// two disjoint and indepedent sets U and V such that every edge connects U to one in V. This
+/// algorithm implements 2-coloring algorithm based on the BFS algorithm.
+///
+/// Always treats the input graph as if undirected.
+pub fn is_bipartite_undirected<G, N, VM>(g: G, start: N) -> bool
+ where G: GraphRef + Visitable<NodeId=N, Map=VM> + IntoNeighbors<NodeId=N>,
+ N: Copy + PartialEq + std::fmt::Debug,
+ VM: VisitMap<N>
+{
+ let mut red = g.visit_map();
+ red.visit(start);
+ let mut blue = g.visit_map();
+
+ let mut stack = ::std::collections::VecDeque::new();
+ stack.push_front(start);
+
+ while let Some(node) = stack.pop_front() {
+ let is_red = red.is_visited(&node);
+ let is_blue = blue.is_visited(&node);
+
+ assert!(is_red ^ is_blue);
+
+ for neighbour in g.neighbors(node) {
+ let is_neigbour_red = red.is_visited(&neighbour);
+ let is_neigbour_blue = blue.is_visited(&neighbour);
+
+ if (is_red && is_neigbour_red) || (is_blue && is_neigbour_blue) {
+ return false;
+ }
+
+ /*
+ if is_red && is_neigbour_blue || is_blue && is_neigbour_red {
+ //good
+ }
+ */
+
+ if !is_neigbour_red && !is_neigbour_blue {
+ //hasn't been visited yet
+
+ match (is_red, is_blue) {
+ (true, false) => { blue.visit(neighbour); },
+ (false, true) => { red.visit(neighbour); },
+ (_, _) => { panic!("Invariant doesn't hold"); }
+ }
+
+ stack.push_back(neighbour);
+ }
+ }
+ }
+
+ true
+}
+
use std::fmt::Debug;
use std::ops::Add;
diff --git a/tests/graph.rs b/tests/graph.rs
index a8e4097..a33977a 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -9,7 +9,7 @@
use petgraph as pg;
use petgraph::algo::{
- dominators, has_path_connecting, is_cyclic_undirected, is_isomorphic_matching,
+ dominators, has_path_connecting, is_cyclic_undirected, is_isomorphic_matching, is_bipartite_undirected,
min_spanning_tree,
};
@@ -280,6 +280,77 @@
}
#[test]
+fn bipartite() {
+ {
+ let mut gr = Graph::new_undirected();
+ let a = gr.add_node("A");
+ let b = gr.add_node("B");
+ let c = gr.add_node("C");
+
+ let d = gr.add_node("D");
+ let e = gr.add_node("E");
+ let f = gr.add_node("F");
+
+ gr.add_edge(a, d, 7.);
+ gr.add_edge(b, d, 6.);
+
+ assert!(is_bipartite_undirected(&gr, a));
+
+ let e_index = gr.add_edge(a, b, 6.);
+
+ assert!(!is_bipartite_undirected(&gr, a));
+
+ gr.remove_edge(e_index);
+
+ assert!(is_bipartite_undirected(&gr, a));
+
+ gr.add_edge(b, e, 7.);
+ gr.add_edge(b, f, 6.);
+ gr.add_edge(c, e, 6.);
+
+ assert!(is_bipartite_undirected(&gr, a));
+ }
+ {
+ let mut gr = Graph::new_undirected();
+ let a = gr.add_node("A");
+ let b = gr.add_node("B");
+ let c = gr.add_node("C");
+ let d = gr.add_node("D");
+ let e = gr.add_node("E");
+
+ let f = gr.add_node("F");
+ let g = gr.add_node("G");
+ let h = gr.add_node("H");
+
+ gr.add_edge(a, f, 7.);
+ gr.add_edge(a, g, 7.);
+ gr.add_edge(a, h, 7.);
+
+ gr.add_edge(b, f, 6.);
+ gr.add_edge(b, g, 6.);
+ gr.add_edge(b, h, 6.);
+
+ gr.add_edge(c, f, 6.);
+ gr.add_edge(c, g, 6.);
+ gr.add_edge(c, h, 6.);
+
+ gr.add_edge(d, f, 6.);
+ gr.add_edge(d, g, 6.);
+ gr.add_edge(d, h, 6.);
+
+ gr.add_edge(e, f, 6.);
+ gr.add_edge(e, g, 6.);
+ gr.add_edge(e, h, 6.);
+
+ assert!(is_bipartite_undirected(&gr, a));
+
+ gr.add_edge(a, b, 6.);
+
+ assert!(!is_bipartite_undirected(&gr, a));
+ }
+}
+
+#[test]
fn multi() {
let mut gr = Graph::new();
let a = gr.add_node("a");
