graph_traversal/
bipartite.rs

1use graph_collections::Queue;
2use graph_core::{Graph, NodeId};
3use std::collections::HashMap;
4
5/// Result of a bipartite check: the two colour partitions.
6///
7/// `left` and `right` together contain every reachable node from the seed
8/// used in [`is_bipartite`].
9pub struct BipartitePartitions {
10    /// Nodes coloured `0`.
11    pub left: Vec<NodeId>,
12    /// Nodes coloured `1`.
13    pub right: Vec<NodeId>,
14}
15
16/// Checks whether the graph is **bipartite** and returns its 2-colouring.
17///
18/// A graph is bipartite iff its nodes can be split into two sets such that
19/// every edge crosses between the sets (no edge is within the same set).
20/// Equivalently, a graph is bipartite iff it contains no odd-length cycle.
21///
22/// Uses BFS with two-colouring. Returns `Some(partitions)` if bipartite,
23/// or `None` if a conflict (odd cycle) is found.
24///
25/// # Examples
26///
27/// ```
28/// use graph_core::{AdjacencyList, Graph};
29/// use graph_traversal::is_bipartite;
30///
31/// // Even cycle (square) is bipartite.
32/// let mut g: AdjacencyList<()> = AdjacencyList::undirected();
33/// let a = g.add_node(());
34/// let b = g.add_node(());
35/// let c = g.add_node(());
36/// let d = g.add_node(());
37/// g.add_edge(a, b, 1.0).unwrap();
38/// g.add_edge(b, c, 1.0).unwrap();
39/// g.add_edge(c, d, 1.0).unwrap();
40/// g.add_edge(d, a, 1.0).unwrap();
41/// assert!(is_bipartite(&g).is_some());
42///
43/// // Odd cycle (triangle) is NOT bipartite.
44/// let mut tri: AdjacencyList<()> = AdjacencyList::undirected();
45/// let a = tri.add_node(());
46/// let b = tri.add_node(());
47/// let c = tri.add_node(());
48/// tri.add_edge(a, b, 1.0).unwrap();
49/// tri.add_edge(b, c, 1.0).unwrap();
50/// tri.add_edge(c, a, 1.0).unwrap();
51/// assert!(is_bipartite(&tri).is_none());
52/// ```
53pub fn is_bipartite<G: Graph>(graph: &G) -> Option<BipartitePartitions> {
54    // colour map: 0 or 1 per node.
55    let mut colour: HashMap<NodeId, u8> = HashMap::new();
56    let mut queue: Queue<NodeId> = Queue::new();
57
58    for seed in graph.nodes() {
59        if colour.contains_key(&seed) {
60            continue;
61        }
62
63        colour.insert(seed, 0);
64        queue.enqueue(seed);
65
66        while let Some(node) = queue.dequeue() {
67            let node_colour = colour[&node];
68            for (neighbour, _) in graph.neighbors(node) {
69                match colour.get(&neighbour) {
70                    Some(&c) if c == node_colour => return None, // conflict
71                    None => {
72                        colour.insert(neighbour, 1 - node_colour);
73                        queue.enqueue(neighbour);
74                    }
75                    _ => {}
76                }
77            }
78        }
79    }
80
81    let mut left = Vec::new();
82    let mut right = Vec::new();
83    for (node, c) in &colour {
84        if *c == 0 {
85            left.push(*node);
86        } else {
87            right.push(*node);
88        }
89    }
90
91    Some(BipartitePartitions { left, right })
92}
graph_traversal/bipartite.rs

graph_traversal/
bipartite.rs
