1 use std::collections::VecDeque;
2 use std::hash::Hash;
3
4 use crate::visit::{
5 EdgeRef, GraphBase, IntoEdges, IntoNeighbors, IntoNodeIdentifiers, NodeCount, NodeIndexable,
6 VisitMap, Visitable,
7 };
8
9 /// Computed
10 /// [*matching*](https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definitions)
11 /// of the graph.
12 pub struct Matching<G: GraphBase> {
13 graph: G,
14 mate: Vec<Option<G::NodeId>>,
15 n_edges: usize,
16 }
17
18 impl<G> Matching<G>
19 where
20 G: GraphBase,
21 {
new(graph: G, mate: Vec<Option<G::NodeId>>, n_edges: usize) -> Self22 fn new(graph: G, mate: Vec<Option<G::NodeId>>, n_edges: usize) -> Self {
23 Self {
24 graph,
25 mate,
26 n_edges,
27 }
28 }
29 }
30
31 impl<G> Matching<G>
32 where
33 G: NodeIndexable,
34 {
35 /// Gets the matched counterpart of given node, if there is any.
36 ///
37 /// Returns `None` if the node is not matched or does not exist.
mate(&self, node: G::NodeId) -> Option<G::NodeId>38 pub fn mate(&self, node: G::NodeId) -> Option<G::NodeId> {
39 self.mate.get(self.graph.to_index(node)).and_then(|&id| id)
40 }
41
42 /// Iterates over all edges from the matching.
43 ///
44 /// An edge is represented by its endpoints. The graph is considered
45 /// undirected and every pair of matched nodes is reported only once.
edges(&self) -> MatchedEdges<'_, G>46 pub fn edges(&self) -> MatchedEdges<'_, G> {
47 MatchedEdges {
48 graph: &self.graph,
49 mate: self.mate.as_slice(),
50 current: 0,
51 }
52 }
53
54 /// Iterates over all nodes from the matching.
nodes(&self) -> MatchedNodes<'_, G>55 pub fn nodes(&self) -> MatchedNodes<'_, G> {
56 MatchedNodes {
57 graph: &self.graph,
58 mate: self.mate.as_slice(),
59 current: 0,
60 }
61 }
62
63 /// Returns `true` if given edge is in the matching, or `false` otherwise.
64 ///
65 /// If any of the nodes does not exist, `false` is returned.
contains_edge(&self, a: G::NodeId, b: G::NodeId) -> bool66 pub fn contains_edge(&self, a: G::NodeId, b: G::NodeId) -> bool {
67 match self.mate(a) {
68 Some(mate) => mate == b,
69 None => false,
70 }
71 }
72
73 /// Returns `true` if given node is in the matching, or `false` otherwise.
74 ///
75 /// If the node does not exist, `false` is returned.
contains_node(&self, node: G::NodeId) -> bool76 pub fn contains_node(&self, node: G::NodeId) -> bool {
77 self.mate(node).is_some()
78 }
79
80 /// Gets the number of matched **edges**.
len(&self) -> usize81 pub fn len(&self) -> usize {
82 self.n_edges
83 }
84
85 /// Returns `true` if the number of matched **edges** is 0.
is_empty(&self) -> bool86 pub fn is_empty(&self) -> bool {
87 self.len() == 0
88 }
89 }
90
91 impl<G> Matching<G>
92 where
93 G: NodeCount,
94 {
95 /// Returns `true` if the matching is perfect.
96 ///
97 /// A matching is
98 /// [*perfect*](https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definitions)
99 /// if every node in the graph is incident to an edge from the matching.
is_perfect(&self) -> bool100 pub fn is_perfect(&self) -> bool {
101 let n_nodes = self.graph.node_count();
102 n_nodes % 2 == 0 && self.n_edges == n_nodes / 2
103 }
104 }
105
106 trait WithDummy: NodeIndexable {
dummy_idx(&self) -> usize107 fn dummy_idx(&self) -> usize;
node_bound_with_dummy(&self) -> usize108 fn node_bound_with_dummy(&self) -> usize;
109 /// Convert `i` to a node index, returns None for the dummy node
try_from_index(&self, i: usize) -> Option<Self::NodeId>110 fn try_from_index(&self, i: usize) -> Option<Self::NodeId>;
111 }
112
113 impl<G: NodeIndexable> WithDummy for G {
dummy_idx(&self) -> usize114 fn dummy_idx(&self) -> usize {
115 // Gabow numbers the vertices from 1 to n, and uses 0 as the dummy
116 // vertex. Our vertex indices are zero-based and so we use the node
117 // bound as the dummy node.
118 self.node_bound()
119 }
120
node_bound_with_dummy(&self) -> usize121 fn node_bound_with_dummy(&self) -> usize {
122 self.node_bound() + 1
123 }
124
try_from_index(&self, i: usize) -> Option<Self::NodeId>125 fn try_from_index(&self, i: usize) -> Option<Self::NodeId> {
126 if i != self.dummy_idx() {
127 Some(self.from_index(i))
128 } else {
129 None
130 }
131 }
132 }
133
134 pub struct MatchedNodes<'a, G: GraphBase> {
135 graph: &'a G,
136 mate: &'a [Option<G::NodeId>],
137 current: usize,
138 }
139
140 impl<G> Iterator for MatchedNodes<'_, G>
141 where
142 G: NodeIndexable,
143 {
144 type Item = G::NodeId;
145
next(&mut self) -> Option<Self::Item>146 fn next(&mut self) -> Option<Self::Item> {
147 while self.current != self.mate.len() {
148 let current = self.current;
149 self.current += 1;
150
151 if self.mate[current].is_some() {
152 return Some(self.graph.from_index(current));
153 }
154 }
155
156 None
157 }
158 }
159
160 pub struct MatchedEdges<'a, G: GraphBase> {
161 graph: &'a G,
162 mate: &'a [Option<G::NodeId>],
163 current: usize,
164 }
165
166 impl<G> Iterator for MatchedEdges<'_, G>
167 where
168 G: NodeIndexable,
169 {
170 type Item = (G::NodeId, G::NodeId);
171
next(&mut self) -> Option<Self::Item>172 fn next(&mut self) -> Option<Self::Item> {
173 while self.current != self.mate.len() {
174 let current = self.current;
175 self.current += 1;
176
177 if let Some(mate) = self.mate[current] {
178 // Check if the mate is a node after the current one. If not, then
179 // do not report that edge since it has been already reported (the
180 // graph is considered undirected).
181 if self.graph.to_index(mate) > current {
182 let this = self.graph.from_index(current);
183 return Some((this, mate));
184 }
185 }
186 }
187
188 None
189 }
190 }
191
192 /// \[Generic\] Compute a
193 /// [*matching*](https://en.wikipedia.org/wiki/Matching_(graph_theory)) using a
194 /// greedy heuristic.
195 ///
196 /// The input graph is treated as if undirected. The underlying heuristic is
197 /// unspecified, but is guaranteed to be bounded by *O(|V| + |E|)*. No
198 /// guarantees about the output are given other than that it is a valid
199 /// matching.
200 ///
201 /// If you require a maximum matching, use [`maximum_matching`][1] function
202 /// instead.
203 ///
204 /// [1]: fn.maximum_matching.html
greedy_matching<G>(graph: G) -> Matching<G> where G: Visitable + IntoNodeIdentifiers + NodeIndexable + IntoNeighbors, G::NodeId: Eq + Hash, G::EdgeId: Eq + Hash,205 pub fn greedy_matching<G>(graph: G) -> Matching<G>
206 where
207 G: Visitable + IntoNodeIdentifiers + NodeIndexable + IntoNeighbors,
208 G::NodeId: Eq + Hash,
209 G::EdgeId: Eq + Hash,
210 {
211 let (mates, n_edges) = greedy_matching_inner(&graph);
212 Matching::new(graph, mates, n_edges)
213 }
214
215 #[inline]
greedy_matching_inner<G>(graph: &G) -> (Vec<Option<G::NodeId>>, usize) where G: Visitable + IntoNodeIdentifiers + NodeIndexable + IntoNeighbors,216 fn greedy_matching_inner<G>(graph: &G) -> (Vec<Option<G::NodeId>>, usize)
217 where
218 G: Visitable + IntoNodeIdentifiers + NodeIndexable + IntoNeighbors,
219 {
220 let mut mate = vec![None; graph.node_bound()];
221 let mut n_edges = 0;
222 let visited = &mut graph.visit_map();
223
224 for start in graph.node_identifiers() {
225 let mut last = Some(start);
226
227 // Function non_backtracking_dfs does not expand the node if it has been
228 // already visited.
229 non_backtracking_dfs(graph, start, visited, |next| {
230 // Alternate matched and unmatched edges.
231 if let Some(pred) = last.take() {
232 mate[graph.to_index(pred)] = Some(next);
233 mate[graph.to_index(next)] = Some(pred);
234 n_edges += 1;
235 } else {
236 last = Some(next);
237 }
238 });
239 }
240
241 (mate, n_edges)
242 }
243
non_backtracking_dfs<G, F>(graph: &G, source: G::NodeId, visited: &mut G::Map, mut visitor: F) where G: Visitable + IntoNeighbors, F: FnMut(G::NodeId),244 fn non_backtracking_dfs<G, F>(graph: &G, source: G::NodeId, visited: &mut G::Map, mut visitor: F)
245 where
246 G: Visitable + IntoNeighbors,
247 F: FnMut(G::NodeId),
248 {
249 if visited.visit(source) {
250 for target in graph.neighbors(source) {
251 if !visited.is_visited(&target) {
252 visitor(target);
253 non_backtracking_dfs(graph, target, visited, visitor);
254
255 // Non-backtracking traversal, stop iterating over the
256 // neighbors.
257 break;
258 }
259 }
260 }
261 }
262
263 #[derive(Clone, Copy)]
264 enum Label<G: GraphBase> {
265 None,
266 Start,
267 // If node v is outer node, then label(v) = w is another outer node on path
268 // from v to start u.
269 Vertex(G::NodeId),
270 // If node v is outer node, then label(v) = (r, s) are two outer vertices
271 // (connected by an edge)
272 Edge(G::EdgeId, [G::NodeId; 2]),
273 // Flag is a special label used in searching for the join vertex of two
274 // paths.
275 Flag(G::EdgeId),
276 }
277
278 impl<G: GraphBase> Label<G> {
is_outer(&self) -> bool279 fn is_outer(&self) -> bool {
280 self != &Label::None
281 && !match self {
282 Label::Flag(_) => true,
283 _ => false,
284 }
285 }
286
is_inner(&self) -> bool287 fn is_inner(&self) -> bool {
288 !self.is_outer()
289 }
290
to_vertex(&self) -> Option<G::NodeId>291 fn to_vertex(&self) -> Option<G::NodeId> {
292 match *self {
293 Label::Vertex(v) => Some(v),
294 _ => None,
295 }
296 }
297
is_flagged(&self, edge: G::EdgeId) -> bool298 fn is_flagged(&self, edge: G::EdgeId) -> bool {
299 match self {
300 Label::Flag(flag) if flag == &edge => true,
301 _ => false,
302 }
303 }
304 }
305
306 impl<G: GraphBase> Default for Label<G> {
default() -> Self307 fn default() -> Self {
308 Label::None
309 }
310 }
311
312 impl<G: GraphBase> PartialEq for Label<G> {
eq(&self, other: &Self) -> bool313 fn eq(&self, other: &Self) -> bool {
314 match (self, other) {
315 (Label::None, Label::None) => true,
316 (Label::Start, Label::Start) => true,
317 (Label::Vertex(v1), Label::Vertex(v2)) => v1 == v2,
318 (Label::Edge(e1, _), Label::Edge(e2, _)) => e1 == e2,
319 (Label::Flag(e1), Label::Flag(e2)) => e1 == e2,
320 _ => false,
321 }
322 }
323 }
324
325 /// \[Generic\] Compute the [*maximum
326 /// matching*](https://en.wikipedia.org/wiki/Matching_(graph_theory)) using
327 /// [Gabow's algorithm][1].
328 ///
329 /// [1]: https://dl.acm.org/doi/10.1145/321941.321942
330 ///
331 /// The input graph is treated as if undirected. The algorithm runs in
332 /// *O(|V|³)*. An algorithm with a better time complexity might be used in the
333 /// future.
334 ///
335 /// **Panics** if `g.node_bound()` is `std::usize::MAX`.
336 ///
337 /// # Examples
338 ///
339 /// ```
340 /// use petgraph::prelude::*;
341 /// use petgraph::algo::maximum_matching;
342 ///
343 /// // The example graph:
344 /// //
345 /// // +-- b ---- d ---- f
346 /// // / | |
347 /// // a | |
348 /// // \ | |
349 /// // +-- c ---- e
350 /// //
351 /// // Maximum matching: { (a, b), (c, e), (d, f) }
352 ///
353 /// let mut graph: UnGraph<(), ()> = UnGraph::new_undirected();
354 /// let a = graph.add_node(());
355 /// let b = graph.add_node(());
356 /// let c = graph.add_node(());
357 /// let d = graph.add_node(());
358 /// let e = graph.add_node(());
359 /// let f = graph.add_node(());
360 /// graph.extend_with_edges(&[(a, b), (a, c), (b, c), (b, d), (c, e), (d, e), (d, f)]);
361 ///
362 /// let matching = maximum_matching(&graph);
363 /// assert!(matching.contains_edge(a, b));
364 /// assert!(matching.contains_edge(c, e));
365 /// assert_eq!(matching.mate(d), Some(f));
366 /// assert_eq!(matching.mate(f), Some(d));
367 /// ```
maximum_matching<G>(graph: G) -> Matching<G> where G: Visitable + NodeIndexable + IntoNodeIdentifiers + IntoEdges,368 pub fn maximum_matching<G>(graph: G) -> Matching<G>
369 where
370 G: Visitable + NodeIndexable + IntoNodeIdentifiers + IntoEdges,
371 {
372 // The dummy identifier needs an unused index
373 assert_ne!(
374 graph.node_bound(),
375 std::usize::MAX,
376 "The input graph capacity should be strictly less than std::usize::MAX."
377 );
378
379 // Greedy algorithm should create a fairly good initial matching. The hope
380 // is that it speeds up the computation by doing les work in the complex
381 // algorithm.
382 let (mut mate, mut n_edges) = greedy_matching_inner(&graph);
383
384 // Gabow's algorithm uses a dummy node in the mate array.
385 mate.push(None);
386 let len = graph.node_bound() + 1;
387 debug_assert_eq!(mate.len(), len);
388
389 let mut label: Vec<Label<G>> = vec![Label::None; len];
390 let mut first_inner = vec![std::usize::MAX; len];
391 let visited = &mut graph.visit_map();
392
393 for start in 0..graph.node_bound() {
394 if mate[start].is_some() {
395 // The vertex is already matched. A start must be a free vertex.
396 continue;
397 }
398
399 // Begin search from the node.
400 label[start] = Label::Start;
401 first_inner[start] = graph.dummy_idx();
402 graph.reset_map(visited);
403
404 // start is never a dummy index
405 let start = graph.from_index(start);
406
407 // Queue will contain outer vertices that should be processed next. The
408 // start vertex is considered an outer vertex.
409 let mut queue = VecDeque::new();
410 queue.push_back(start);
411 // Mark the start vertex so it is not processed repeatedly.
412 visited.visit(start);
413
414 'search: while let Some(outer_vertex) = queue.pop_front() {
415 for edge in graph.edges(outer_vertex) {
416 if edge.source() == edge.target() {
417 // Ignore self-loops.
418 continue;
419 }
420
421 let other_vertex = edge.target();
422 let other_idx = graph.to_index(other_vertex);
423
424 if mate[other_idx].is_none() && other_vertex != start {
425 // An augmenting path was found. Augment the matching. If
426 // `other` is actually the start node, then the augmentation
427 // must not be performed, because the start vertex would be
428 // incident to two edges, which violates the matching
429 // property.
430 mate[other_idx] = Some(outer_vertex);
431 augment_path(&graph, outer_vertex, other_vertex, &mut mate, &label);
432 n_edges += 1;
433
434 // The path is augmented, so the start is no longer free
435 // vertex. We need to begin with a new start.
436 break 'search;
437 } else if label[other_idx].is_outer() {
438 // The `other` is an outer vertex (a label has been set to
439 // it). An odd cycle (blossom) was found. Assign this edge
440 // as a label to all inner vertices in paths P(outer) and
441 // P(other).
442 find_join(
443 &graph,
444 edge,
445 &mate,
446 &mut label,
447 &mut first_inner,
448 |labeled| {
449 if visited.visit(labeled) {
450 queue.push_back(labeled);
451 }
452 },
453 );
454 } else {
455 let mate_vertex = mate[other_idx];
456 let mate_idx = mate_vertex.map_or(graph.dummy_idx(), |id| graph.to_index(id));
457
458 if label[mate_idx].is_inner() {
459 // Mate of `other` vertex is inner (no label has been
460 // set to it so far). But it actually is an outer vertex
461 // (it is on a path to the start vertex that begins with
462 // a matched edge, since it is a mate of `other`).
463 // Assign the label of this mate to the `outer` vertex,
464 // so the path for it can be reconstructed using `mate`
465 // and this label.
466 label[mate_idx] = Label::Vertex(outer_vertex);
467 first_inner[mate_idx] = other_idx;
468 }
469
470 // Add the vertex to the queue only if it's not the dummy and this is its first
471 // discovery.
472 if let Some(mate_vertex) = mate_vertex {
473 if visited.visit(mate_vertex) {
474 queue.push_back(mate_vertex);
475 }
476 }
477 }
478 }
479 }
480
481 // Reset the labels. All vertices are inner for the next search.
482 for lbl in label.iter_mut() {
483 *lbl = Label::None;
484 }
485 }
486
487 // Discard the dummy node.
488 mate.pop();
489
490 Matching::new(graph, mate, n_edges)
491 }
492
find_join<G, F>( graph: &G, edge: G::EdgeRef, mate: &[Option<G::NodeId>], label: &mut [Label<G>], first_inner: &mut [usize], mut visitor: F, ) where G: IntoEdges + NodeIndexable + Visitable, F: FnMut(G::NodeId),493 fn find_join<G, F>(
494 graph: &G,
495 edge: G::EdgeRef,
496 mate: &[Option<G::NodeId>],
497 label: &mut [Label<G>],
498 first_inner: &mut [usize],
499 mut visitor: F,
500 ) where
501 G: IntoEdges + NodeIndexable + Visitable,
502 F: FnMut(G::NodeId),
503 {
504 // Simultaneously traverse the inner vertices on paths P(source) and
505 // P(target) to find a join vertex - an inner vertex that is shared by these
506 // paths.
507 let source = graph.to_index(edge.source());
508 let target = graph.to_index(edge.target());
509
510 let mut left = first_inner[source];
511 let mut right = first_inner[target];
512
513 if left == right {
514 // No vertices can be labeled, since both paths already refer to a
515 // common vertex - the join.
516 return;
517 }
518
519 // Flag the (first) inner vertices. This ensures that they are assigned the
520 // join as their first inner vertex.
521 let flag = Label::Flag(edge.id());
522 label[left] = flag;
523 label[right] = flag;
524
525 // Find the join.
526 let join = loop {
527 // Swap the sides. Do not swap if the right side is already finished.
528 if right != graph.dummy_idx() {
529 std::mem::swap(&mut left, &mut right);
530 }
531
532 // Set left to the next inner vertex in P(source) or P(target).
533 // The unwraps are safe because left is not the dummy node.
534 let left_mate = graph.to_index(mate[left].unwrap());
535 let next_inner = label[left_mate].to_vertex().unwrap();
536 left = first_inner[graph.to_index(next_inner)];
537
538 if !label[left].is_flagged(edge.id()) {
539 // The inner vertex is not flagged yet, so flag it.
540 label[left] = flag;
541 } else {
542 // The inner vertex is already flagged. It means that the other side
543 // had to visit it already. Therefore it is the join vertex.
544 break left;
545 }
546 };
547
548 // Label all inner vertices on P(source) and P(target) with the found join.
549 for endpoint in [source, target].iter().copied() {
550 let mut inner = first_inner[endpoint];
551 while inner != join {
552 // Notify the caller about labeling a vertex.
553 if let Some(ix) = graph.try_from_index(inner) {
554 visitor(ix);
555 }
556
557 label[inner] = Label::Edge(edge.id(), [edge.source(), edge.target()]);
558 first_inner[inner] = join;
559 let inner_mate = graph.to_index(mate[inner].unwrap());
560 let next_inner = label[inner_mate].to_vertex().unwrap();
561 inner = first_inner[graph.to_index(next_inner)];
562 }
563 }
564
565 for (vertex_idx, vertex_label) in label.iter().enumerate() {
566 // To all outer vertices that are on paths P(source) and P(target) until
567 // the join, se the join as their first inner vertex.
568 if vertex_idx != graph.dummy_idx()
569 && vertex_label.is_outer()
570 && label[first_inner[vertex_idx]].is_outer()
571 {
572 first_inner[vertex_idx] = join;
573 }
574 }
575 }
576
augment_path<G>( graph: &G, outer: G::NodeId, other: G::NodeId, mate: &mut [Option<G::NodeId>], label: &[Label<G>], ) where G: NodeIndexable,577 fn augment_path<G>(
578 graph: &G,
579 outer: G::NodeId,
580 other: G::NodeId,
581 mate: &mut [Option<G::NodeId>],
582 label: &[Label<G>],
583 ) where
584 G: NodeIndexable,
585 {
586 let outer_idx = graph.to_index(outer);
587
588 let temp = mate[outer_idx];
589 let temp_idx = temp.map_or(graph.dummy_idx(), |id| graph.to_index(id));
590 mate[outer_idx] = Some(other);
591
592 if mate[temp_idx] != Some(outer) {
593 // We are at the end of the path and so the entire path is completely
594 // rematched/augmented.
595 } else if let Label::Vertex(vertex) = label[outer_idx] {
596 // The outer vertex has a vertex label which refers to another outer
597 // vertex on the path. So we set this another outer node as the mate for
598 // the previous mate of the outer node.
599 mate[temp_idx] = Some(vertex);
600 if let Some(temp) = temp {
601 augment_path(graph, vertex, temp, mate, label);
602 }
603 } else if let Label::Edge(_, [source, target]) = label[outer_idx] {
604 // The outer vertex has an edge label which refers to an edge in a
605 // blossom. We need to augment both directions along the blossom.
606 augment_path(graph, source, target, mate, label);
607 augment_path(graph, target, source, mate, label);
608 } else {
609 panic!("Unexpected label when augmenting path");
610 }
611 }
612