drmkit_planes/matching.rs
1// SPDX-FileCopyrightText: (c) 2026 Joel Winarske
2// SPDX-License-Identifier: MIT
3
4//! Maximum-cardinality bipartite matching, Hopcroft–Karp.
5//!
6//! Port of `src/planes/matching.{hpp,cpp}`.
7//!
8//! Plane allocation is a bipartite graph:
9//!
10//! - **left** nodes are layers,
11//! - **right** nodes are planes,
12//! - an **edge** means the layer could potentially use that plane.
13//!
14//! Runs in `O(E·√V)` — microseconds at the counts that occur in practice,
15//! where both sides are usually eight or fewer.
16//!
17//! # Cardinality first, score second
18//!
19//! The matcher maximizes the **number of placements**. Scores only order the
20//! search, so a preferred plane is tried first among otherwise equal options.
21//! A score can never cause a layer to go unplaced that could have been placed.
22//! That ordering is what makes the allocator's stability bonus safe to add —
23//! see [`WARM_STABILITY_BONUS`](crate::WARM_STABILITY_BONUS).
24
25use std::collections::VecDeque;
26
27/// One candidate placement.
28#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29struct Edge {
30 right: usize,
31 /// Higher is more preferred. Ordering only; never affects cardinality.
32 score: i32,
33}
34
35/// A reusable Hopcroft–Karp matcher.
36///
37/// Built to be reset and refilled each frame: the internal vectors keep their
38/// capacity across [`reset`](Self::reset), so a caller with a stable graph
39/// shape pays one set of allocations on the first frame and none after.
40#[derive(Debug, Default, Clone)]
41pub struct BipartiteMatching {
42 n_left: usize,
43 n_right: usize,
44 /// `adj[u]` is the edges out of left node `u`. Sorted by descending score
45 /// in [`solve`](Self::solve).
46 adj: Vec<Vec<Edge>>,
47 match_left: Vec<Option<usize>>,
48 match_right: Vec<Option<usize>>,
49 /// BFS layer distance per left node, plus one sentinel slot at `n_left`
50 /// standing for "reached a free right node". `None` is infinity.
51 dist: Vec<Option<usize>>,
52 matched: usize,
53}
54
55impl BipartiteMatching {
56 /// An empty matcher. Shape it with [`reset`](Self::reset).
57 #[must_use]
58 pub const fn new() -> Self {
59 Self {
60 n_left: 0,
61 n_right: 0,
62 adj: Vec::new(),
63 match_left: Vec::new(),
64 match_right: Vec::new(),
65 dist: Vec::new(),
66 matched: 0,
67 }
68 }
69
70 /// A matcher shaped for `n_left` layers and `n_right` planes.
71 #[must_use]
72 pub fn with_shape(n_left: usize, n_right: usize) -> Self {
73 let mut matching = Self::new();
74 matching.reset(n_left, n_right);
75 matching
76 }
77
78 /// Re-shape and clear, keeping allocated capacity.
79 ///
80 /// Every per-node container is reset, so a fresh call sees exactly the
81 /// state a freshly constructed matcher would.
82 pub fn reset(&mut self, n_left: usize, n_right: usize) {
83 self.n_left = n_left;
84 self.n_right = n_right;
85 self.matched = 0;
86
87 // `resize` leaves existing slots' edges intact, so clear each one: the
88 // caller wants a fresh edge list, not last frame's.
89 self.adj.resize_with(n_left, Vec::new);
90 self.adj.truncate(n_left);
91 for edges in &mut self.adj {
92 edges.clear();
93 }
94
95 self.match_left.clear();
96 self.match_left.resize(n_left, None);
97 self.match_right.clear();
98 self.match_right.resize(n_right, None);
99 self.dist.clear();
100 self.dist.resize(n_left + 1, None);
101 }
102
103 /// Add an unscored edge: layer `left` could use plane `right`.
104 ///
105 /// Out-of-range endpoints are ignored rather than panicking — a caller
106 /// filtering candidates should not have to re-check bounds the matcher
107 /// already knows.
108 pub fn add_edge(&mut self, left: usize, right: usize) {
109 self.add_scored_edge(left, right, 0);
110 }
111
112 /// Add an edge with a preference score. Higher is tried first.
113 ///
114 /// The score cannot change how *many* layers get placed — see the module
115 /// documentation.
116 pub fn add_scored_edge(&mut self, left: usize, right: usize, score: i32) {
117 if left >= self.n_left || right >= self.n_right {
118 return;
119 }
120 self.adj[left].push(Edge { right, score });
121 }
122
123 /// Compute the maximum-cardinality matching, returning how many pairs it
124 /// found.
125 pub fn solve(&mut self) -> usize {
126 self.matched = 0;
127 for edges in &mut self.match_left {
128 *edges = None;
129 }
130 for edges in &mut self.match_right {
131 *edges = None;
132 }
133
134 // Sort each adjacency list by descending score so the DFS tries the
135 // caller's preferred planes first. A stable sort keeps insertion order
136 // among equal scores, which makes the result deterministic. Without
137 // this, Hopcroft-Karp still finds a maximum matching but pairs
138 // arbitrarily -- wrong when the caller expressed a preference.
139 for edges in &mut self.adj {
140 edges.sort_by(|a, b| b.score.cmp(&a.score));
141 }
142
143 while self.bfs() {
144 for u in 0..self.n_left {
145 if self.match_left[u].is_none() && self.dfs(u) {
146 self.matched += 1;
147 }
148 }
149 }
150 self.matched
151 }
152
153 /// Build the BFS layering. Returns whether an augmenting path exists.
154 fn bfs(&mut self) -> bool {
155 let sentinel = self.n_left;
156 let mut queue = VecDeque::with_capacity(self.n_left);
157
158 for u in 0..self.n_left {
159 if self.match_left[u].is_none() {
160 self.dist[u] = Some(0);
161 queue.push_back(u);
162 } else {
163 self.dist[u] = None; // infinity
164 }
165 }
166 self.dist[sentinel] = None;
167
168 while let Some(u) = queue.pop_front() {
169 // Only expand nodes closer than the best free right node found so
170 // far; `None` at the sentinel means none has been reached yet.
171 let closer = match (self.dist[u], self.dist[sentinel]) {
172 (Some(_), None) => true,
173 (Some(du), Some(ds)) => du < ds,
174 (None, _) => false,
175 };
176 if !closer {
177 continue;
178 }
179 let Some(du) = self.dist[u] else { continue };
180
181 for index in 0..self.adj[u].len() {
182 let v = self.adj[u][index].right;
183 let next = self.match_right[v].unwrap_or(sentinel);
184 if self.dist[next].is_none() {
185 self.dist[next] = Some(du + 1);
186 if next != sentinel {
187 queue.push_back(next);
188 }
189 }
190 }
191 }
192
193 self.dist[sentinel].is_some()
194 }
195
196 /// Walk one augmenting path from left node `u`.
197 ///
198 /// Recursion depth is bounded by the number of left nodes: each step moves
199 /// to a strictly deeper BFS layer, and there are at most `n_left + 1` of
200 /// them. With layer counts in the single digits this cannot approach the
201 /// stack limit.
202 fn dfs(&mut self, u: usize) -> bool {
203 let sentinel = self.n_left;
204 if u == sentinel {
205 return true; // reached a free right node
206 }
207
208 let Some(du) = self.dist[u] else {
209 return false;
210 };
211
212 for index in 0..self.adj[u].len() {
213 let v = self.adj[u][index].right;
214 let next = self.match_right[v].unwrap_or(sentinel);
215 if self.dist[next] == Some(du + 1) && self.dfs(next) {
216 self.match_right[v] = Some(u);
217 self.match_left[u] = Some(v);
218 return true;
219 }
220 }
221
222 self.dist[u] = None; // exhausted; do not revisit this round
223 false
224 }
225
226 /// The plane matched to a layer, after [`solve`](Self::solve).
227 #[must_use]
228 pub fn match_for_left(&self, left: usize) -> Option<usize> {
229 self.match_left.get(left).copied().flatten()
230 }
231
232 /// The layer matched to a plane, after [`solve`](Self::solve).
233 #[must_use]
234 pub fn match_for_right(&self, right: usize) -> Option<usize> {
235 self.match_right.get(right).copied().flatten()
236 }
237
238 /// How many pairs the last [`solve`](Self::solve) found.
239 #[must_use]
240 pub const fn matched_count(&self) -> usize {
241 self.matched
242 }
243
244 /// The number of left nodes.
245 #[must_use]
246 pub const fn left_len(&self) -> usize {
247 self.n_left
248 }
249
250 /// The number of right nodes.
251 #[must_use]
252 pub const fn right_len(&self) -> usize {
253 self.n_right
254 }
255}