@@ -11,15 +11,15 @@ use super::visit::{
1111/// of the graph.
1212pub struct Matching < G : GraphBase > {
1313 graph : G ,
14- mate : Vec < G :: NodeId > ,
14+ mate : Vec < Option < G :: NodeId > > ,
1515 n_edges : usize ,
1616}
1717
1818impl < G > Matching < G >
1919where
2020 G : GraphBase ,
2121{
22- fn new ( graph : G , mate : Vec < G :: NodeId > , n_edges : usize ) -> Self {
22+ fn new ( graph : G , mate : Vec < Option < G :: NodeId > > , n_edges : usize ) -> Self {
2323 Self {
2424 graph,
2525 mate,
3636 ///
3737 /// Returns `None` if the node is not matched or does not exist.
3838 pub fn mate ( & self , node : G :: NodeId ) -> Option < G :: NodeId > {
39- self . mate . get ( self . graph . to_index ( node) ) . and_then ( |& mate| {
40- if mate != self . graph . dummy ( ) {
41- Some ( mate)
42- } else {
43- None
44- }
45- } )
39+ self . mate . get ( self . graph . to_index ( node) ) . and_then ( |& id| id)
4640 }
4741
4842 /// Iterates over all edges from the matching.
@@ -105,16 +99,13 @@ where
10599}
106100
107101trait WithDummy : NodeIndexable {
108- fn dummy ( & self ) -> Self :: NodeId ;
109102 fn dummy_idx ( & self ) -> usize ;
110103 fn node_bound_with_dummy ( & self ) -> usize ;
104+ /// Convert `i` to a node index, returns None for the dummy node
105+ fn try_from_index ( self : & Self , i : usize ) -> Option < Self :: NodeId > ;
111106}
112107
113108impl < G : NodeIndexable > WithDummy for G {
114- fn dummy ( & self ) -> Self :: NodeId {
115- self . from_index ( self . dummy_idx ( ) )
116- }
117-
118109 fn dummy_idx ( & self ) -> usize {
119110 // Gabow numbers the vertices from 1 to n, and uses 0 as the dummy
120111 // vertex. Our vertex indices are zero-based and so we use the node
@@ -125,11 +116,19 @@ impl<G: NodeIndexable> WithDummy for G {
125116 fn node_bound_with_dummy ( & self ) -> usize {
126117 self . node_bound ( ) + 1
127118 }
119+
120+ fn try_from_index ( self : & Self , i : usize ) -> Option < Self :: NodeId > {
121+ if i != self . dummy_idx ( ) {
122+ Some ( self . from_index ( i) )
123+ } else {
124+ None
125+ }
126+ }
128127}
129128
130129pub struct MatchedNodes < ' a , G : GraphBase > {
131130 graph : & ' a G ,
132- mate : & ' a [ G :: NodeId ] ,
131+ mate : & ' a [ Option < G :: NodeId > ] ,
133132 current : usize ,
134133}
135134
@@ -144,7 +143,7 @@ where
144143 let current = self . current ;
145144 self . current += 1 ;
146145
147- if self . mate [ current] != self . graph . dummy ( ) {
146+ if self . mate [ current] . is_some ( ) {
148147 return Some ( self . graph . from_index ( current) ) ;
149148 }
150149 }
@@ -155,7 +154,7 @@ where
155154
156155pub struct MatchedEdges < ' a , G : GraphBase > {
157156 graph : & ' a G ,
158- mate : & ' a [ G :: NodeId ] ,
157+ mate : & ' a [ Option < G :: NodeId > ] ,
159158 current : usize ,
160159}
161160
@@ -170,14 +169,14 @@ where
170169 let current = self . current ;
171170 self . current += 1 ;
172171
173- let mate = self . mate [ current] ;
174-
175- // Check if the mate is a node after the current one. If not, then
176- // do not report that edge since it has been already reported (the
177- // graph is considered undirected).
178- if mate != self . graph . dummy ( ) && self . graph . to_index ( mate ) > current {
179- let this = self . graph . from_index ( current ) ;
180- return Some ( ( this , mate ) ) ;
172+ if let Some ( mate) = self . mate [ current] {
173+ // Check if the mate is a node after the current one. If not, then
174+ // do not report that edge since it has been already reported (the
175+ // graph is considered undirected).
176+ if self . graph . to_index ( mate ) > current {
177+ let this = self . graph . from_index ( current) ;
178+ return Some ( ( this , mate ) ) ;
179+ }
181180 }
182181 }
183182
@@ -204,15 +203,16 @@ where
204203 G :: NodeId : Eq + Hash ,
205204 G :: EdgeId : Eq + Hash ,
206205{
207- let ( mate , n_edges) = greedy_matching_inner ( & graph) ;
208- Matching :: new ( graph, mate , n_edges)
206+ let ( mates , n_edges) = greedy_matching_inner ( & graph) ;
207+ Matching :: new ( graph, mates , n_edges)
209208}
210209
211- fn greedy_matching_inner < G > ( graph : & G ) -> ( Vec < G :: NodeId > , usize )
210+ #[ inline]
211+ fn greedy_matching_inner < G > ( graph : & G ) -> ( Vec < Option < G :: NodeId > > , usize )
212212where
213213 G : Visitable + IntoNodeIdentifiers + NodeIndexable + IntoNeighbors ,
214214{
215- let mut mate = vec ! [ graph . dummy ( ) ; graph. node_bound( ) ] ;
215+ let mut mate = vec ! [ None ; graph. node_bound( ) ] ;
216216 let mut n_edges = 0 ;
217217 let visited = & mut graph. visit_map ( ) ;
218218
@@ -224,8 +224,8 @@ where
224224 non_backtracking_dfs ( graph, start, visited, |next| {
225225 // Alternate matched and unmatched edges.
226226 if let Some ( pred) = last. take ( ) {
227- mate[ graph. to_index ( pred) ] = next;
228- mate[ graph. to_index ( next) ] = pred;
227+ mate[ graph. to_index ( pred) ] = Some ( next) ;
228+ mate[ graph. to_index ( next) ] = Some ( pred) ;
229229 n_edges += 1 ;
230230 } else {
231231 last = Some ( next) ;
@@ -327,6 +327,8 @@ impl<G: GraphBase> PartialEq for Label<G> {
327327/// *O(|V|³)*. An algorithm with a better time complexity might be used in the
328328/// future.
329329///
330+ /// **Panics** if `g.node_bound()` is `std::usize::MAX`.
331+ ///
330332/// # Examples
331333///
332334/// ```
@@ -362,22 +364,29 @@ pub fn maximum_matching<G>(graph: G) -> Matching<G>
362364where
363365 G : Visitable + NodeIndexable + IntoNodeIdentifiers + IntoEdges ,
364366{
367+ // The dummy identifier needs an unused index
368+ assert_ne ! (
369+ graph. node_bound( ) ,
370+ std:: usize :: MAX ,
371+ "The input graph capacity should be strictly less than std::usize::MAX."
372+ ) ;
373+
365374 // Greedy algorithm should create a fairly good initial matching. The hope
366375 // is that it speeds up the computation by doing les work in the complex
367376 // algorithm.
368377 let ( mut mate, mut n_edges) = greedy_matching_inner ( & graph) ;
369378
370379 // Gabow's algorithm uses a dummy node in the mate array.
371- mate. push ( graph. dummy ( ) ) ;
372-
373- let len = graph. node_bound_with_dummy ( ) ;
380+ mate. push ( None ) ;
381+ let len = graph. node_bound ( ) + 1 ;
374382 debug_assert_eq ! ( mate. len( ) , len) ;
383+
375384 let mut label: Vec < Label < G > > = vec ! [ Label :: None ; len] ;
376385 let mut first_inner = vec ! [ std:: usize :: MAX ; len] ;
377386 let visited = & mut graph. visit_map ( ) ;
378387
379388 for start in 0 ..graph. node_bound ( ) {
380- if mate[ start] != graph . dummy ( ) {
389+ if mate[ start] . is_some ( ) {
381390 // The vertex is already matched. A start must be a free vertex.
382391 continue ;
383392 }
@@ -387,6 +396,7 @@ where
387396 first_inner[ start] = graph. dummy_idx ( ) ;
388397 graph. reset_map ( visited) ;
389398
399+ // start is never a dummy index
390400 let start = graph. from_index ( start) ;
391401
392402 // Queue will contain outer vertices that should be processed next. The
@@ -406,13 +416,13 @@ where
406416 let other_vertex = edge. target ( ) ;
407417 let other_idx = graph. to_index ( other_vertex) ;
408418
409- if mate[ other_idx] == graph . dummy ( ) && other_vertex != start {
419+ if mate[ other_idx] . is_none ( ) && other_vertex != start {
410420 // An augmenting path was found. Augment the matching. If
411421 // `other` is actually the start node, then the augmentation
412422 // must not be performed, because the start vertex would be
413423 // incident to two edges, which violates the matching
414424 // property.
415- mate[ other_idx] = outer_vertex;
425+ mate[ other_idx] = Some ( outer_vertex) ;
416426 augment_path ( & graph, outer_vertex, other_vertex, & mut mate, & label) ;
417427 n_edges += 1 ;
418428
@@ -438,7 +448,7 @@ where
438448 ) ;
439449 } else {
440450 let mate_vertex = mate[ other_idx] ;
441- let mate_idx = graph. to_index ( mate_vertex ) ;
451+ let mate_idx = mate_vertex . map_or ( graph. dummy_idx ( ) , |id| graph . to_index ( id ) ) ;
442452
443453 if label[ mate_idx] . is_inner ( ) {
444454 // Mate of `other` vertex is inner (no label has been
@@ -452,10 +462,12 @@ where
452462 first_inner[ mate_idx] = other_idx;
453463 }
454464
455- if visited. visit ( mate_vertex) {
456- // Add the vertex to the queue only if this is its first
457- // discovery.
458- queue. push_back ( mate_vertex) ;
465+ // Add the vertex to the queue only if it's not the dummy and this is its first
466+ // discovery.
467+ if let Some ( mate_vertex) = mate_vertex {
468+ if visited. visit ( mate_vertex) {
469+ queue. push_back ( mate_vertex) ;
470+ }
459471 }
460472 }
461473 }
@@ -476,7 +488,7 @@ where
476488fn find_join < G , F > (
477489 graph : & G ,
478490 edge : G :: EdgeRef ,
479- mate : & Vec < G :: NodeId > ,
491+ mate : & Vec < Option < G :: NodeId > > ,
480492 label : & mut Vec < Label < G > > ,
481493 first_inner : & mut Vec < usize > ,
482494 mut visitor : F ,
@@ -513,7 +525,10 @@ fn find_join<G, F>(
513525 }
514526
515527 // Set left to the next inner vertex in P(source) or P(target).
516- left = first_inner[ graph. to_index ( label[ graph. to_index ( mate[ left] ) ] . to_vertex ( ) . unwrap ( ) ) ] ;
528+ // The unwraps are safe because left is not the dummy node.
529+ let left_mate = graph. to_index ( mate[ left] . unwrap ( ) ) ;
530+ let next_inner = label[ left_mate] . to_vertex ( ) . unwrap ( ) ;
531+ left = first_inner[ graph. to_index ( next_inner) ] ;
517532
518533 if !label[ left] . is_flagged ( edge. id ( ) ) {
519534 // The inner vertex is not flagged yet, so flag it.
@@ -530,12 +545,15 @@ fn find_join<G, F>(
530545 let mut inner = first_inner[ endpoint] ;
531546 while inner != join {
532547 // Notify the caller about labeling a vertex.
533- visitor ( graph. from_index ( inner) ) ;
548+ if let Some ( ix) = graph. try_from_index ( inner) {
549+ visitor ( ix) ;
550+ }
534551
535552 label[ inner] = Label :: Edge ( edge. id ( ) , [ edge. source ( ) , edge. target ( ) ] ) ;
536553 first_inner[ inner] = join;
537- inner = first_inner
538- [ graph. to_index ( label[ graph. to_index ( mate[ inner] ) ] . to_vertex ( ) . unwrap ( ) ) ] ;
554+ let inner_mate = graph. to_index ( mate[ inner] . unwrap ( ) ) ;
555+ let next_inner = label[ inner_mate] . to_vertex ( ) . unwrap ( ) ;
556+ inner = first_inner[ graph. to_index ( next_inner) ] ;
539557 }
540558 }
541559
@@ -555,27 +573,29 @@ fn augment_path<G>(
555573 graph : & G ,
556574 outer : G :: NodeId ,
557575 other : G :: NodeId ,
558- mate : & mut Vec < G :: NodeId > ,
576+ mate : & mut Vec < Option < G :: NodeId > > ,
559577 label : & Vec < Label < G > > ,
560578) where
561579 G : NodeIndexable ,
562580{
563581 let outer_idx = graph. to_index ( outer) ;
564582
565583 let temp = mate[ outer_idx] ;
566- let temp_idx = graph. to_index ( temp ) ;
567- mate[ outer_idx] = other;
584+ let temp_idx = temp . map_or ( graph. dummy_idx ( ) , |id| graph . to_index ( id ) ) ;
585+ mate[ outer_idx] = Some ( other) ;
568586
569- if mate[ temp_idx] != outer {
587+ if mate[ temp_idx] != Some ( outer) {
570588 // We are at the end of the path and so the entire path is completely
571589 // rematched/augmented.
572590 return ;
573591 } else if let Label :: Vertex ( vertex) = label[ outer_idx] {
574592 // The outer vertex has a vertex label which refers to another outer
575593 // vertex on the path. So we set this another outer node as the mate for
576594 // the previous mate of the outer node.
577- mate[ temp_idx] = vertex;
578- augment_path ( graph, vertex, temp, mate, label) ;
595+ mate[ temp_idx] = Some ( vertex) ;
596+ if let Some ( temp) = temp {
597+ augment_path ( graph, vertex, temp, mate, label) ;
598+ }
579599 } else if let Label :: Edge ( _, [ source, target] ) = label[ outer_idx] {
580600 // The outer vertex has an edge label which refers to an edge in a
581601 // blossom. We need to augment both directions along the blossom.
0 commit comments