16 |
16 |
17 #ifndef LEMON_MAX_MATCHING_H |
17 #ifndef LEMON_MAX_MATCHING_H |
18 #define LEMON_MAX_MATCHING_H |
18 #define LEMON_MAX_MATCHING_H |
19 |
19 |
20 #include <queue> |
20 #include <queue> |
21 #include <invalid.h> |
21 #include <lemon/invalid.h> |
22 #include <unionfind.h> |
22 #include <lemon/unionfind.h> |
23 #include <lemon/graph_utils.h> |
23 #include <lemon/graph_utils.h> |
24 |
24 |
25 ///\ingroup galgs |
25 ///\ingroup galgs |
26 ///\file |
26 ///\file |
27 ///\brief Maximum matching algorithm. |
27 ///\brief Maximum matching algorithm. |
79 |
79 |
80 private: |
80 private: |
81 |
81 |
82 static const int HEUR_density=2; |
82 static const int HEUR_density=2; |
83 const Graph& g; |
83 const Graph& g; |
84 typename Graph::template NodeMap<Node> mate; |
84 typename Graph::template NodeMap<Node> _mate; |
85 typename Graph::template NodeMap<pos_enum> position; |
85 typename Graph::template NodeMap<pos_enum> position; |
86 |
86 |
87 public: |
87 public: |
88 |
88 |
89 MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g) {} |
89 MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {} |
90 |
90 |
91 ///Runs Edmonds' algorithm. |
91 ///Runs Edmonds' algorithm. |
92 |
92 |
93 ///Runs Edmonds' algorithm for sparse graphs (number of edges < |
93 ///Runs Edmonds' algorithm for sparse graphs (number of edges < |
94 ///2*number of nodes), and a heuristical Edmonds' algorithm with a |
94 ///2*number of nodes), and a heuristical Edmonds' algorithm with a |
117 ///Resets the actual matching to the empty matching. |
117 ///Resets the actual matching to the empty matching. |
118 |
118 |
119 ///Resets the actual matching to the empty matching. |
119 ///Resets the actual matching to the empty matching. |
120 /// |
120 /// |
121 void resetMatching(); |
121 void resetMatching(); |
|
122 |
|
123 ///Returns the mate of a node in the actual matching. |
|
124 |
|
125 ///Returns the mate of a \c node in the actual matching. |
|
126 ///Returns INVALID if the \c node is not covered by the actual matching. |
|
127 Node mate(Node& node) const { |
|
128 return _mate[node]; |
|
129 } |
122 |
130 |
123 ///Reads a matching from a \c Node map of \c Nodes. |
131 ///Reads a matching from a \c Node map of \c Nodes. |
124 |
132 |
125 ///Reads a matching from a \c Node map of \c Nodes. This map must be \e |
133 ///Reads a matching from a \c Node map of \c Nodes. This map must be \e |
126 ///symmetric, i.e. if \c map[u]==v then \c map[v]==u must hold, and |
134 ///symmetric, i.e. if \c map[u]==v then \c map[v]==u must hold, and |
127 ///\c uv will be an edge of the matching. |
135 ///\c uv will be an edge of the matching. |
128 template<typename NMapN> |
136 template<typename NMapN> |
129 void readNMapNode(NMapN& map) { |
137 void readNMapNode(NMapN& map) { |
130 for(NodeIt v(g); v!=INVALID; ++v) { |
138 for(NodeIt v(g); v!=INVALID; ++v) { |
131 mate.set(v,map[v]); |
139 _mate.set(v,map[v]); |
132 } |
140 } |
133 } |
141 } |
134 |
142 |
135 ///Writes the stored matching to a \c Node map of \c Nodes. |
143 ///Writes the stored matching to a \c Node map of \c Nodes. |
136 |
144 |
138 ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c |
146 ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c |
139 ///map[v]==u will hold, and now \c uv is an edge of the matching. |
147 ///map[v]==u will hold, and now \c uv is an edge of the matching. |
140 template<typename NMapN> |
148 template<typename NMapN> |
141 void writeNMapNode (NMapN& map) const { |
149 void writeNMapNode (NMapN& map) const { |
142 for(NodeIt v(g); v!=INVALID; ++v) { |
150 for(NodeIt v(g); v!=INVALID; ++v) { |
143 map.set(v,mate[v]); |
151 map.set(v,_mate[v]); |
144 } |
152 } |
145 } |
153 } |
146 |
154 |
147 ///Reads a matching from a \c Node map of \c Edges. |
155 ///Reads a matching from a \c Node map of \c Edges. |
148 |
156 |
153 template<typename NMapE> |
161 template<typename NMapE> |
154 void readNMapEdge(NMapE& map) { |
162 void readNMapEdge(NMapE& map) { |
155 for(NodeIt v(g); v!=INVALID; ++v) { |
163 for(NodeIt v(g); v!=INVALID; ++v) { |
156 Edge e=map[v]; |
164 Edge e=map[v]; |
157 if ( g.valid(e) ) |
165 if ( g.valid(e) ) |
158 g.source(e) == v ? mate.set(v,g.target(e)) : mate.set(v,g.source(e)); |
166 g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e)); |
159 } |
167 } |
160 } |
168 } |
161 |
169 |
162 ///Writes the matching stored to a \c Node map of \c Edges. |
170 ///Writes the matching stored to a \c Node map of \c Edges. |
163 |
171 |
167 ///edge is an edge of the matching. |
175 ///edge is an edge of the matching. |
168 template<typename NMapE> |
176 template<typename NMapE> |
169 void writeNMapEdge (NMapE& map) const { |
177 void writeNMapEdge (NMapE& map) const { |
170 typename Graph::template NodeMap<bool> todo(g,true); |
178 typename Graph::template NodeMap<bool> todo(g,true); |
171 for(NodeIt v(g); v!=INVALID; ++v) { |
179 for(NodeIt v(g); v!=INVALID; ++v) { |
172 if ( todo[v] && mate[v]!=INVALID ) { |
180 if ( todo[v] && _mate[v]!=INVALID ) { |
173 Node u=mate[v]; |
181 Node u=_mate[v]; |
174 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
182 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
175 if ( g.target(e) == u ) { |
183 if ( g.target(e) == u ) { |
176 map.set(u,e); |
184 map.set(u,e); |
177 map.set(v,e); |
185 map.set(v,e); |
178 todo.set(u,false); |
186 todo.set(u,false); |
214 void writeEMapBool (EMapB& map) const { |
222 void writeEMapBool (EMapB& map) const { |
215 for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false); |
223 for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false); |
216 |
224 |
217 typename Graph::template NodeMap<bool> todo(g,true); |
225 typename Graph::template NodeMap<bool> todo(g,true); |
218 for(NodeIt v(g); v!=INVALID; ++v) { |
226 for(NodeIt v(g); v!=INVALID; ++v) { |
219 if ( todo[v] && mate[v]!=INVALID ) { |
227 if ( todo[v] && _mate[v]!=INVALID ) { |
220 Node u=mate[v]; |
228 Node u=_mate[v]; |
221 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
229 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
222 if ( g.target(e) == u ) { |
230 if ( g.target(e) == u ) { |
223 map.set(e,true); |
231 map.set(e,true); |
224 todo.set(u,false); |
232 todo.set(u,false); |
225 todo.set(v,false); |
233 todo.set(v,false); |
290 UFE blossom(blossom_base); |
298 UFE blossom(blossom_base); |
291 typename UFE::MapType tree_base(g); |
299 typename UFE::MapType tree_base(g); |
292 UFE tree(tree_base); |
300 UFE tree(tree_base); |
293 |
301 |
294 for(NodeIt v(g); v!=INVALID; ++v) { |
302 for(NodeIt v(g); v!=INVALID; ++v) { |
295 if ( position[v]==C && mate[v]==INVALID ) { |
303 if ( position[v]==C && _mate[v]==INVALID ) { |
296 blossom.insert(v); |
304 blossom.insert(v); |
297 tree.insert(v); |
305 tree.insert(v); |
298 position.set(v,D); |
306 position.set(v,D); |
299 if ( heur == 1 ) lateShrink( v, ear, blossom, tree ); |
307 if ( heur == 1 ) lateShrink( v, ear, blossom, tree ); |
300 else normShrink( v, ear, blossom, tree ); |
308 else normShrink( v, ear, blossom, tree ); |
331 |
339 |
332 typename Graph::template NodeMap<bool> path(g,false); |
340 typename Graph::template NodeMap<bool> path(g,false); |
333 |
341 |
334 Node b=blossom.find(x); |
342 Node b=blossom.find(x); |
335 path.set(b,true); |
343 path.set(b,true); |
336 b=mate[b]; |
344 b=_mate[b]; |
337 while ( b!=INVALID ) { |
345 while ( b!=INVALID ) { |
338 b=blossom.find(ear[b]); |
346 b=blossom.find(ear[b]); |
339 path.set(b,true); |
347 path.set(b,true); |
340 b=mate[b]; |
348 b=_mate[b]; |
341 } //going till the root |
349 } //going till the root |
342 |
350 |
343 Node top=y; |
351 Node top=y; |
344 Node middle=blossom.find(top); |
352 Node middle=blossom.find(top); |
345 Node bottom=x; |
353 Node bottom=x; |
388 if ( blossom.find(x) != blossom.find(y) ) { //shrink |
396 if ( blossom.find(x) != blossom.find(y) ) { //shrink |
389 typename Graph::template NodeMap<bool> path(g,false); |
397 typename Graph::template NodeMap<bool> path(g,false); |
390 |
398 |
391 Node b=blossom.find(x); |
399 Node b=blossom.find(x); |
392 path.set(b,true); |
400 path.set(b,true); |
393 b=mate[b]; |
401 b=_mate[b]; |
394 while ( b!=INVALID ) { |
402 while ( b!=INVALID ) { |
395 b=blossom.find(ear[b]); |
403 b=blossom.find(ear[b]); |
396 path.set(b,true); |
404 path.set(b,true); |
397 b=mate[b]; |
405 b=_mate[b]; |
398 } //going till the root |
406 } //going till the root |
399 |
407 |
400 Node top=y; |
408 Node top=y; |
401 Node middle=blossom.find(top); |
409 Node middle=blossom.find(top); |
402 Node bottom=x; |
410 Node bottom=x; |
413 |
421 |
414 blossom.makeRep(base); |
422 blossom.makeRep(base); |
415 } |
423 } |
416 break; |
424 break; |
417 case C: |
425 case C: |
418 if ( mate[y]!=INVALID ) { //grow |
426 if ( _mate[y]!=INVALID ) { //grow |
419 |
427 |
420 ear.set(y,x); |
428 ear.set(y,x); |
421 Node w=mate[y]; |
429 Node w=_mate[y]; |
422 blossom.insert(w); |
430 blossom.insert(w); |
423 position.set(y,A); |
431 position.set(y,A); |
424 position.set(w,D); |
432 position.set(w,D); |
425 tree.insert(y); |
433 tree.insert(y); |
426 tree.insert(w); |
434 tree.insert(w); |
427 tree.join(y,blossom.find(x)); |
435 tree.join(y,blossom.find(x)); |
428 tree.join(w,y); |
436 tree.join(w,y); |
429 Q.push(w); |
437 Q.push(w); |
430 } else { //augment |
438 } else { //augment |
431 augment(x, ear, blossom, tree); |
439 augment(x, ear, blossom, tree); |
432 mate.set(x,y); |
440 _mate.set(x,y); |
433 mate.set(y,x); |
441 _mate.set(y,x); |
434 return; |
442 return; |
435 } //if |
443 } //if |
436 break; |
444 break; |
437 default: break; |
445 default: break; |
438 } |
446 } |
441 } |
449 } |
442 |
450 |
443 template <typename Graph> |
451 template <typename Graph> |
444 void MaxMatching<Graph>::greedyMatching() { |
452 void MaxMatching<Graph>::greedyMatching() { |
445 for(NodeIt v(g); v!=INVALID; ++v) |
453 for(NodeIt v(g); v!=INVALID; ++v) |
446 if ( mate[v]==INVALID ) { |
454 if ( _mate[v]==INVALID ) { |
447 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { |
455 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { |
448 Node y=g.target(e); |
456 Node y=g.target(e); |
449 if ( mate[y]==INVALID && y!=v ) { |
457 if ( _mate[y]==INVALID && y!=v ) { |
450 mate.set(v,y); |
458 _mate.set(v,y); |
451 mate.set(y,v); |
459 _mate.set(y,v); |
452 break; |
460 break; |
453 } |
461 } |
454 } |
462 } |
455 } |
463 } |
456 } |
464 } |
457 |
465 |
458 template <typename Graph> |
466 template <typename Graph> |
459 int MaxMatching<Graph>::size() const { |
467 int MaxMatching<Graph>::size() const { |
460 int s=0; |
468 int s=0; |
461 for(NodeIt v(g); v!=INVALID; ++v) { |
469 for(NodeIt v(g); v!=INVALID; ++v) { |
462 if ( mate[v]!=INVALID ) { |
470 if ( _mate[v]!=INVALID ) { |
463 ++s; |
471 ++s; |
464 } |
472 } |
465 } |
473 } |
466 return (int)s/2; |
474 return (int)s/2; |
467 } |
475 } |
468 |
476 |
469 template <typename Graph> |
477 template <typename Graph> |
470 void MaxMatching<Graph>::resetMatching() { |
478 void MaxMatching<Graph>::resetMatching() { |
471 for(NodeIt v(g); v!=INVALID; ++v) |
479 for(NodeIt v(g); v!=INVALID; ++v) |
472 mate.set(v,INVALID); |
480 _mate.set(v,INVALID); |
473 } |
481 } |
474 |
482 |
475 template <typename Graph> |
483 template <typename Graph> |
476 bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear, |
484 bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear, |
477 UFE& blossom, UFE& tree, std::queue<Node>& Q) { |
485 UFE& blossom, UFE& tree, std::queue<Node>& Q) { |
478 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
486 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
479 Node y=g.target(e); |
487 Node y=g.target(e); |
480 |
488 |
481 if ( position[y]==C ) { |
489 if ( position[y]==C ) { |
482 if ( mate[y]!=INVALID ) { //grow |
490 if ( _mate[y]!=INVALID ) { //grow |
483 ear.set(y,x); |
491 ear.set(y,x); |
484 Node w=mate[y]; |
492 Node w=_mate[y]; |
485 blossom.insert(w); |
493 blossom.insert(w); |
486 position.set(y,A); |
494 position.set(y,A); |
487 position.set(w,D); |
495 position.set(w,D); |
488 tree.insert(y); |
496 tree.insert(y); |
489 tree.insert(w); |
497 tree.insert(w); |
490 tree.join(y,blossom.find(x)); |
498 tree.join(y,blossom.find(x)); |
491 tree.join(w,y); |
499 tree.join(w,y); |
492 Q.push(w); |
500 Q.push(w); |
493 } else { //augment |
501 } else { //augment |
494 augment(x, ear, blossom, tree); |
502 augment(x, ear, blossom, tree); |
495 mate.set(x,y); |
503 _mate.set(x,y); |
496 mate.set(y,x); |
504 _mate.set(y,x); |
497 return true; |
505 return true; |
498 } |
506 } |
499 } |
507 } |
500 } |
508 } |
501 return false; |
509 return false; |
505 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear, |
513 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear, |
506 UFE& blossom, UFE& tree, std::queue<Node>& Q) { |
514 UFE& blossom, UFE& tree, std::queue<Node>& Q) { |
507 ear.set(top,bottom); |
515 ear.set(top,bottom); |
508 Node t=top; |
516 Node t=top; |
509 while ( t!=middle ) { |
517 while ( t!=middle ) { |
510 Node u=mate[t]; |
518 Node u=_mate[t]; |
511 t=ear[u]; |
519 t=ear[u]; |
512 ear.set(t,u); |
520 ear.set(t,u); |
513 } |
521 } |
514 bottom=mate[middle]; |
522 bottom=_mate[middle]; |
515 position.set(bottom,D); |
523 position.set(bottom,D); |
516 Q.push(bottom); |
524 Q.push(bottom); |
517 top=ear[bottom]; |
525 top=ear[bottom]; |
518 Node oldmiddle=middle; |
526 Node oldmiddle=middle; |
519 middle=blossom.find(top); |
527 middle=blossom.find(top); |
525 } |
533 } |
526 |
534 |
527 template <typename Graph> |
535 template <typename Graph> |
528 void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear, |
536 void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear, |
529 UFE& blossom, UFE& tree) { |
537 UFE& blossom, UFE& tree) { |
530 Node v=mate[x]; |
538 Node v=_mate[x]; |
531 while ( v!=INVALID ) { |
539 while ( v!=INVALID ) { |
532 |
540 |
533 Node u=ear[v]; |
541 Node u=ear[v]; |
534 mate.set(v,u); |
542 _mate.set(v,u); |
535 Node tmp=v; |
543 Node tmp=v; |
536 v=mate[u]; |
544 v=_mate[u]; |
537 mate.set(u,tmp); |
545 _mate.set(u,tmp); |
538 } |
546 } |
539 typename UFE::ItemIt it; |
547 typename UFE::ItemIt it; |
540 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) { |
548 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) { |
541 if ( position[it] == D ) { |
549 if ( position[it] == D ) { |
542 typename UFE::ItemIt b_it; |
550 typename UFE::ItemIt b_it; |