00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_MAX_MATCHING_H
00020 #define LEMON_MAX_MATCHING_H
00021
00022 #include <queue>
00023 #include <lemon/invalid.h>
00024 #include <lemon/unionfind.h>
00025 #include <lemon/graph_utils.h>
00026
00030
00031 namespace lemon {
00032
00035
00037
00057 template <typename Graph>
00058 class MaxMatching {
00059
00060 protected:
00061
00062 typedef typename Graph::Node Node;
00063 typedef typename Graph::Edge Edge;
00064 typedef typename Graph::UEdge UEdge;
00065 typedef typename Graph::UEdgeIt UEdgeIt;
00066 typedef typename Graph::NodeIt NodeIt;
00067 typedef typename Graph::IncEdgeIt IncEdgeIt;
00068
00069 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
00070
00071 public:
00072
00074
00080 enum pos_enum {
00081 D=0,
00082 A=1,
00083 C=2
00084 };
00085
00086 protected:
00087
00088 static const int HEUR_density=2;
00089 const Graph& g;
00090 typename Graph::template NodeMap<Node> _mate;
00091 typename Graph::template NodeMap<pos_enum> position;
00092
00093 public:
00094
00095 MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
00096
00098
00102 void run() {
00103 if ( countUEdges(g) < HEUR_density*countNodes(g) ) {
00104 greedyMatching();
00105 runEdmonds(0);
00106 } else runEdmonds(1);
00107 }
00108
00109
00111
00115 void runEdmonds( int heur = 1 ) {
00116
00117 for(NodeIt v(g); v!=INVALID; ++v)
00118 position.set(v,C);
00119
00120 typename Graph::template NodeMap<Node> ear(g,INVALID);
00121
00122
00123
00124 typename UFE::MapType blossom_base(g);
00125 UFE blossom(blossom_base);
00126 typename UFE::MapType tree_base(g);
00127 UFE tree(tree_base);
00128
00129
00130
00131 for(NodeIt v(g); v!=INVALID; ++v) {
00132 if ( position[v]==C && _mate[v]==INVALID ) {
00133 blossom.insert(v);
00134 tree.insert(v);
00135 position.set(v,D);
00136 if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
00137 else normShrink( v, ear, blossom, tree );
00138 }
00139 }
00140 }
00141
00142
00144
00147 void greedyMatching() {
00148 for(NodeIt v(g); v!=INVALID; ++v)
00149 if ( _mate[v]==INVALID ) {
00150 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
00151 Node y=g.runningNode(e);
00152 if ( _mate[y]==INVALID && y!=v ) {
00153 _mate.set(v,y);
00154 _mate.set(y,v);
00155 break;
00156 }
00157 }
00158 }
00159 }
00160
00162
00165 int size() const {
00166 int s=0;
00167 for(NodeIt v(g); v!=INVALID; ++v) {
00168 if ( _mate[v]!=INVALID ) {
00169 ++s;
00170 }
00171 }
00172 return s/2;
00173 }
00174
00175
00177
00180 void resetMatching() {
00181 for(NodeIt v(g); v!=INVALID; ++v)
00182 _mate.set(v,INVALID);
00183 }
00184
00186
00189 Node mate(Node& node) const {
00190 return _mate[node];
00191 }
00192
00194
00198 template<typename NMapN>
00199 void readNMapNode(NMapN& map) {
00200 for(NodeIt v(g); v!=INVALID; ++v) {
00201 _mate.set(v,map[v]);
00202 }
00203 }
00204
00206
00210 template<typename NMapN>
00211 void writeNMapNode (NMapN& map) const {
00212 for(NodeIt v(g); v!=INVALID; ++v) {
00213 map.set(v,_mate[v]);
00214 }
00215 }
00216
00218
00224 template<typename NMapE>
00225 void readNMapEdge(NMapE& map) {
00226 for(NodeIt v(g); v!=INVALID; ++v) {
00227 UEdge e=map[v];
00228 if ( e!=INVALID )
00229 _mate.set(v,g.oppositeNode(v,e));
00230 }
00231 }
00232
00234
00240 template<typename NMapE>
00241 void writeNMapEdge (NMapE& map) const {
00242 typename Graph::template NodeMap<bool> todo(g,true);
00243 for(NodeIt v(g); v!=INVALID; ++v) {
00244 if ( todo[v] && _mate[v]!=INVALID ) {
00245 Node u=_mate[v];
00246 for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
00247 if ( g.runningNode(e) == u ) {
00248 map.set(u,e);
00249 map.set(v,e);
00250 todo.set(u,false);
00251 todo.set(v,false);
00252 break;
00253 }
00254 }
00255 }
00256 }
00257 }
00258
00259
00261
00266 template<typename EMapB>
00267 void readEMapBool(EMapB& map) {
00268 for(UEdgeIt e(g); e!=INVALID; ++e) {
00269 if ( map[e] ) {
00270 Node u=g.source(e);
00271 Node v=g.target(e);
00272 _mate.set(u,v);
00273 _mate.set(v,u);
00274 }
00275 }
00276 }
00277
00278
00280
00285 template<typename EMapB>
00286 void writeEMapBool (EMapB& map) const {
00287 for(UEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
00288
00289 typename Graph::template NodeMap<bool> todo(g,true);
00290 for(NodeIt v(g); v!=INVALID; ++v) {
00291 if ( todo[v] && _mate[v]!=INVALID ) {
00292 Node u=_mate[v];
00293 for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
00294 if ( g.runningNode(e) == u ) {
00295 map.set(e,true);
00296 todo.set(u,false);
00297 todo.set(v,false);
00298 break;
00299 }
00300 }
00301 }
00302 }
00303 }
00304
00305
00308
00312 template<typename NMapEnum>
00313 void writePos (NMapEnum& map) const {
00314 for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]);
00315 }
00316
00317 private:
00318
00319
00320 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
00321 UFE& blossom, UFE& tree);
00322
00323 void normShrink(Node v, typename Graph::template NodeMap<Node>& ear,
00324 UFE& blossom, UFE& tree);
00325
00326 bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear,
00327 UFE& blossom, UFE& tree, std::queue<Node>& Q);
00328
00329 void shrinkStep(Node& top, Node& middle, Node& bottom,
00330 typename Graph::template NodeMap<Node>& ear,
00331 UFE& blossom, UFE& tree, std::queue<Node>& Q);
00332
00333 void augment(Node x, typename Graph::template NodeMap<Node>& ear,
00334 UFE& blossom, UFE& tree);
00335
00336 };
00337
00338
00339
00340
00341
00342
00343
00344 template <typename Graph>
00345 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
00346 UFE& blossom, UFE& tree) {
00347
00348 std::queue<Node> Q;
00349 Q.push(v);
00350 std::queue<Node> R;
00351
00352
00353 while ( !Q.empty() ) {
00354 Node x=Q.front();
00355 Q.pop();
00356 if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
00357 else R.push(x);
00358 }
00359
00360 while ( !R.empty() ) {
00361 Node x=R.front();
00362 R.pop();
00363
00364 for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
00365 Node y=g.runningNode(e);
00366
00367 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) {
00368
00369
00370 typename Graph::template NodeMap<bool> path(g,false);
00371
00372 Node b=blossom.find(x);
00373 path.set(b,true);
00374 b=_mate[b];
00375 while ( b!=INVALID ) {
00376 b=blossom.find(ear[b]);
00377 path.set(b,true);
00378 b=_mate[b];
00379 }
00380
00381 Node top=y;
00382 Node middle=blossom.find(top);
00383 Node bottom=x;
00384 while ( !path[middle] )
00385 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
00386
00387 Node base=middle;
00388 top=x;
00389 middle=blossom.find(top);
00390 bottom=y;
00391 Node blossom_base=blossom.find(base);
00392 while ( middle!=blossom_base )
00393 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
00394
00395 blossom.makeRep(base);
00396 }
00397
00398 while ( !Q.empty() ) {
00399 Node x=Q.front();
00400 Q.pop();
00401 if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
00402 else R.push(x);
00403 }
00404 }
00405 }
00406 }
00407
00408
00409 template <typename Graph>
00410 void MaxMatching<Graph>::normShrink(Node v,
00411 typename Graph::template
00412 NodeMap<Node>& ear,
00413 UFE& blossom, UFE& tree) {
00414 std::queue<Node> Q;
00415 Q.push(v);
00416 while ( !Q.empty() ) {
00417
00418 Node x=Q.front();
00419 Q.pop();
00420
00421 for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
00422 Node y=g.runningNode(e);
00423
00424 switch ( position[y] ) {
00425 case D:
00426
00427 if ( blossom.find(x) != blossom.find(y) ) {
00428 typename Graph::template NodeMap<bool> path(g,false);
00429
00430 Node b=blossom.find(x);
00431 path.set(b,true);
00432 b=_mate[b];
00433 while ( b!=INVALID ) {
00434 b=blossom.find(ear[b]);
00435 path.set(b,true);
00436 b=_mate[b];
00437 }
00438
00439 Node top=y;
00440 Node middle=blossom.find(top);
00441 Node bottom=x;
00442 while ( !path[middle] )
00443 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
00444
00445 Node base=middle;
00446 top=x;
00447 middle=blossom.find(top);
00448 bottom=y;
00449 Node blossom_base=blossom.find(base);
00450 while ( middle!=blossom_base )
00451 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
00452
00453 blossom.makeRep(base);
00454 }
00455 break;
00456 case C:
00457 if ( _mate[y]!=INVALID ) {
00458
00459 ear.set(y,x);
00460 Node w=_mate[y];
00461 blossom.insert(w);
00462 position.set(y,A);
00463 position.set(w,D);
00464 tree.insert(y);
00465 tree.insert(w);
00466 tree.join(y,blossom.find(x));
00467 tree.join(w,y);
00468 Q.push(w);
00469 } else {
00470 augment(x, ear, blossom, tree);
00471 _mate.set(x,y);
00472 _mate.set(y,x);
00473 return;
00474 }
00475 break;
00476 default: break;
00477 }
00478 }
00479 }
00480 }
00481
00482 template <typename Graph>
00483 bool MaxMatching<Graph>::noShrinkStep(Node x,
00484 typename Graph::template
00485 NodeMap<Node>& ear,
00486 UFE& blossom, UFE& tree,
00487 std::queue<Node>& Q) {
00488 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
00489 Node y=g.runningNode(e);
00490
00491 if ( position[y]==C ) {
00492 if ( _mate[y]!=INVALID ) {
00493 ear.set(y,x);
00494 Node w=_mate[y];
00495 blossom.insert(w);
00496 position.set(y,A);
00497 position.set(w,D);
00498 tree.insert(y);
00499 tree.insert(w);
00500 tree.join(y,blossom.find(x));
00501 tree.join(w,y);
00502 Q.push(w);
00503 } else {
00504 augment(x, ear, blossom, tree);
00505 _mate.set(x,y);
00506 _mate.set(y,x);
00507 return true;
00508 }
00509 }
00510 }
00511 return false;
00512 }
00513
00514 template <typename Graph>
00515 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom,
00516 typename Graph::template
00517 NodeMap<Node>& ear,
00518 UFE& blossom, UFE& tree,
00519 std::queue<Node>& Q) {
00520 ear.set(top,bottom);
00521 Node t=top;
00522 while ( t!=middle ) {
00523 Node u=_mate[t];
00524 t=ear[u];
00525 ear.set(t,u);
00526 }
00527 bottom=_mate[middle];
00528 position.set(bottom,D);
00529 Q.push(bottom);
00530 top=ear[bottom];
00531 Node oldmiddle=middle;
00532 middle=blossom.find(top);
00533 tree.erase(bottom);
00534 tree.erase(oldmiddle);
00535 blossom.insert(bottom);
00536 blossom.join(bottom, oldmiddle);
00537 blossom.join(top, oldmiddle);
00538 }
00539
00540 template <typename Graph>
00541 void MaxMatching<Graph>::augment(Node x,
00542 typename Graph::template NodeMap<Node>& ear,
00543 UFE& blossom, UFE& tree) {
00544 Node v=_mate[x];
00545 while ( v!=INVALID ) {
00546
00547 Node u=ear[v];
00548 _mate.set(v,u);
00549 Node tmp=v;
00550 v=_mate[u];
00551 _mate.set(u,tmp);
00552 }
00553 typename UFE::ItemIt it;
00554 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {
00555 if ( position[it] == D ) {
00556 typename UFE::ItemIt b_it;
00557 for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {
00558 position.set( b_it ,C);
00559 }
00560 blossom.eraseClass(it);
00561 } else position.set( it ,C);
00562 }
00563 tree.eraseClass(x);
00564
00565 }
00566
00568
00569 }
00570
00571 #endif //LEMON_MAX_MATCHING_H