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