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