weavatrix_graph/algo/
bipartite.rs

1use crate::IndexUndirectedGraphView;
2use crate::Vec;
3use alloc::collections::VecDeque;
4
5#[derive(Debug, Clone, PartialEq, Eq)]
6pub struct BipartitePartition<Node> {
7    left: Vec<Node>,
8    right: Vec<Node>,
9}
10
11impl<Node> BipartitePartition<Node> {
12    #[must_use]
13    pub fn left(&self) -> &[Node] {
14        &self.left
15    }
16
17    #[must_use]
18    pub fn right(&self) -> &[Node] {
19        &self.right
20    }
21}
22
23#[derive(Debug, Clone, PartialEq, Eq)]
24pub struct BipartiteMatching<Node> {
25    pairs: Vec<(Node, Node)>,
26}
27
28impl<Node> BipartiteMatching<Node> {
29    #[must_use]
30    pub fn pairs(&self) -> &[(Node, Node)] {
31        &self.pairs
32    }
33
34    #[must_use]
35    pub const fn len(&self) -> usize {
36        self.pairs.len()
37    }
38
39    #[must_use]
40    pub const fn is_empty(&self) -> bool {
41        self.pairs.is_empty()
42    }
43}
44
45pub fn bipartite_partition<G>(graph: &G) -> Option<BipartitePartition<G::Node>>
46where
47    G: IndexUndirectedGraphView,
48{
49    let (nodes, adjacency) = indexed(graph);
50    let colors = color(&nodes, &adjacency)?;
51    let mut left = Vec::new();
52    let mut right = Vec::new();
53    for node in nodes.into_iter().flatten() {
54        if colors[G::node_slot(node)] == Some(false) {
55            left.push(node);
56        } else {
57            right.push(node);
58        }
59    }
60    Some(BipartitePartition { left, right })
61}
62
63pub fn maximum_bipartite_matching<G>(graph: &G) -> Option<BipartiteMatching<G::Node>>
64where
65    G: IndexUndirectedGraphView,
66{
67    let (nodes, adjacency) = indexed(graph);
68    let colors = color(&nodes, &adjacency)?;
69    let left = nodes
70        .iter()
71        .enumerate()
72        .filter_map(|(slot, node)| (node.is_some() && colors[slot] == Some(false)).then_some(slot))
73        .collect::<Vec<_>>();
74    let mut matching = vec![None; graph.node_bound()];
75    loop {
76        let distances = layers(&left, &adjacency, &matching);
77        let mut changed = false;
78        for &node in &left {
79            if matching[node].is_none() && augment(node, &adjacency, &distances, &mut matching) {
80                changed = true;
81            }
82        }
83        if !changed {
84            break;
85        }
86    }
87    let pairs = left
88        .into_iter()
89        .filter_map(|left| Some((nodes[left]?, nodes[matching[left]?]?)))
90        .collect();
91    Some(BipartiteMatching { pairs })
92}
93
94fn indexed<G: IndexUndirectedGraphView>(graph: &G) -> (Vec<Option<G::Node>>, Vec<Vec<usize>>) {
95    let mut nodes = vec![None; graph.node_bound()];
96    let mut adjacency = vec![Vec::new(); graph.node_bound()];
97    for node in graph.node_indices() {
98        let slot = G::node_slot(node);
99        nodes[slot] = Some(node);
100        adjacency[slot] = graph
101            .incident_edges(node)
102            .filter_map(|edge| graph.opposite(edge, node))
103            .map(G::node_slot)
104            .collect();
105        adjacency[slot].sort_unstable();
106        adjacency[slot].dedup();
107    }
108    (nodes, adjacency)
109}
110
111fn color<Node>(nodes: &[Option<Node>], adjacency: &[Vec<usize>]) -> Option<Vec<Option<bool>>> {
112    let mut colors = vec![None; nodes.len()];
113    for start in 0..nodes.len() {
114        if nodes[start].is_none() || colors[start].is_some() {
115            continue;
116        }
117        colors[start] = Some(false);
118        let mut queue = VecDeque::from([start]);
119        while let Some(node) = queue.pop_front() {
120            let current = colors[node]?;
121            for &neighbor in &adjacency[node] {
122                if neighbor == node {
123                    return None;
124                }
125                if let Some(neighbor_color) = colors[neighbor] {
126                    if neighbor_color == current {
127                        return None;
128                    }
129                } else {
130                    colors[neighbor] = Some(!current);
131                    queue.push_back(neighbor);
132                }
133            }
134        }
135    }
136    Some(colors)
137}
138
139fn layers(left: &[usize], adjacency: &[Vec<usize>], matching: &[Option<usize>]) -> Vec<usize> {
140    let mut distances = vec![usize::MAX; adjacency.len()];
141    let mut queue = VecDeque::new();
142    for &node in left {
143        if matching[node].is_none() {
144            distances[node] = 0;
145            queue.push_back(node);
146        }
147    }
148    while let Some(node) = queue.pop_front() {
149        for &right in &adjacency[node] {
150            if let Some(next) = matching[right]
151                && distances[next] == usize::MAX
152            {
153                distances[next] = distances[node] + 1;
154                queue.push_back(next);
155            }
156        }
157    }
158    distances
159}
160
161fn augment(
162    node: usize,
163    adjacency: &[Vec<usize>],
164    distances: &[usize],
165    matching: &mut [Option<usize>],
166) -> bool {
167    for &right in &adjacency[node] {
168        let can_use = matching[right].is_none_or(|next| {
169            distances[next] == distances[node] + 1 && augment(next, adjacency, distances, matching)
170        });
171        if can_use {
172            matching[node] = Some(right);
173            matching[right] = Some(node);
174            return true;
175        }
176    }
177    false
178}
weavatrix_graph/algo/bipartite.rs

weavatrix_graph/algo/
bipartite.rs
