src/lemon/max_matching.h
changeset 1435 8e85e6bbefdf
parent 1234 49d018060749
equal deleted inserted replaced
10:32598df4200c -1:000000000000
     1 /* -*- C++ -*-
       
     2  * src/lemon/max_matching.h - Part of LEMON, a generic C++ optimization library
       
     3  *
       
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     6  *
       
     7  * Permission to use, modify and distribute this software is granted
       
     8  * provided that this copyright notice appears in all copies. For
       
     9  * precise terms see the accompanying LICENSE file.
       
    10  *
       
    11  * This software is provided "AS IS" with no warranty of any kind,
       
    12  * express or implied, and with no claim as to its suitability for any
       
    13  * purpose.
       
    14  *
       
    15  */
       
    16 
       
    17 #ifndef LEMON_MAX_MATCHING_H
       
    18 #define LEMON_MAX_MATCHING_H
       
    19 
       
    20 #include <queue>
       
    21 #include <lemon/invalid.h>
       
    22 #include <lemon/unionfind.h>
       
    23 #include <lemon/graph_utils.h>
       
    24 
       
    25 ///\ingroup galgs
       
    26 ///\file
       
    27 ///\brief Maximum matching algorithm.
       
    28 
       
    29 namespace lemon {
       
    30 
       
    31   /// \addtogroup galgs
       
    32   /// @{
       
    33 
       
    34   ///Edmonds' alternating forest maximum matching algorithm.
       
    35 
       
    36   ///This class provides Edmonds' alternating forest matching
       
    37   ///algorithm. The starting matching (if any) can be passed to the
       
    38   ///algorithm using read-in functions \ref readNMapNode, \ref
       
    39   ///readNMapEdge or \ref readEMapBool depending on the container. The
       
    40   ///resulting maximum matching can be attained by write-out functions
       
    41   ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool
       
    42   ///depending on the preferred container. 
       
    43   ///
       
    44   ///The dual side of a matching is a map of the nodes to
       
    45   ///MaxMatching::pos_enum, having values D, A and C showing the
       
    46   ///Gallai-Edmonds decomposition of the graph. The nodes in D induce
       
    47   ///a graph with factor-critical components, the nodes in A form the
       
    48   ///barrier, and the nodes in C induce a graph having a perfect
       
    49   ///matching. This decomposition can be attained by calling \ref
       
    50   ///writePos after running the algorithm. 
       
    51   ///
       
    52   ///\param Graph The undirected graph type the algorithm runs on.
       
    53   ///
       
    54   ///\author Jacint Szabo  
       
    55   template <typename Graph>
       
    56   class MaxMatching {
       
    57 
       
    58   protected:
       
    59 
       
    60     typedef typename Graph::Node Node;
       
    61     typedef typename Graph::Edge Edge;
       
    62     typedef typename Graph::UndirEdge UndirEdge;
       
    63     typedef typename Graph::UndirEdgeIt UndirEdgeIt;
       
    64     typedef typename Graph::NodeIt NodeIt;
       
    65     typedef typename Graph::IncEdgeIt IncEdgeIt;
       
    66 
       
    67     typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
       
    68 
       
    69   public:
       
    70     
       
    71     ///Indicates the Gallai-Edmonds decomposition of the graph.
       
    72 
       
    73     ///Indicates the Gallai-Edmonds decomposition of the graph, which
       
    74     ///shows an upper bound on the size of a maximum matching. The
       
    75     ///nodes with pos_enum \c D induce a graph with factor-critical
       
    76     ///components, the nodes in \c A form the canonical barrier, and the
       
    77     ///nodes in \c C induce a graph having a perfect matching. 
       
    78     enum pos_enum {
       
    79       D=0,
       
    80       A=1,
       
    81       C=2
       
    82     }; 
       
    83 
       
    84   protected:
       
    85 
       
    86     static const int HEUR_density=2;
       
    87     const Graph& g;
       
    88     typename Graph::template NodeMap<Node> _mate;
       
    89     typename Graph::template NodeMap<pos_enum> position;
       
    90      
       
    91   public:
       
    92     
       
    93     MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
       
    94 
       
    95     ///Runs Edmonds' algorithm.
       
    96 
       
    97     ///Runs Edmonds' algorithm for sparse graphs (number of edges <
       
    98     ///2*number of nodes), and a heuristical Edmonds' algorithm with a
       
    99     ///heuristic of postponing shrinks for dense graphs. 
       
   100     inline void run();
       
   101 
       
   102     ///Runs Edmonds' algorithm.
       
   103     
       
   104     ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
       
   105     ///Edmonds' algorithm with a heuristic of postponing shrinks,
       
   106     ///giving a faster algorithm for dense graphs.  
       
   107     void runEdmonds( int heur );
       
   108 
       
   109     ///Finds a greedy matching starting from the actual matching.
       
   110     
       
   111     ///Starting form the actual matching stored, it finds a maximal
       
   112     ///greedy matching.
       
   113     void greedyMatching();
       
   114 
       
   115     ///Returns the size of the actual matching stored.
       
   116 
       
   117     ///Returns the size of the actual matching stored. After \ref
       
   118     ///run() it returns the size of a maximum matching in the graph.
       
   119     int size() const;
       
   120 
       
   121     ///Resets the actual matching to the empty matching.
       
   122 
       
   123     ///Resets the actual matching to the empty matching.  
       
   124     ///
       
   125     void resetMatching();
       
   126 
       
   127     ///Returns the mate of a node in the actual matching.
       
   128 
       
   129     ///Returns the mate of a \c node in the actual matching. 
       
   130     ///Returns INVALID if the \c node is not covered by the actual matching. 
       
   131     Node mate(Node& node) const {
       
   132       return _mate[node];
       
   133     } 
       
   134 
       
   135     ///Reads a matching from a \c Node valued \c Node map.
       
   136 
       
   137     ///Reads a matching from a \c Node valued \c Node map. This map
       
   138     ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u
       
   139     ///must hold, and \c uv will be an edge of the matching.
       
   140     template<typename NMapN>
       
   141     void readNMapNode(NMapN& map) {
       
   142       for(NodeIt v(g); v!=INVALID; ++v) {
       
   143 	_mate.set(v,map[v]);   
       
   144       } 
       
   145     } 
       
   146     
       
   147     ///Writes the stored matching to a \c Node valued \c Node map.
       
   148 
       
   149     ///Writes the stored matching to a \c Node valued \c Node map. The
       
   150     ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c
       
   151     ///map[v]==u will hold, and now \c uv is an edge of the matching.
       
   152     template<typename NMapN>
       
   153     void writeNMapNode (NMapN& map) const {
       
   154       for(NodeIt v(g); v!=INVALID; ++v) {
       
   155 	map.set(v,_mate[v]);   
       
   156       } 
       
   157     } 
       
   158 
       
   159     ///Reads a matching from an \c UndirEdge valued \c Node map.
       
   160 
       
   161     ///Reads a matching from an \c UndirEdge valued \c Node map. \c
       
   162     ///map[v] must be an \c UndirEdge incident to \c v. This map must
       
   163     ///have the property that if \c g.oppositeNode(u,map[u])==v then
       
   164     ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge
       
   165     ///joining \c u to \c v will be an edge of the matching.
       
   166     template<typename NMapE>
       
   167     void readNMapEdge(NMapE& map) {
       
   168      for(NodeIt v(g); v!=INVALID; ++v) {
       
   169        UndirEdge e=map[v];
       
   170 	if ( e!=INVALID )
       
   171 	  _mate.set(v,g.oppositeNode(v,e));
       
   172       } 
       
   173     } 
       
   174     
       
   175     ///Writes the matching stored to an \c UndirEdge valued \c Node map.
       
   176 
       
   177     ///Writes the stored matching to an \c UndirEdge valued \c Node
       
   178     ///map. \c map[v] will be an \c UndirEdge incident to \c v. This
       
   179     ///map will have the property that if \c g.oppositeNode(u,map[u])
       
   180     ///== v then \c map[u]==map[v] holds, and now this edge is an edge
       
   181     ///of the matching.
       
   182     template<typename NMapE>
       
   183     void writeNMapEdge (NMapE& map)  const {
       
   184       typename Graph::template NodeMap<bool> todo(g,true); 
       
   185       for(NodeIt v(g); v!=INVALID; ++v) {
       
   186 	if ( todo[v] && _mate[v]!=INVALID ) {
       
   187 	  Node u=_mate[v];
       
   188 	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
       
   189 	    if ( g.runningNode(e) == u ) {
       
   190 	      map.set(u,e);
       
   191 	      map.set(v,e);
       
   192 	      todo.set(u,false);
       
   193 	      todo.set(v,false);
       
   194 	      break;
       
   195 	    }
       
   196 	  }
       
   197 	}
       
   198       } 
       
   199     }
       
   200 
       
   201 
       
   202     ///Reads a matching from a \c bool valued \c Edge map.
       
   203     
       
   204     ///Reads a matching from a \c bool valued \c Edge map. This map
       
   205     ///must have the property that there are no two incident edges \c
       
   206     ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
       
   207     ///map[e]==true form the matching.
       
   208     template<typename EMapB>
       
   209     void readEMapBool(EMapB& map) {
       
   210       for(UndirEdgeIt e(g); e!=INVALID; ++e) {
       
   211 	if ( map[e] ) {
       
   212 	  Node u=g.source(e);	  
       
   213 	  Node v=g.target(e);
       
   214 	  _mate.set(u,v);
       
   215 	  _mate.set(v,u);
       
   216 	} 
       
   217       } 
       
   218     }
       
   219 
       
   220 
       
   221     ///Writes the matching stored to a \c bool valued \c Edge map.
       
   222 
       
   223     ///Writes the matching stored to a \c bool valued \c Edge
       
   224     ///map. This map will have the property that there are no two
       
   225     ///incident edges \c e, \c f with \c map[e]==map[f]==true. The
       
   226     ///edges \c e with \c map[e]==true form the matching.
       
   227     template<typename EMapB>
       
   228     void writeEMapBool (EMapB& map) const {
       
   229       for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
       
   230 
       
   231       typename Graph::template NodeMap<bool> todo(g,true); 
       
   232       for(NodeIt v(g); v!=INVALID; ++v) {
       
   233 	if ( todo[v] && _mate[v]!=INVALID ) {
       
   234 	  Node u=_mate[v];
       
   235 	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
       
   236 	    if ( g.runningNode(e) == u ) {
       
   237 	      map.set(e,true);
       
   238 	      todo.set(u,false);
       
   239 	      todo.set(v,false);
       
   240 	      break;
       
   241 	    }
       
   242 	  }
       
   243 	}
       
   244       } 
       
   245     }
       
   246 
       
   247 
       
   248     ///Writes the canonical decomposition of the graph after running
       
   249     ///the algorithm.
       
   250 
       
   251     ///After calling any run methods of the class, it writes the
       
   252     ///Gallai-Edmonds canonical decomposition of the graph. \c map
       
   253     ///must be a node map of \ref pos_enum 's.
       
   254     template<typename NMapEnum>
       
   255     void writePos (NMapEnum& map) const {
       
   256       for(NodeIt v(g); v!=INVALID; ++v)  map.set(v,position[v]);
       
   257     }
       
   258 
       
   259   private: 
       
   260 
       
   261  
       
   262     void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
       
   263 		    UFE& blossom, UFE& tree);
       
   264 
       
   265     void normShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
       
   266 		    UFE& blossom, UFE& tree);
       
   267 
       
   268     bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear,  
       
   269 		      UFE& blossom, UFE& tree, std::queue<Node>& Q);
       
   270 
       
   271     void shrinkStep(Node& top, Node& middle, Node& bottom,
       
   272 		    typename Graph::template NodeMap<Node>& ear,  
       
   273 		    UFE& blossom, UFE& tree, std::queue<Node>& Q);
       
   274 
       
   275     void augment(Node x, typename Graph::template NodeMap<Node>& ear,  
       
   276 		 UFE& blossom, UFE& tree);
       
   277 
       
   278   };
       
   279 
       
   280 
       
   281   // **********************************************************************
       
   282   //  IMPLEMENTATIONS
       
   283   // **********************************************************************
       
   284 
       
   285 
       
   286   template <typename Graph>
       
   287   void MaxMatching<Graph>::run() {
       
   288     if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
       
   289       greedyMatching();
       
   290       runEdmonds(0);
       
   291     } else runEdmonds(1);
       
   292   }
       
   293 
       
   294 
       
   295   template <typename Graph>
       
   296   void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
       
   297 
       
   298     for(NodeIt v(g); v!=INVALID; ++v)
       
   299       position.set(v,C);      
       
   300 
       
   301     typename Graph::template NodeMap<Node> ear(g,INVALID); 
       
   302     //undefined for the base nodes of the blossoms (i.e. for the
       
   303     //representative elements of UFE blossom) and for the nodes in C 
       
   304 
       
   305     typename UFE::MapType blossom_base(g);
       
   306     UFE blossom(blossom_base);
       
   307     typename UFE::MapType tree_base(g);
       
   308     UFE tree(tree_base);
       
   309     //If these UFE's would be members of the class then also
       
   310     //blossom_base and tree_base should be a member.
       
   311 
       
   312     for(NodeIt v(g); v!=INVALID; ++v) {
       
   313       if ( position[v]==C && _mate[v]==INVALID ) {
       
   314 	blossom.insert(v);
       
   315 	tree.insert(v); 
       
   316 	position.set(v,D);
       
   317 	if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
       
   318 	else normShrink( v, ear, blossom, tree );
       
   319       }
       
   320     }
       
   321   }
       
   322 
       
   323     
       
   324   template <typename Graph>
       
   325   void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
       
   326 				      UFE& blossom, UFE& tree) {
       
   327 
       
   328     std::queue<Node> Q;   //queue of the totally unscanned nodes
       
   329     Q.push(v);  
       
   330     std::queue<Node> R;   
       
   331     //queue of the nodes which must be scanned for a possible shrink
       
   332       
       
   333     while ( !Q.empty() ) {
       
   334       Node x=Q.front();
       
   335       Q.pop();
       
   336       if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
       
   337       else R.push(x);
       
   338     }
       
   339       
       
   340     while ( !R.empty() ) {
       
   341       Node x=R.front();
       
   342       R.pop();
       
   343 	
       
   344       for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
       
   345 	Node y=g.runningNode(e);
       
   346 
       
   347 	if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { 
       
   348 	  //x and y must be in the same tree
       
   349 	
       
   350 	  typename Graph::template NodeMap<bool> path(g,false);
       
   351 
       
   352 	  Node b=blossom.find(x);
       
   353 	  path.set(b,true);
       
   354 	  b=_mate[b];
       
   355 	  while ( b!=INVALID ) { 
       
   356 	    b=blossom.find(ear[b]);
       
   357 	    path.set(b,true);
       
   358 	    b=_mate[b];
       
   359 	  } //going till the root
       
   360 	
       
   361 	  Node top=y;
       
   362 	  Node middle=blossom.find(top);
       
   363 	  Node bottom=x;
       
   364 	  while ( !path[middle] )
       
   365 	    shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
       
   366 		  
       
   367 	  Node base=middle;
       
   368 	  top=x;
       
   369 	  middle=blossom.find(top);
       
   370 	  bottom=y;
       
   371 	  Node blossom_base=blossom.find(base);
       
   372 	  while ( middle!=blossom_base )
       
   373 	    shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
       
   374 		  
       
   375 	  blossom.makeRep(base);
       
   376 	} // if shrink is needed
       
   377 
       
   378 	while ( !Q.empty() ) {
       
   379 	  Node x=Q.front();
       
   380 	  Q.pop();
       
   381 	  if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
       
   382 	  else R.push(x);
       
   383 	}
       
   384       } //for e
       
   385     } // while ( !R.empty() )
       
   386   }
       
   387 
       
   388 
       
   389   template <typename Graph>
       
   390   void MaxMatching<Graph>::normShrink(Node v,
       
   391 				      typename Graph::template
       
   392 				      NodeMap<Node>& ear,  
       
   393 				      UFE& blossom, UFE& tree) {
       
   394     std::queue<Node> Q;   //queue of the unscanned nodes
       
   395     Q.push(v);  
       
   396     while ( !Q.empty() ) {
       
   397 
       
   398       Node x=Q.front();
       
   399       Q.pop();
       
   400 	
       
   401       for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
       
   402 	Node y=g.runningNode(e);
       
   403 	      
       
   404 	switch ( position[y] ) {
       
   405 	case D:          //x and y must be in the same tree
       
   406 
       
   407 	  if ( blossom.find(x) != blossom.find(y) ) { //shrink
       
   408 	    typename Graph::template NodeMap<bool> path(g,false);
       
   409 	      
       
   410 	    Node b=blossom.find(x);
       
   411 	    path.set(b,true);
       
   412 	    b=_mate[b];
       
   413 	    while ( b!=INVALID ) { 
       
   414 	      b=blossom.find(ear[b]);
       
   415 	      path.set(b,true);
       
   416 	      b=_mate[b];
       
   417 	    } //going till the root
       
   418 	
       
   419 	    Node top=y;
       
   420 	    Node middle=blossom.find(top);
       
   421 	    Node bottom=x;
       
   422 	    while ( !path[middle] )
       
   423 	      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
       
   424 		
       
   425 	    Node base=middle;
       
   426 	    top=x;
       
   427 	    middle=blossom.find(top);
       
   428 	    bottom=y;
       
   429 	    Node blossom_base=blossom.find(base);
       
   430 	    while ( middle!=blossom_base )
       
   431 	      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
       
   432 		
       
   433 	    blossom.makeRep(base);
       
   434 	  }
       
   435 	  break;
       
   436 	case C:
       
   437 	  if ( _mate[y]!=INVALID ) {   //grow
       
   438 
       
   439 	    ear.set(y,x);
       
   440 	    Node w=_mate[y];
       
   441 	    blossom.insert(w);
       
   442 	    position.set(y,A); 
       
   443 	    position.set(w,D); 
       
   444 	    tree.insert(y);
       
   445 	    tree.insert(w);
       
   446 	    tree.join(y,blossom.find(x));  
       
   447 	    tree.join(w,y);  
       
   448 	    Q.push(w);
       
   449 	  } else {                 //augment  
       
   450 	    augment(x, ear, blossom, tree);
       
   451 	    _mate.set(x,y);
       
   452 	    _mate.set(y,x);
       
   453 	    return;
       
   454 	  } //if 
       
   455 	  break;
       
   456 	default: break;
       
   457 	}
       
   458       }
       
   459     }
       
   460   }
       
   461 
       
   462   template <typename Graph>
       
   463   void MaxMatching<Graph>::greedyMatching() {
       
   464     for(NodeIt v(g); v!=INVALID; ++v)
       
   465       if ( _mate[v]==INVALID ) {
       
   466 	for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
       
   467 	  Node y=g.runningNode(e);
       
   468 	  if ( _mate[y]==INVALID && y!=v ) {
       
   469 	    _mate.set(v,y);
       
   470 	    _mate.set(y,v);
       
   471 	    break;
       
   472 	  }
       
   473 	}
       
   474       } 
       
   475   }
       
   476    
       
   477   template <typename Graph>
       
   478   int MaxMatching<Graph>::size() const {
       
   479     int s=0;
       
   480     for(NodeIt v(g); v!=INVALID; ++v) {
       
   481       if ( _mate[v]!=INVALID ) {
       
   482 	++s;
       
   483       }
       
   484     }
       
   485     return s/2;
       
   486   }
       
   487 
       
   488   template <typename Graph>
       
   489   void MaxMatching<Graph>::resetMatching() {
       
   490     for(NodeIt v(g); v!=INVALID; ++v)
       
   491       _mate.set(v,INVALID);      
       
   492   }
       
   493 
       
   494   template <typename Graph>
       
   495   bool MaxMatching<Graph>::noShrinkStep(Node x,
       
   496 					typename Graph::template 
       
   497 					NodeMap<Node>& ear,  
       
   498 					UFE& blossom, UFE& tree,
       
   499 					std::queue<Node>& Q) {
       
   500     for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
       
   501       Node y=g.runningNode(e);
       
   502 	
       
   503       if ( position[y]==C ) {
       
   504 	if ( _mate[y]!=INVALID ) {       //grow
       
   505 	  ear.set(y,x);
       
   506 	  Node w=_mate[y];
       
   507 	  blossom.insert(w);
       
   508 	  position.set(y,A);
       
   509 	  position.set(w,D);
       
   510 	  tree.insert(y);
       
   511 	  tree.insert(w);
       
   512 	  tree.join(y,blossom.find(x));  
       
   513 	  tree.join(w,y);  
       
   514 	  Q.push(w);
       
   515 	} else {                      //augment 
       
   516 	  augment(x, ear, blossom, tree);
       
   517 	  _mate.set(x,y);
       
   518 	  _mate.set(y,x);
       
   519 	  return true;
       
   520 	}
       
   521       }
       
   522     }
       
   523     return false;
       
   524   }
       
   525 
       
   526   template <typename Graph>
       
   527   void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom,
       
   528 				      typename Graph::template
       
   529 				      NodeMap<Node>& ear,  
       
   530 				      UFE& blossom, UFE& tree,
       
   531 				      std::queue<Node>& Q) {
       
   532     ear.set(top,bottom);
       
   533     Node t=top;
       
   534     while ( t!=middle ) {
       
   535       Node u=_mate[t];
       
   536       t=ear[u];
       
   537       ear.set(t,u);
       
   538     } 
       
   539     bottom=_mate[middle];
       
   540     position.set(bottom,D);
       
   541     Q.push(bottom);
       
   542     top=ear[bottom];		
       
   543     Node oldmiddle=middle;
       
   544     middle=blossom.find(top);
       
   545     tree.erase(bottom);
       
   546     tree.erase(oldmiddle);
       
   547     blossom.insert(bottom);
       
   548     blossom.join(bottom, oldmiddle);
       
   549     blossom.join(top, oldmiddle);
       
   550   }
       
   551 
       
   552   template <typename Graph>
       
   553   void MaxMatching<Graph>::augment(Node x,
       
   554 				   typename Graph::template NodeMap<Node>& ear,  
       
   555 				   UFE& blossom, UFE& tree) { 
       
   556     Node v=_mate[x];
       
   557     while ( v!=INVALID ) {
       
   558 	
       
   559       Node u=ear[v];
       
   560       _mate.set(v,u);
       
   561       Node tmp=v;
       
   562       v=_mate[u];
       
   563       _mate.set(u,tmp);
       
   564     }
       
   565     typename UFE::ItemIt it;
       
   566     for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
       
   567       if ( position[it] == D ) {
       
   568 	typename UFE::ItemIt b_it;
       
   569 	for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {  
       
   570 	  position.set( b_it ,C);
       
   571 	}
       
   572 	blossom.eraseClass(it);
       
   573       } else position.set( it ,C);
       
   574     }
       
   575     tree.eraseClass(x);
       
   576 
       
   577   }
       
   578 
       
   579   /// @}
       
   580   
       
   581 } //END OF NAMESPACE LEMON
       
   582 
       
   583 #endif //LEMON_MAX_MATCHING_H