Contains Edmonds' matching algorithm in a plain and in a heuristical form.
authorjacint
Wed, 05 May 2004 17:51:56 +0000
changeset 537acd69f60b9c7
parent 536 c050de070935
child 538 d8863141824d
Contains Edmonds' matching algorithm in a plain and in a heuristical form.
src/work/jacint/max_matching.h
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/jacint/max_matching.h	Wed May 05 17:51:56 2004 +0000
     1.3 @@ -0,0 +1,568 @@
     1.4 +// -*- C++ -*-
     1.5 +#ifndef HUGO_MAX_MATCHING_H
     1.6 +#define HUGO_MAX_MATCHING_H
     1.7 +
     1.8 +///\ingroup galgs
     1.9 +///\file
    1.10 +///\brief Maximum matching algorithm.
    1.11 +
    1.12 +#include <queue>
    1.13 +
    1.14 +#include <invalid.h>
    1.15 +#include <unionfind.h>
    1.16 +
    1.17 +namespace hugo {
    1.18 +
    1.19 +  /// \addtogroup galgs
    1.20 +  /// @{
    1.21 +
    1.22 +  ///Maximum matching algorithms class.
    1.23 +
    1.24 +  ///This class provides Edmonds' alternating forest matching
    1.25 +  ///algorithm. The starting matching (if any) can be passed to the
    1.26 +  ///algorithm using read-in functions \ref readNMapNode, \ref
    1.27 +  ///readNMapEdge or \ref readEMapBool depending on the container. The
    1.28 +  ///resulting maximum matching can be attained by write-out functions
    1.29 +  ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool
    1.30 +  ///depending on the preferred container. 
    1.31 +
    1.32 +  ///The dual side of a mathcing is a map of the nodes to
    1.33 +  ///MaxMatching::pos_enum, having values D, A and C showing the
    1.34 +  ///Gallai-Edmonds decomposition of the graph. The nodes in D induce
    1.35 +  ///a graph with factor-critical components, the nodes in A form the
    1.36 +  ///barrier, and the nodes in C induce a graph having a perfect
    1.37 +  ///matching. This decomposition can be attained by calling \ref
    1.38 +  ///writePos after running the algorithm. Before subsequent runs,
    1.39 +  ///the function \ref resetPos() must be called.
    1.40 +
    1.41 +  ///\param Graph The undirected graph type the algorithm runs on.
    1.42 +
    1.43 +  ///\author Jacint Szabo  
    1.44 +  template <typename Graph>
    1.45 +  class MaxMatching {
    1.46 +    typedef typename Graph::Node Node;
    1.47 +    typedef typename Graph::Edge Edge;
    1.48 +    typedef typename Graph::EdgeIt EdgeIt;
    1.49 +    typedef typename Graph::NodeIt NodeIt;
    1.50 +    typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.51 +
    1.52 +    typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
    1.53 +
    1.54 +  public:
    1.55 +    
    1.56 +    ///Indicates the Gallai-Edmonds decomposition of the graph.
    1.57 +
    1.58 +    ///Indicates the Gallai-Edmonds decomposition of the graph, which
    1.59 +    ///shows an upper bound on the size of a maximum matching. The
    1.60 +    ///nodes with pos_enum D induce a graph with factor-critical
    1.61 +    ///components, the nodes in A form the canonical barrier, and the
    1.62 +    ///nodes in C induce a graph having a perfect matching. 
    1.63 +    enum pos_enum {
    1.64 +      D=0,
    1.65 +      A=1,
    1.66 +      C=2
    1.67 +    }; 
    1.68 +
    1.69 +  private:
    1.70 +
    1.71 +    const Graph& G;
    1.72 +    typename Graph::template NodeMap<Node> mate;
    1.73 +    typename Graph::template NodeMap<pos_enum> position;
    1.74 +     
    1.75 +  public:
    1.76 +    
    1.77 +    MaxMatching(Graph& _G) : G(_G), mate(_G,INVALID), position(_G,C) {}
    1.78 +
    1.79 +    ///Runs Edmonds' algorithm.
    1.80 +
    1.81 +    ///Runs Edmonds' algorithm for sparse graphs (edgeNum >=
    1.82 +    ///2*nodeNum), and a heuristical Edmonds' algorithm with a
    1.83 +    ///heuristic of postponing shrinks for dense graphs. \pre Before
    1.84 +    ///the subsequent calls \ref resetPos must be called.
    1.85 +    void run();
    1.86 +
    1.87 +    ///Runs Edmonds' algorithm.
    1.88 +    
    1.89 +    ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
    1.90 +    ///Edmonds' algorithm with a heuristic of postponing shrinks,
    1.91 +    ///giving a faster algorithm for dense graphs.  \pre Before the
    1.92 +    ///subsequent calls \ref resetPos must be called.
    1.93 +    void runEdmonds( int heur );
    1.94 +
    1.95 +    ///Finds a greedy matching starting from the actual matching.
    1.96 +    
    1.97 +    ///Starting form the actual matching stored, it finds a maximal
    1.98 +    ///greedy matching.
    1.99 +    void greedyMatching();
   1.100 +
   1.101 +    ///Returns the size of the actual matching stored.
   1.102 +
   1.103 +    ///Returns the size of the actual matching stored. After \ref
   1.104 +    ///run() it returns the size of a maximum matching in the graph.
   1.105 +    int size();
   1.106 +
   1.107 +    ///Resets the map storing the Gallai-Edmonds decomposition.
   1.108 +    
   1.109 +    ///Resets the map storing the Gallai-Edmonds decomposition of the
   1.110 +    ///graph, making it possible to run the algorithm. Must be called
   1.111 +    ///before all runs of the Edmonds algorithm, except for the first
   1.112 +    ///run.
   1.113 +    void resetPos();
   1.114 +
   1.115 +    ///Resets the actual matching to the empty matching.
   1.116 +
   1.117 +    ///Resets the actual matching to the empty matching.  
   1.118 +    ///
   1.119 +    void resetMatching();
   1.120 +
   1.121 +    ///Reads a matching from a \c Node map of \c Nodes.
   1.122 +
   1.123 +    ///Reads a matching from a \c Node map of \c Nodes. This map must be \e
   1.124 +    ///symmetric, i.e. if \c map[u]=v then \c map[v]=u must hold, and
   1.125 +    ///now \c uv is an edge of the matching.
   1.126 +    template<typename NMapN>
   1.127 +    void readNMapNode(NMapN& map) {
   1.128 +      NodeIt v;
   1.129 +      for( G.first(v); G.valid(v); G.next(v)) {
   1.130 +	mate.set(v,map[v]);   
   1.131 +      } 
   1.132 +    } 
   1.133 +    
   1.134 +    ///Writes the stored matching to a \c Node map of \c Nodes.
   1.135 +
   1.136 +    ///Writes the stored matching to a \c Node map of \c Nodes. The
   1.137 +    ///resulting map will be \e symmetric, i.e. if \c map[u]=v then \c
   1.138 +    ///map[v]=u will hold, and now \c uv is an edge of the matching.
   1.139 +    template<typename NMapN>
   1.140 +    void writeNMapNode(NMapN& map) {
   1.141 +      NodeIt v;
   1.142 +      for( G.first(v); G.valid(v); G.next(v)) {
   1.143 +	map.set(v,mate[v]);   
   1.144 +      } 
   1.145 +    } 
   1.146 +
   1.147 +    ///Reads a matching from a \c Node map of \c Edges.
   1.148 +
   1.149 +    ///Reads a matching from a \c Node map of incident \c Edges. This
   1.150 +    ///map must have the property that if \c G.bNode(map[u])=v then \c
   1.151 +    ///G.bNode(map[v])=u must hold, and now this edge is an edge of
   1.152 +    ///the matching.
   1.153 +    template<typename NMapE>
   1.154 +    void readNMapEdge(NMapE& map) {
   1.155 +      NodeIt v;
   1.156 +      for( G.first(v); G.valid(v); G.next(v)) {
   1.157 +	Edge e=map[v];
   1.158 +	if ( G.valid(e) )
   1.159 +	  G.tail(e) == v ? mate.set(v,G.head(e)) : mate.set(v,G.tail(e)); 
   1.160 +      } 
   1.161 +    } 
   1.162 +    
   1.163 +    ///Writes the matching stored to a \c Node map of \c Edges.
   1.164 +
   1.165 +    ///Writes the stored matching to a \c Node map of incident \c
   1.166 +    ///Edges. This map will have the property that if \c
   1.167 +    ///G.bNode(map[u])=v then \c G.bNode(map[v])=u holds, and now this
   1.168 +    ///edge is an edge of the matching.
   1.169 +    template<typename NMapE>
   1.170 +    void writeNMapEdge(NMapE& map)  {
   1.171 +      typename Graph::template NodeMap<bool> todo(G,false); 
   1.172 +      NodeIt v;
   1.173 +      for( G.first(v); G.valid(v); G.next(v)) {
   1.174 +	if ( mate[v]!=INVALID ) todo.set(v,true); 
   1.175 +      }
   1.176 +      NodeIt e;
   1.177 +      for( G.first(e); G.valid(e); G.next(e)) {
   1.178 +	if ( todo[G.head(e)] && todo[G.tail(e)] ) {
   1.179 +	  Node u=G.tail(e);
   1.180 +	  Node v=G.head(e); 
   1.181 +	  if ( mate[u]=v && mate[v]=u ) {
   1.182 +	    map.set(u,e);
   1.183 +	    map.set(v,e);
   1.184 +	    todo.set(u,false);
   1.185 +	    todo.set(v,false);
   1.186 +	  }
   1.187 +	}
   1.188 +      }
   1.189 +    } 
   1.190 +
   1.191 +    ///Reads a matching from an \c Edge map of \c bools.
   1.192 +    
   1.193 +    ///Reads a matching from an \c Edge map of \c bools. This map must
   1.194 +    ///have the property that there are no two adjacent edges \c e, \c
   1.195 +    ///f with \c map[e]=map[f]=true. The edges \c e with \c
   1.196 +    ///map[e]=true form the matching.
   1.197 +    template<typename EMapB>
   1.198 +    void readEMapBool(EMapB& map) {
   1.199 +      EdgeIt e;
   1.200 +      for( G.first(e); G.valid(e); G.next(e)) {
   1.201 +	if ( G.valid(e) ) {
   1.202 +	  Node u=G.tail(e);	  
   1.203 +	  Node v=G.head(e);
   1.204 +	  mate.set(u,v);
   1.205 +	  mate.set(v,u);
   1.206 +	} 
   1.207 +      } 
   1.208 +    }
   1.209 +
   1.210 +
   1.211 +    ///Writes the matching stored to an \c Edge map of \c bools.
   1.212 +
   1.213 +    ///Writes the matching stored to an \c Edge map of \c bools. This
   1.214 +    ///map will have the property that there are no two adjacent edges
   1.215 +    ///\c e, \c f with \c map[e]=map[f]=true. The edges \c e with \c
   1.216 +    ///map[e]=true form the matching.
   1.217 +    template<typename EMapB>
   1.218 +    void writeEMapBool(EMapB& map) {
   1.219 +      typename Graph::template NodeMap<bool> todo(G,false); 
   1.220 +      NodeIt v;
   1.221 +      for( G.first(v); G.valid(v); G.next(v)) {
   1.222 +	if ( mate[v]!=INVALID ) todo.set(v,true); 
   1.223 +      }
   1.224 +      
   1.225 +      NodeIt e;
   1.226 +      for( G.first(e); G.valid(e); G.next(e)) {
   1.227 +	map.set(e,false);
   1.228 +	if ( todo[G.head(e)] && todo[G.tail(e)] ) {
   1.229 +	  Node u=G.tail(e);
   1.230 +	  Node v=G.head(e); 
   1.231 +	  if ( mate[u]=v && mate[v]=u ) {
   1.232 +	    map.set(e,true);
   1.233 +	    todo.set(u,false);
   1.234 +	    todo.set(v,false);
   1.235 +	  }
   1.236 +	}
   1.237 +      }
   1.238 +    }
   1.239 +
   1.240 +    ///Writes the canonical decomposition of the graph after running
   1.241 +    ///the algorithm.
   1.242 +
   1.243 +    ///After calling any run methods of the class, and before calling
   1.244 +    ///\ref resetPos(), it writes the Gallai-Edmonds canonical
   1.245 +    ///decomposition of the graph. \c map must be a node map of \ref pos_enum 's.
   1.246 +    template<typename NMapEnum>
   1.247 +    void writePos(NMapEnum& map)  {
   1.248 +      NodeIt v;
   1.249 +      for( G.first(v); G.valid(v); G.next(v)) map.set(v,position[v]);
   1.250 +    }
   1.251 +
   1.252 +  private: 
   1.253 +
   1.254 +    void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
   1.255 +		    UFE& blossom, UFE& tree);
   1.256 +
   1.257 +    void normShrink(Node v, typename Graph::NodeMap<Node>& ear,  
   1.258 +		    UFE& blossom, UFE& tree);
   1.259 +
   1.260 +    bool noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear,  
   1.261 +		      UFE& blossom, UFE& tree, std::queue<Node>& Q);
   1.262 +
   1.263 +    void shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear,  
   1.264 +		    UFE& blossom, UFE& tree, std::queue<Node>& Q);
   1.265 +
   1.266 +    void augment(Node x, typename Graph::NodeMap<Node>& ear,  
   1.267 +		 UFE& blossom, UFE& tree);
   1.268 +
   1.269 +  };
   1.270 +
   1.271 +
   1.272 +  // **********************************************************************
   1.273 +  //  IMPLEMENTATIONS
   1.274 +  // **********************************************************************
   1.275 +
   1.276 +
   1.277 +  template <typename Graph>
   1.278 +  void MaxMatching<Graph>::run() {
   1.279 +    if ( G.edgeNum() > 2*G.nodeNum() ) {
   1.280 +      greedyMatching();
   1.281 +      runEdmonds(1);
   1.282 +    } else runEdmonds(0);
   1.283 +  }
   1.284 +
   1.285 +  template <typename Graph>
   1.286 +  void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
   1.287 +      
   1.288 +    typename Graph::template NodeMap<Node> ear(G,INVALID); 
   1.289 +    //undefined for the base nodes of the blossoms (i.e. for the
   1.290 +    //representative elements of UFE blossom) and for the nodes in C
   1.291 +      
   1.292 +    typename UFE::MapType blossom_base(G);
   1.293 +    UFE blossom(blossom_base);
   1.294 +    typename UFE::MapType tree_base(G);
   1.295 +    UFE tree(tree_base);
   1.296 +	
   1.297 +    NodeIt v;
   1.298 +    for( G.first(v); G.valid(v); G.next(v) ) {
   1.299 +      if ( position[v]==C && mate[v]==INVALID ) {
   1.300 +	blossom.insert(v);
   1.301 +	tree.insert(v); 
   1.302 +	position.set(v,D);
   1.303 +	if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
   1.304 +	else normShrink( v, ear, blossom, tree );
   1.305 +      }
   1.306 +    }
   1.307 +  }
   1.308 +    
   1.309 +  template <typename Graph>
   1.310 +  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
   1.311 +				      UFE& blossom, UFE& tree) {
   1.312 +     
   1.313 +    std::queue<Node> Q;   //queue of the totally unscanned nodes
   1.314 +    Q.push(v);  
   1.315 +    std::queue<Node> R;   
   1.316 +    //queue of the nodes which must be scanned for a possible shrink
   1.317 +      
   1.318 +    while ( !Q.empty() ) {
   1.319 +      Node x=Q.front();
   1.320 +      Q.pop();
   1.321 +      if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
   1.322 +      else R.push(x);
   1.323 +    }
   1.324 +      
   1.325 +    while ( !R.empty() ) {
   1.326 +      Node x=R.front();
   1.327 +      R.pop();
   1.328 +	
   1.329 +      OutEdgeIt e;
   1.330 +      for( G.first(e,x); G.valid(e); G.next(e) ) {
   1.331 +	Node y=G.bNode(e);
   1.332 +
   1.333 +	if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { 
   1.334 +	  //x and y must be in the same tree
   1.335 +	
   1.336 +	  typename Graph::template NodeMap<bool> path(G,false);
   1.337 +
   1.338 +	  Node b=blossom.find(x);
   1.339 +	  path.set(b,true);
   1.340 +	  b=mate[b];
   1.341 +	  while ( b!=INVALID ) { 
   1.342 +	    b=blossom.find(ear[b]);
   1.343 +	    path.set(b,true);
   1.344 +	    b=mate[b];
   1.345 +	  } //going till the root
   1.346 +	
   1.347 +	  Node top=y;
   1.348 +	  Node middle=blossom.find(top);
   1.349 +	  Node bottom=x;
   1.350 +	  while ( !path[middle] )
   1.351 +	    shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.352 +		  
   1.353 +	  Node base=middle;
   1.354 +	  top=x;
   1.355 +	  middle=blossom.find(top);
   1.356 +	  bottom=y;
   1.357 +	  Node blossom_base=blossom.find(base);
   1.358 +	  while ( middle!=blossom_base )
   1.359 +	    shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.360 +		  
   1.361 +	  blossom.makeRep(base);
   1.362 +	} // if shrink is needed
   1.363 +
   1.364 +	while ( !Q.empty() ) {
   1.365 +	  Node x=Q.front();
   1.366 +	  Q.pop();
   1.367 +	  if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
   1.368 +	  else R.push(x);
   1.369 +	}
   1.370 +      } //for e
   1.371 +    } // while ( !R.empty() )
   1.372 +  }
   1.373 +
   1.374 +  template <typename Graph>
   1.375 +  void MaxMatching<Graph>::normShrink(Node v, typename Graph::NodeMap<Node>& ear,  
   1.376 +				      UFE& blossom, UFE& tree) {
   1.377 +
   1.378 +    std::queue<Node> Q;   //queue of the unscanned nodes
   1.379 +    Q.push(v);  
   1.380 +    while ( !Q.empty() ) {
   1.381 +      Node x=Q.front();
   1.382 +      Q.pop();
   1.383 +	
   1.384 +      OutEdgeIt e;
   1.385 +      for( G.first(e,x); G.valid(e); G.next(e) ) {
   1.386 +	Node y=G.bNode(e);
   1.387 +	      
   1.388 +	switch ( position[y] ) {
   1.389 +	case D:          //x and y must be in the same tree
   1.390 +	  if ( blossom.find(x) != blossom.find(y) ) { //shrink
   1.391 +	    typename Graph::template NodeMap<bool> path(G,false);
   1.392 +	      
   1.393 +	    Node b=blossom.find(x);
   1.394 +	    path.set(b,true);
   1.395 +	    b=mate[b];
   1.396 +	    while ( b!=INVALID ) { 
   1.397 +	      b=blossom.find(ear[b]);
   1.398 +	      path.set(b,true);
   1.399 +	      b=mate[b];
   1.400 +	    } //going till the root
   1.401 +	
   1.402 +	    Node top=y;
   1.403 +	    Node middle=blossom.find(top);
   1.404 +	    Node bottom=x;
   1.405 +	    while ( !path[middle] )
   1.406 +	      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.407 +		
   1.408 +	    Node base=middle;
   1.409 +	    top=x;
   1.410 +	    middle=blossom.find(top);
   1.411 +	    bottom=y;
   1.412 +	    Node blossom_base=blossom.find(base);
   1.413 +	    while ( middle!=blossom_base )
   1.414 +	      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
   1.415 +		
   1.416 +	    blossom.makeRep(base);
   1.417 +	  }
   1.418 +	  break;
   1.419 +	case C:
   1.420 +	  if ( mate[y]!=INVALID ) {   //grow
   1.421 +	    ear.set(y,x);
   1.422 +	    Node w=mate[y];
   1.423 +	    blossom.insert(w);
   1.424 +	    position.set(y,A); 
   1.425 +	    position.set(w,D); 
   1.426 +	    tree.insert(y);
   1.427 +	    tree.insert(w);
   1.428 +	    tree.join(y,blossom.find(x));  
   1.429 +	    tree.join(w,y);  
   1.430 +	    Q.push(w);
   1.431 +	  } else {                 //augment  
   1.432 +	    augment(x, ear, blossom, tree);
   1.433 +	    mate.set(x,y);
   1.434 +	    mate.set(y,x);
   1.435 +	    return;
   1.436 +	  } //if 
   1.437 +	  break;
   1.438 +	default: break;
   1.439 +	}
   1.440 +      }
   1.441 +    }
   1.442 +  }
   1.443 +
   1.444 +  template <typename Graph>
   1.445 +  void MaxMatching<Graph>::greedyMatching() {
   1.446 +    NodeIt v;
   1.447 +    for( G.first(v); G.valid(v); G.next(v) )
   1.448 +      if ( mate[v]==INVALID ) {
   1.449 +	OutEdgeIt e;
   1.450 +	for( G.first(e,v); G.valid(e); G.next(e) ) {
   1.451 +	  Node y=G.bNode(e);
   1.452 +	  if ( mate[y]==INVALID && y!=v ) {
   1.453 +	    mate.set(v,y);
   1.454 +	    mate.set(y,v);
   1.455 +	    break;
   1.456 +	  }
   1.457 +	}
   1.458 +      } 
   1.459 +  }
   1.460 +   
   1.461 +  template <typename Graph>
   1.462 +  int MaxMatching<Graph>::size() {
   1.463 +    int s=0;
   1.464 +    NodeIt v;
   1.465 +    for(G.first(v); G.valid(v); G.next(v) ) {
   1.466 +      if ( G.valid(mate[v]) ) {
   1.467 +	++s;
   1.468 +      }
   1.469 +    }
   1.470 +    return (int)s/2;
   1.471 +  }
   1.472 +
   1.473 +  template <typename Graph>
   1.474 +  void MaxMatching<Graph>::resetPos() {
   1.475 +    NodeIt v;
   1.476 +    for( G.first(v); G.valid(v); G.next(v))
   1.477 +      position.set(v,C);      
   1.478 +  }
   1.479 +
   1.480 +  template <typename Graph>
   1.481 +  void MaxMatching<Graph>::resetMatching() {
   1.482 +    NodeIt v;
   1.483 +    for( G.first(v); G.valid(v); G.next(v))
   1.484 +      mate.set(v,INVALID);      
   1.485 +  }
   1.486 +
   1.487 +  template <typename Graph>
   1.488 +  bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear,  
   1.489 +					UFE& blossom, UFE& tree, std::queue<Node>& Q) {
   1.490 +    OutEdgeIt e;
   1.491 +    for( G.first(e,x); G.valid(e); G.next(e) ) {
   1.492 +      Node y=G.bNode(e);
   1.493 +	
   1.494 +      if ( position[y]==C ) {
   1.495 +	if ( mate[y]!=INVALID ) {       //grow
   1.496 +	  ear.set(y,x);
   1.497 +	  Node w=mate[y];
   1.498 +	  blossom.insert(w);
   1.499 +	  position.set(y,A);
   1.500 +	  position.set(w,D);
   1.501 +	  tree.insert(y);
   1.502 +	  tree.insert(w);
   1.503 +	  tree.join(y,blossom.find(x));  
   1.504 +	  tree.join(w,y);  
   1.505 +	  Q.push(w);
   1.506 +	} else {                      //augment 
   1.507 +	  augment(x, ear, blossom, tree);
   1.508 +	  mate.set(x,y);
   1.509 +	  mate.set(y,x);
   1.510 +	  return true;
   1.511 +	}
   1.512 +      }
   1.513 +    }
   1.514 +    return false;
   1.515 +  }
   1.516 +
   1.517 +  template <typename Graph>
   1.518 +  void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear,  
   1.519 +				      UFE& blossom, UFE& tree, std::queue<Node>& Q) {
   1.520 +    ear.set(top,bottom);
   1.521 +    Node t=top;
   1.522 +    while ( t!=middle ) {
   1.523 +      Node u=mate[t];
   1.524 +      t=ear[u];
   1.525 +      ear.set(t,u);
   1.526 +    } 
   1.527 +    bottom=mate[middle];
   1.528 +    position.set(bottom,D);
   1.529 +    Q.push(bottom);
   1.530 +    top=ear[bottom];		
   1.531 +    Node oldmiddle=middle;
   1.532 +    middle=blossom.find(top);
   1.533 +    tree.erase(bottom);
   1.534 +    tree.erase(oldmiddle);
   1.535 +    blossom.insert(bottom);
   1.536 +    blossom.join(bottom, oldmiddle);
   1.537 +    blossom.join(top, oldmiddle);
   1.538 +  }
   1.539 +
   1.540 +  template <typename Graph>
   1.541 +  void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear,  
   1.542 +				   UFE& blossom, UFE& tree) { 
   1.543 +    Node v=mate[x];
   1.544 +    while ( G.valid(v) ) {
   1.545 +	
   1.546 +      Node u=ear[v];
   1.547 +      mate.set(v,u);
   1.548 +      Node tmp=v;
   1.549 +      v=mate[u];
   1.550 +      mate.set(u,tmp);
   1.551 +    }
   1.552 +    typename UFE::ItemIt it;
   1.553 +    for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
   1.554 +      if ( position[it] == D ) {
   1.555 +	typename UFE::ItemIt b_it;
   1.556 +	for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {  
   1.557 +	  position.set( b_it ,C);
   1.558 +	}
   1.559 +	blossom.eraseClass(it);
   1.560 +      } else position.set( it ,C);
   1.561 +    }
   1.562 +    tree.eraseClass(x);
   1.563 +  }
   1.564 +
   1.565 +
   1.566 +
   1.567 +  /// @}
   1.568 +  
   1.569 +} //END OF NAMESPACE HUGO
   1.570 +
   1.571 +#endif //EDMONDS_H