Function is_bipartite 

pub fn is_bipartite<G>(graph: &G) -> Option<BipartitePartitions>
where
    G: Graph,

Checks whether the graph is bipartite and returns its 2-colouring.

A graph is bipartite iff its nodes can be split into two sets such that every edge crosses between the sets (no edge is within the same set). Equivalently, a graph is bipartite iff it contains no odd-length cycle.

Uses BFS with two-colouring. Returns Some(partitions) if bipartite, or None if a conflict (odd cycle) is found.

Examples

use graph_core::{AdjacencyList, Graph};
use graph_traversal::is_bipartite;

// Even cycle (square) is bipartite.
let mut g: AdjacencyList<()> = AdjacencyList::undirected();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
let d = g.add_node(());
g.add_edge(a, b, 1.0).unwrap();
g.add_edge(b, c, 1.0).unwrap();
g.add_edge(c, d, 1.0).unwrap();
g.add_edge(d, a, 1.0).unwrap();
assert!(is_bipartite(&g).is_some());

// Odd cycle (triangle) is NOT bipartite.
let mut tri: AdjacencyList<()> = AdjacencyList::undirected();
let a = tri.add_node(());
let b = tri.add_node(());
let c = tri.add_node(());
tri.add_edge(a, b, 1.0).unwrap();
tri.add_edge(b, c, 1.0).unwrap();
tri.add_edge(c, a, 1.0).unwrap();
assert!(is_bipartite(&tri).is_none());