# HG changeset patch # User jacint # Date 1143730931 0 # Node ID f34f044a043c67c0004c4e101931fbe394c5b125 # Parent 0f3367da61042b063b2aaa58b2aec99e82067517 Unionfind changes induced some bugs here. Also some augmentations made. diff -r 0f3367da6104 -r f34f044a043c lemon/max_matching.h --- a/lemon/max_matching.h Thu Mar 30 09:42:05 2006 +0000 +++ b/lemon/max_matching.h Thu Mar 30 15:02:11 2006 +0000 @@ -114,6 +114,7 @@ ///giving a faster algorithm for dense graphs. void runEdmonds( int heur = 1 ) { + //each vertex is put to C for(NodeIt v(g); v!=INVALID; ++v) position.set(v,C); @@ -128,6 +129,11 @@ //If these UFE's would be members of the class then also //blossom_base and tree_base should be a member. + //We build only one tree and the other vertices uncovered by the + //matching belong to C. (They can be considered as singleton + //trees.) If this tree can be augmented or no more + //grow/augmentation/shrink is possible then we return to this + //"for" cycle. for(NodeIt v(g); v!=INVALID; ++v) { if ( position[v]==C && _mate[v]==INVALID ) { blossom.insert(v); @@ -223,8 +229,8 @@ ///joining \c u to \c v will be an edge of the matching. template void readNMapEdge(NMapE& map) { - for(NodeIt v(g); v!=INVALID; ++v) { - UEdge e=map[v]; + for(NodeIt v(g); v!=INVALID; ++v) { + UEdge e=map[v]; if ( e!=INVALID ) _mate.set(v,g.oppositeNode(v,e)); } @@ -323,13 +329,17 @@ void normShrink(Node v, typename Graph::template NodeMap& ear, UFE& blossom, UFE& tree); - bool noShrinkStep(Node x, typename Graph::template NodeMap& ear, - UFE& blossom, UFE& tree, std::queue& Q); + void shrink(Node x,Node y, typename Graph::template NodeMap& ear, + UFE& blossom, UFE& tree,std::queue& Q); void shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::template NodeMap& ear, UFE& blossom, UFE& tree, std::queue& Q); + bool growOrAugment(Node& y, Node& x, typename Graph::template + NodeMap& ear, UFE& blossom, UFE& tree, + std::queue& Q); + void augment(Node x, typename Graph::template NodeMap& ear, UFE& blossom, UFE& tree); @@ -342,8 +352,11 @@ template - void MaxMatching::lateShrink(Node v, typename Graph::template NodeMap& ear, - UFE& blossom, UFE& tree) { + void MaxMatching::lateShrink(Node v, typename Graph::template + NodeMap& ear, UFE& blossom, UFE& tree) { + //We have one tree which we grow, and also shrink but only if it cannot be + //postponed. If we augment then we return to the "for" cycle of + //runEdmonds(). std::queue Q; //queue of the totally unscanned nodes Q.push(v); @@ -353,8 +366,13 @@ while ( !Q.empty() ) { Node x=Q.front(); Q.pop(); - if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return; - else R.push(x); + for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { + Node y=g.runningNode(e); + //growOrAugment grows if y is covered by the matching and + //augments if not. In this latter case it returns 1. + if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return; + } + R.push(x); } while ( !R.empty() ) { @@ -364,42 +382,20 @@ for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) { Node y=g.runningNode(e); - if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { - //x and y must be in the same tree + if ( position[y] == D && blossom.find(x) != blossom.find(y) ) + //Recall that we have only one tree. + shrink( x, y, ear, blossom, tree, Q); - typename Graph::template NodeMap path(g,false); - - Node b=blossom.find(x); - path.set(b,true); - b=_mate[b]; - while ( b!=INVALID ) { - b=blossom.find(ear[b]); - path.set(b,true); - b=_mate[b]; - } //going till the root - - Node top=y; - Node middle=blossom.find(top); - Node bottom=x; - while ( !path[middle] ) - shrinkStep(top, middle, bottom, ear, blossom, tree, Q); - - Node base=middle; - top=x; - middle=blossom.find(top); - bottom=y; - Node blossom_base=blossom.find(base); - while ( middle!=blossom_base ) - shrinkStep(top, middle, bottom, ear, blossom, tree, Q); - - blossom.makeRep(base); - } // if shrink is needed - while ( !Q.empty() ) { Node x=Q.front(); Q.pop(); - if ( noShrinkStep(x, ear, blossom, tree, Q) ) return; - else R.push(x); + for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { + Node y=g.runningNode(e); + //growOrAugment grows if y is covered by the matching and + //augments if not. In this latter case it returns 1. + if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return; + } + R.push(x); } } //for e } // while ( !R.empty() ) @@ -411,6 +407,9 @@ typename Graph::template NodeMap& ear, UFE& blossom, UFE& tree) { + //We have one tree, which we grow and shrink. If we augment then we + //return to the "for" cycle of runEdmonds(). + std::queue Q; //queue of the unscanned nodes Q.push(v); while ( !Q.empty() ) { @@ -423,100 +422,70 @@ switch ( position[y] ) { case D: //x and y must be in the same tree - - if ( blossom.find(x) != blossom.find(y) ) { //shrink - typename Graph::template NodeMap path(g,false); - - Node b=blossom.find(x); - path.set(b,true); - b=_mate[b]; - while ( b!=INVALID ) { - b=blossom.find(ear[b]); - path.set(b,true); - b=_mate[b]; - } //going till the root - - Node top=y; - Node middle=blossom.find(top); - Node bottom=x; - while ( !path[middle] ) - shrinkStep(top, middle, bottom, ear, blossom, tree, Q); - - Node base=middle; - top=x; - middle=blossom.find(top); - bottom=y; - Node blossom_base=blossom.find(base); - while ( middle!=blossom_base ) - shrinkStep(top, middle, bottom, ear, blossom, tree, Q); - - blossom.makeRep(base); - } + if ( blossom.find(x) != blossom.find(y) ) + //x and y are in the same tree + shrink( x, y, ear, blossom, tree, Q); break; case C: - if ( _mate[y]!=INVALID ) { //grow - - ear.set(y,x); - Node w=_mate[y]; - blossom.insert(w); - position.set(y,A); - position.set(w,D); - tree.insert(y); - tree.insert(w); - tree.join(y,blossom.find(x)); - tree.join(w,y); - Q.push(w); - } else { //augment - augment(x, ear, blossom, tree); - _mate.set(x,y); - _mate.set(y,x); - return; - } //if + //growOrAugment grows if y is covered by the matching and + //augments if not. In this latter case it returns 1. + if ( growOrAugment(y, x, ear, blossom, tree, Q) ) return; break; default: break; - } + } } } } + template - bool MaxMatching::noShrinkStep(Node x, - typename Graph::template - NodeMap& ear, - UFE& blossom, UFE& tree, - std::queue& Q) { - for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { - Node y=g.runningNode(e); - - if ( position[y]==C ) { - if ( _mate[y]!=INVALID ) { //grow - ear.set(y,x); - Node w=_mate[y]; - blossom.insert(w); - position.set(y,A); - position.set(w,D); - tree.insert(y); - tree.insert(w); - tree.join(y,blossom.find(x)); - tree.join(w,y); - Q.push(w); - } else { //augment - augment(x, ear, blossom, tree); - _mate.set(x,y); - _mate.set(y,x); - return true; - } - } - } - return false; + void MaxMatching::shrink(Node x,Node y, typename + Graph::template NodeMap& ear, + UFE& blossom, UFE& tree, std::queue& Q) { + //x and y are the two adjacent vertices in two blossoms. + + typename Graph::template NodeMap path(g,false); + + Node b=blossom.find(x); + path.set(b,true); + b=_mate[b]; + while ( b!=INVALID ) { + b=blossom.find(ear[b]); + path.set(b,true); + b=_mate[b]; + } //we go until the root through bases of blossoms and odd vertices + + Node top=y; + Node middle=blossom.find(top); + Node bottom=x; + while ( !path[middle] ) + shrinkStep(top, middle, bottom, ear, blossom, tree, Q); + //Until we arrive to a node on the path, we update blossom, tree + //and the positions of the odd nodes. + + Node base=middle; + top=x; + middle=blossom.find(top); + bottom=y; + Node blossom_base=blossom.find(base); + while ( middle!=blossom_base ) + shrinkStep(top, middle, bottom, ear, blossom, tree, Q); + //Until we arrive to a node on the path, we update blossom, tree + //and the positions of the odd nodes. + + blossom.makeRep(base); } + + template void MaxMatching::shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::template NodeMap& ear, UFE& blossom, UFE& tree, std::queue& Q) { + //We traverse a blossom and update everything. + ear.set(top,bottom); Node t=top; while ( t!=middle ) { @@ -537,6 +506,36 @@ blossom.join(top, oldmiddle); } + + template + bool MaxMatching::growOrAugment(Node& y, Node& x, typename Graph::template + NodeMap& ear, UFE& blossom, UFE& tree, + std::queue& Q) { + //x is in a blossom in the tree, y is outside. If y is covered by + //the matching we grow, otherwise we augment. In this case we + //return 1. + + if ( _mate[y]!=INVALID ) { //grow + ear.set(y,x); + Node w=_mate[y]; + blossom.insert(w); + position.set(y,A); + position.set(w,D); + tree.insert(y); + tree.insert(w); + tree.join(y,blossom.find(x)); + tree.join(w,y); + Q.push(w); + } else { //augment + augment(x, ear, blossom, tree); + _mate.set(x,y); + _mate.set(y,x); + return true; + } + return false; + } + + template void MaxMatching::augment(Node x, typename Graph::template NodeMap& ear, @@ -550,6 +549,7 @@ v=_mate[u]; _mate.set(u,tmp); } + Node y=blossom.find(x); typename UFE::ItemIt it; for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) { if ( position[it] == D ) { @@ -560,7 +560,7 @@ blossom.eraseClass(it); } else position.set( it ,C); } - tree.eraseClass(x); + tree.eraseClass(y); }