Unionfind changes induced some bugs here. Also some augmentations made.
authorjacint
Thu, 30 Mar 2006 15:02:11 +0000
changeset 2023f34f044a043c
parent 2022 0f3367da6104
child 2024 4ab8a25def3c
Unionfind changes induced some bugs here. Also some augmentations made.
lemon/max_matching.h
     1.1 --- a/lemon/max_matching.h	Thu Mar 30 09:42:05 2006 +0000
     1.2 +++ b/lemon/max_matching.h	Thu Mar 30 15:02:11 2006 +0000
     1.3 @@ -114,6 +114,7 @@
     1.4      ///giving a faster algorithm for dense graphs.  
     1.5      void runEdmonds( int heur = 1 ) {
     1.6        
     1.7 +      //each vertex is put to C
     1.8        for(NodeIt v(g); v!=INVALID; ++v)
     1.9  	position.set(v,C);      
    1.10        
    1.11 @@ -128,6 +129,11 @@
    1.12        //If these UFE's would be members of the class then also
    1.13        //blossom_base and tree_base should be a member.
    1.14        
    1.15 +      //We build only one tree and the other vertices uncovered by the
    1.16 +      //matching belong to C. (They can be considered as singleton
    1.17 +      //trees.) If this tree can be augmented or no more
    1.18 +      //grow/augmentation/shrink is possible then we return to this
    1.19 +      //"for" cycle.
    1.20        for(NodeIt v(g); v!=INVALID; ++v) {
    1.21  	if ( position[v]==C && _mate[v]==INVALID ) {
    1.22  	  blossom.insert(v);
    1.23 @@ -223,8 +229,8 @@
    1.24      ///joining \c u to \c v will be an edge of the matching.
    1.25      template<typename NMapE>
    1.26      void readNMapEdge(NMapE& map) {
    1.27 -     for(NodeIt v(g); v!=INVALID; ++v) {
    1.28 -       UEdge e=map[v];
    1.29 +      for(NodeIt v(g); v!=INVALID; ++v) {
    1.30 +	UEdge e=map[v];
    1.31  	if ( e!=INVALID )
    1.32  	  _mate.set(v,g.oppositeNode(v,e));
    1.33        } 
    1.34 @@ -323,13 +329,17 @@
    1.35      void normShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
    1.36  		    UFE& blossom, UFE& tree);
    1.37  
    1.38 -    bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear,  
    1.39 -		      UFE& blossom, UFE& tree, std::queue<Node>& Q);
    1.40 +    void shrink(Node x,Node y, typename Graph::template NodeMap<Node>& ear,  
    1.41 +		UFE& blossom, UFE& tree,std::queue<Node>& Q);
    1.42  
    1.43      void shrinkStep(Node& top, Node& middle, Node& bottom,
    1.44  		    typename Graph::template NodeMap<Node>& ear,  
    1.45  		    UFE& blossom, UFE& tree, std::queue<Node>& Q);
    1.46  
    1.47 +    bool growOrAugment(Node& y, Node& x, typename Graph::template 
    1.48 +		       NodeMap<Node>& ear, UFE& blossom, UFE& tree, 
    1.49 +		       std::queue<Node>& Q);
    1.50 +
    1.51      void augment(Node x, typename Graph::template NodeMap<Node>& ear,  
    1.52  		 UFE& blossom, UFE& tree);
    1.53  
    1.54 @@ -342,8 +352,11 @@
    1.55  
    1.56  
    1.57    template <typename Graph>
    1.58 -  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
    1.59 -				      UFE& blossom, UFE& tree) {
    1.60 +  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template 
    1.61 +				      NodeMap<Node>& ear, UFE& blossom, UFE& tree) {
    1.62 +    //We have one tree which we grow, and also shrink but only if it cannot be
    1.63 +    //postponed. If we augment then we return to the "for" cycle of
    1.64 +    //runEdmonds().
    1.65  
    1.66      std::queue<Node> Q;   //queue of the totally unscanned nodes
    1.67      Q.push(v);  
    1.68 @@ -353,8 +366,13 @@
    1.69      while ( !Q.empty() ) {
    1.70        Node x=Q.front();
    1.71        Q.pop();
    1.72 -      if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
    1.73 -      else R.push(x);
    1.74 +      for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
    1.75 +	Node y=g.runningNode(e);
    1.76 +	//growOrAugment grows if y is covered by the matching and
    1.77 +	//augments if not. In this latter case it returns 1.
    1.78 +	if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return;
    1.79 +      }
    1.80 +      R.push(x);
    1.81      }
    1.82        
    1.83      while ( !R.empty() ) {
    1.84 @@ -364,42 +382,20 @@
    1.85        for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
    1.86  	Node y=g.runningNode(e);
    1.87  
    1.88 -	if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { 
    1.89 -	  //x and y must be in the same tree
    1.90 +	if ( position[y] == D && blossom.find(x) != blossom.find(y) )  
    1.91 +	  //Recall that we have only one tree.
    1.92 +	  shrink( x, y, ear, blossom, tree, Q);	
    1.93  	
    1.94 -	  typename Graph::template NodeMap<bool> path(g,false);
    1.95 -
    1.96 -	  Node b=blossom.find(x);
    1.97 -	  path.set(b,true);
    1.98 -	  b=_mate[b];
    1.99 -	  while ( b!=INVALID ) { 
   1.100 -	    b=blossom.find(ear[b]);
   1.101 -	    path.set(b,true);
   1.102 -	    b=_mate[b];
   1.103 -	  } //going till the root
   1.104 -	
   1.105 -	  Node top=y;
   1.106 -	  Node middle=blossom.find(top);
   1.107 -	  Node bottom=x;
   1.108 -	  while ( !path[middle] )
   1.109 -	    shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.110 -		  
   1.111 -	  Node base=middle;
   1.112 -	  top=x;
   1.113 -	  middle=blossom.find(top);
   1.114 -	  bottom=y;
   1.115 -	  Node blossom_base=blossom.find(base);
   1.116 -	  while ( middle!=blossom_base )
   1.117 -	    shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.118 -		  
   1.119 -	  blossom.makeRep(base);
   1.120 -	} // if shrink is needed
   1.121 -
   1.122  	while ( !Q.empty() ) {
   1.123  	  Node x=Q.front();
   1.124  	  Q.pop();
   1.125 -	  if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
   1.126 -	  else R.push(x);
   1.127 +	  for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
   1.128 +	    Node y=g.runningNode(e);
   1.129 +	    //growOrAugment grows if y is covered by the matching and
   1.130 +	    //augments if not. In this latter case it returns 1.
   1.131 +	    if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return;
   1.132 +	  }
   1.133 +	  R.push(x);
   1.134  	}
   1.135        } //for e
   1.136      } // while ( !R.empty() )
   1.137 @@ -411,6 +407,9 @@
   1.138  				      typename Graph::template
   1.139  				      NodeMap<Node>& ear,  
   1.140  				      UFE& blossom, UFE& tree) {
   1.141 +    //We have one tree, which we grow and shrink. If we augment then we
   1.142 +    //return to the "for" cycle of runEdmonds().
   1.143 +    
   1.144      std::queue<Node> Q;   //queue of the unscanned nodes
   1.145      Q.push(v);  
   1.146      while ( !Q.empty() ) {
   1.147 @@ -423,100 +422,70 @@
   1.148  	      
   1.149  	switch ( position[y] ) {
   1.150  	case D:          //x and y must be in the same tree
   1.151 -
   1.152 -	  if ( blossom.find(x) != blossom.find(y) ) { //shrink
   1.153 -	    typename Graph::template NodeMap<bool> path(g,false);
   1.154 -	      
   1.155 -	    Node b=blossom.find(x);
   1.156 -	    path.set(b,true);
   1.157 -	    b=_mate[b];
   1.158 -	    while ( b!=INVALID ) { 
   1.159 -	      b=blossom.find(ear[b]);
   1.160 -	      path.set(b,true);
   1.161 -	      b=_mate[b];
   1.162 -	    } //going till the root
   1.163 -	
   1.164 -	    Node top=y;
   1.165 -	    Node middle=blossom.find(top);
   1.166 -	    Node bottom=x;
   1.167 -	    while ( !path[middle] )
   1.168 -	      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.169 -		
   1.170 -	    Node base=middle;
   1.171 -	    top=x;
   1.172 -	    middle=blossom.find(top);
   1.173 -	    bottom=y;
   1.174 -	    Node blossom_base=blossom.find(base);
   1.175 -	    while ( middle!=blossom_base )
   1.176 -	      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.177 -		
   1.178 -	    blossom.makeRep(base);
   1.179 -	  }
   1.180 +	  if ( blossom.find(x) != blossom.find(y) )
   1.181 +	    //x and y are in the same tree
   1.182 +	    shrink( x, y, ear, blossom, tree, Q);
   1.183  	  break;
   1.184  	case C:
   1.185 -	  if ( _mate[y]!=INVALID ) {   //grow
   1.186 -
   1.187 -	    ear.set(y,x);
   1.188 -	    Node w=_mate[y];
   1.189 -	    blossom.insert(w);
   1.190 -	    position.set(y,A); 
   1.191 -	    position.set(w,D); 
   1.192 -	    tree.insert(y);
   1.193 -	    tree.insert(w);
   1.194 -	    tree.join(y,blossom.find(x));  
   1.195 -	    tree.join(w,y);  
   1.196 -	    Q.push(w);
   1.197 -	  } else {                 //augment  
   1.198 -	    augment(x, ear, blossom, tree);
   1.199 -	    _mate.set(x,y);
   1.200 -	    _mate.set(y,x);
   1.201 -	    return;
   1.202 -	  } //if 
   1.203 +	  //growOrAugment grows if y is covered by the matching and
   1.204 +	  //augments if not. In this latter case it returns 1.
   1.205 +	  if ( growOrAugment(y, x, ear, blossom, tree, Q) ) return;
   1.206  	  break;
   1.207  	default: break;
   1.208 -	}
   1.209 +       	}
   1.210        }
   1.211      }
   1.212    }
   1.213 +  
   1.214  
   1.215    template <typename Graph>
   1.216 -  bool MaxMatching<Graph>::noShrinkStep(Node x,
   1.217 -					typename Graph::template 
   1.218 -					NodeMap<Node>& ear,  
   1.219 -					UFE& blossom, UFE& tree,
   1.220 -					std::queue<Node>& Q) {
   1.221 -    for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
   1.222 -      Node y=g.runningNode(e);
   1.223 -	
   1.224 -      if ( position[y]==C ) {
   1.225 -	if ( _mate[y]!=INVALID ) {       //grow
   1.226 -	  ear.set(y,x);
   1.227 -	  Node w=_mate[y];
   1.228 -	  blossom.insert(w);
   1.229 -	  position.set(y,A);
   1.230 -	  position.set(w,D);
   1.231 -	  tree.insert(y);
   1.232 -	  tree.insert(w);
   1.233 -	  tree.join(y,blossom.find(x));  
   1.234 -	  tree.join(w,y);  
   1.235 -	  Q.push(w);
   1.236 -	} else {                      //augment 
   1.237 -	  augment(x, ear, blossom, tree);
   1.238 -	  _mate.set(x,y);
   1.239 -	  _mate.set(y,x);
   1.240 -	  return true;
   1.241 -	}
   1.242 -      }
   1.243 -    }
   1.244 -    return false;
   1.245 +    void MaxMatching<Graph>::shrink(Node x,Node y, typename 
   1.246 +				    Graph::template NodeMap<Node>& ear,  
   1.247 +				    UFE& blossom, UFE& tree, std::queue<Node>& Q) {
   1.248 +    //x and y are the two adjacent vertices in two blossoms.
   1.249 +   
   1.250 +    typename Graph::template NodeMap<bool> path(g,false);
   1.251 +    
   1.252 +    Node b=blossom.find(x);
   1.253 +    path.set(b,true);
   1.254 +    b=_mate[b];
   1.255 +    while ( b!=INVALID ) { 
   1.256 +      b=blossom.find(ear[b]);
   1.257 +      path.set(b,true);
   1.258 +      b=_mate[b];
   1.259 +    } //we go until the root through bases of blossoms and odd vertices
   1.260 +    
   1.261 +    Node top=y;
   1.262 +    Node middle=blossom.find(top);
   1.263 +    Node bottom=x;
   1.264 +    while ( !path[middle] )
   1.265 +      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.266 +    //Until we arrive to a node on the path, we update blossom, tree
   1.267 +    //and the positions of the odd nodes.
   1.268 +    
   1.269 +    Node base=middle;
   1.270 +    top=x;
   1.271 +    middle=blossom.find(top);
   1.272 +    bottom=y;
   1.273 +    Node blossom_base=blossom.find(base);
   1.274 +    while ( middle!=blossom_base )
   1.275 +      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.276 +    //Until we arrive to a node on the path, we update blossom, tree
   1.277 +    //and the positions of the odd nodes.
   1.278 +    
   1.279 +    blossom.makeRep(base);
   1.280    }
   1.281  
   1.282 +
   1.283 +
   1.284    template <typename Graph>
   1.285    void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom,
   1.286  				      typename Graph::template
   1.287  				      NodeMap<Node>& ear,  
   1.288  				      UFE& blossom, UFE& tree,
   1.289  				      std::queue<Node>& Q) {
   1.290 +    //We traverse a blossom and update everything.
   1.291 +    
   1.292      ear.set(top,bottom);
   1.293      Node t=top;
   1.294      while ( t!=middle ) {
   1.295 @@ -537,6 +506,36 @@
   1.296      blossom.join(top, oldmiddle);
   1.297    }
   1.298  
   1.299 +
   1.300 +  template <typename Graph>
   1.301 +  bool MaxMatching<Graph>::growOrAugment(Node& y, Node& x, typename Graph::template
   1.302 +					 NodeMap<Node>& ear, UFE& blossom, UFE& tree,
   1.303 +					 std::queue<Node>& Q) {
   1.304 +    //x is in a blossom in the tree, y is outside. If y is covered by
   1.305 +    //the matching we grow, otherwise we augment. In this case we
   1.306 +    //return 1.
   1.307 +    
   1.308 +    if ( _mate[y]!=INVALID ) {       //grow
   1.309 +      ear.set(y,x);
   1.310 +      Node w=_mate[y];
   1.311 +      blossom.insert(w);
   1.312 +      position.set(y,A);
   1.313 +      position.set(w,D);
   1.314 +      tree.insert(y);
   1.315 +      tree.insert(w);
   1.316 +      tree.join(y,blossom.find(x));  
   1.317 +      tree.join(w,y);  
   1.318 +      Q.push(w);
   1.319 +    } else {                      //augment 
   1.320 +      augment(x, ear, blossom, tree);
   1.321 +      _mate.set(x,y);
   1.322 +      _mate.set(y,x);
   1.323 +      return true;
   1.324 +    }
   1.325 +    return false;
   1.326 +  }
   1.327 +  
   1.328 +
   1.329    template <typename Graph>
   1.330    void MaxMatching<Graph>::augment(Node x,
   1.331  				   typename Graph::template NodeMap<Node>& ear,  
   1.332 @@ -550,6 +549,7 @@
   1.333        v=_mate[u];
   1.334        _mate.set(u,tmp);
   1.335      }
   1.336 +    Node y=blossom.find(x);
   1.337      typename UFE::ItemIt it;
   1.338      for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
   1.339        if ( position[it] == D ) {
   1.340 @@ -560,7 +560,7 @@
   1.341  	blossom.eraseClass(it);
   1.342        } else position.set( it ,C);
   1.343      }
   1.344 -    tree.eraseClass(x);
   1.345 +    tree.eraseClass(y);
   1.346  
   1.347    }
   1.348