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