Index: lemon/max_matching.h
===================================================================
--- lemon/max_matching.h	(revision 2391)
+++ lemon/max_matching.h	(revision 2505)
@@ -31,23 +31,19 @@
 namespace lemon {
 
-  /// \ingroup matching
-
-  ///Edmonds' alternating forest maximum matching algorithm.
-
+  ///\ingroup matching
+
+  ///\brief Edmonds' alternating forest maximum matching algorithm.
+  ///
   ///This class provides Edmonds' alternating forest matching
   ///algorithm. The starting matching (if any) can be passed to the
-  ///algorithm using read-in functions \ref readNMapNode, \ref
-  ///readNMapEdge or \ref readEMapBool depending on the container. The
-  ///resulting maximum matching can be attained by write-out functions
-  ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool
-  ///depending on the preferred container. 
+  ///algorithm using some of init functions.
   ///
   ///The dual side of a matching is a map of the nodes to
-  ///MaxMatching::pos_enum, having values D, A and C showing the
-  ///Gallai-Edmonds decomposition of the graph. The nodes in D induce
-  ///a graph with factor-critical components, the nodes in A form the
-  ///barrier, and the nodes in C induce a graph having a perfect
-  ///matching. This decomposition can be attained by calling \ref
-  ///writePos after running the algorithm. 
+  ///MaxMatching::DecompType, having values \c D, \c A and \c C
+  ///showing the Gallai-Edmonds decomposition of the graph. The nodes
+  ///in \c D induce a graph with factor-critical components, the nodes
+  ///in \c A form the barrier, and the nodes in \c C induce a graph
+  ///having a perfect matching. This decomposition can be attained by
+  ///calling \c decomposition() after running the algorithm.
   ///
   ///\param Graph The undirected graph type the algorithm runs on.
@@ -68,15 +64,19 @@
     typedef typename Graph::template NodeMap<int> UFECrossRef;
     typedef UnionFindEnum<UFECrossRef> UFE;
+    typedef std::vector<Node> NV;
+
+    typedef typename Graph::template NodeMap<int> EFECrossRef;
+    typedef ExtendFindEnum<EFECrossRef> EFE;
 
   public:
     
-    ///Indicates the Gallai-Edmonds decomposition of the graph.
-
+    ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
+    ///
     ///Indicates the Gallai-Edmonds decomposition of the graph, which
     ///shows an upper bound on the size of a maximum matching. The
-    ///nodes with pos_enum \c D induce a graph with factor-critical
+    ///nodes with DecompType \c D induce a graph with factor-critical
     ///components, the nodes in \c A form the canonical barrier, and the
     ///nodes in \c C induce a graph having a perfect matching. 
-    enum pos_enum {
+    enum DecompType {
       D=0,
       A=1,
@@ -89,69 +89,30 @@
     const Graph& g;
     typename Graph::template NodeMap<Node> _mate;
-    typename Graph::template NodeMap<pos_enum> position;
+    typename Graph::template NodeMap<DecompType> position;
      
   public:
     
-    MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
-
-    ///Runs Edmonds' algorithm.
-
-    ///Runs Edmonds' algorithm for sparse graphs (number of edges <
-    ///2*number of nodes), and a heuristical Edmonds' algorithm with a
-    ///heuristic of postponing shrinks for dense graphs. 
-    void run() {
-      if ( countUEdges(g) < HEUR_density*countNodes(g) ) {
-	greedyMatching();
-	runEdmonds(0);
-      } else runEdmonds(1);
-    }
-
-
-    ///Runs Edmonds' algorithm.
-    
-    ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
-    ///Edmonds' algorithm with a heuristic of postponing shrinks,
-    ///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);      
-      
-      typename Graph::template NodeMap<Node> ear(g,INVALID); 
-      //undefined for the base nodes of the blossoms (i.e. for the
-      //representative elements of UFE blossom) and for the nodes in C 
-      
-      UFECrossRef blossom_base(g);
-      UFE blossom(blossom_base);
-
-      UFECrossRef tree_base(g);
-      UFE tree(tree_base);
-
-      //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);
-	  tree.insert(v); 
-	  position.set(v,D);
-	  if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
-	  else normShrink( v, ear, blossom, tree );
-	}
-      }
-    }
-
-
-    ///Finds a greedy matching starting from the actual matching.
-    
-    ///Starting form the actual matching stored, it finds a maximal
-    ///greedy matching.
-    void greedyMatching() {
+    MaxMatching(const Graph& _g) 
+      : g(_g), _mate(_g), position(_g) {}
+
+    ///\brief Sets the actual matching to the empty matching.
+    ///
+    ///Sets the actual matching to the empty matching.  
+    ///
+    void init() {
+      for(NodeIt v(g); v!=INVALID; ++v) {
+	_mate.set(v,INVALID);      
+	position.set(v,C);
+      }
+    }
+
+    ///\brief Finds a greedy matching for initial matching.
+    ///
+    ///For initial matchig it finds a maximal greedy matching.
+    void greedyInit() {
+      for(NodeIt v(g); v!=INVALID; ++v) {
+	_mate.set(v,INVALID);      
+	position.set(v,C);
+      }
       for(NodeIt v(g); v!=INVALID; ++v)
 	if ( _mate[v]==INVALID ) {
@@ -167,6 +128,151 @@
     }
 
-    ///Returns the size of the actual matching stored.
-
+    ///\brief Initialize the matching from each nodes' mate.
+    ///
+    ///Initialize the matching from a \c Node valued \c Node map. This
+    ///map must be \e symmetric, i.e. if \c map[u]==v then \c
+    ///map[v]==u must hold, and \c uv will be an edge of the initial
+    ///matching.
+    template <typename MateMap>
+    void mateMapInit(MateMap& map) {
+      for(NodeIt v(g); v!=INVALID; ++v) {
+	_mate.set(v,map[v]);
+	position.set(v,C);
+      } 
+    }
+
+    ///\brief Initialize the matching from a node map with the
+    ///incident matching edges.
+    ///
+    ///Initialize the matching from an \c UEdge valued \c Node map. \c
+    ///map[v] must be an \c UEdge incident to \c v. This map must have
+    ///the property that if \c g.oppositeNode(u,map[u])==v then \c \c
+    ///g.oppositeNode(v,map[v])==u holds, and now some edge joining \c
+    ///u to \c v will be an edge of the matching.
+    template<typename MatchingMap>
+    void matchingMapInit(MatchingMap& map) {
+      for(NodeIt v(g); v!=INVALID; ++v) {
+	position.set(v,C);
+	UEdge e=map[v];
+	if ( e!=INVALID )
+	  _mate.set(v,g.oppositeNode(v,e));
+	else 
+	  _mate.set(v,INVALID);
+      } 
+    } 
+
+    ///\brief Initialize the matching from the map containing the
+    ///undirected matching edges.
+    ///
+    ///Initialize the matching from a \c bool valued \c UEdge map. This
+    ///map must have the property that there are no two incident edges
+    ///\c e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
+    ///map[e]==true form the matching.
+    template <typename MatchingMap>
+    void matchingInit(MatchingMap& map) {
+      for(NodeIt v(g); v!=INVALID; ++v) {
+	_mate.set(v,INVALID);      
+	position.set(v,C);
+      }
+      for(UEdgeIt e(g); e!=INVALID; ++e) {
+	if ( map[e] ) {
+	  Node u=g.source(e);	  
+	  Node v=g.target(e);
+	  _mate.set(u,v);
+	  _mate.set(v,u);
+	} 
+      } 
+    }
+
+
+    ///\brief Runs Edmonds' algorithm.
+    ///
+    ///Runs Edmonds' algorithm for sparse graphs (number of edges <
+    ///2*number of nodes), and a heuristical Edmonds' algorithm with a
+    ///heuristic of postponing shrinks for dense graphs. 
+    void run() {
+      if (countUEdges(g) < HEUR_density * countNodes(g)) {
+	greedyInit();
+	startSparse();
+      } else {
+	init();
+	startDense();
+      }
+    }
+
+
+    ///\brief Starts Edmonds' algorithm.
+    /// 
+    ///If runs the original Edmonds' algorithm.  
+    void startSparse() {
+            
+      typename Graph::template NodeMap<Node> ear(g,INVALID); 
+      //undefined for the base nodes of the blossoms (i.e. for the
+      //representative elements of UFE blossom) and for the nodes in C 
+      
+      UFECrossRef blossom_base(g);
+      UFE blossom(blossom_base);
+      NV rep(countNodes(g));
+
+      EFECrossRef tree_base(g);
+      EFE tree(tree_base);
+
+      //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) {
+	  rep[blossom.insert(v)] = v;
+	  tree.insert(v); 
+	  position.set(v,D);
+	  normShrink(v, ear, blossom, rep, tree);
+	}
+      }
+    }
+
+    ///\brief Starts Edmonds' algorithm.
+    /// 
+    ///It runs Edmonds' algorithm with a heuristic of postponing
+    ///shrinks, giving a faster algorithm for dense graphs.
+    void startDense() {
+            
+      typename Graph::template NodeMap<Node> ear(g,INVALID); 
+      //undefined for the base nodes of the blossoms (i.e. for the
+      //representative elements of UFE blossom) and for the nodes in C 
+      
+      UFECrossRef blossom_base(g);
+      UFE blossom(blossom_base);
+      NV rep(countNodes(g));
+
+      EFECrossRef tree_base(g);
+      EFE tree(tree_base);
+
+      //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 ) {
+	  rep[blossom.insert(v)] = v;
+	  tree.insert(v); 
+	  position.set(v,D);
+	  lateShrink(v, ear, blossom, rep, tree);
+	}
+      }
+    }
+
+
+
+    ///\brief Returns the size of the actual matching stored.
+    ///
     ///Returns the size of the actual matching stored. After \ref
     ///run() it returns the size of a maximum matching in the graph.
@@ -182,63 +288,58 @@
 
 
-    ///Resets the actual matching to the empty matching.
-
-    ///Resets the actual matching to the empty matching.  
-    ///
-    void resetMatching() {
-      for(NodeIt v(g); v!=INVALID; ++v)
-	_mate.set(v,INVALID);      
-    }
-
-    ///Returns the mate of a node in the actual matching.
-
+    ///\brief Returns the mate of a node in the actual matching.
+    ///
     ///Returns the mate of a \c node in the actual matching. 
     ///Returns INVALID if the \c node is not covered by the actual matching. 
-    Node mate(Node& node) const {
+    Node mate(const Node& node) const {
       return _mate[node];
     } 
 
-    ///Reads a matching from a \c Node valued \c Node map.
-
-    ///Reads a matching from a \c Node valued \c Node map. This map
-    ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u
-    ///must hold, and \c uv will be an edge of the matching.
-    template<typename NMapN>
-    void readNMapNode(NMapN& map) {
-      for(NodeIt v(g); v!=INVALID; ++v) {
-	_mate.set(v,map[v]);   
-      } 
+    ///\brief Returns the matching edge incident to the given node.
+    ///
+    ///Returns the matching edge of a \c node in the actual matching. 
+    ///Returns INVALID if the \c node is not covered by the actual matching. 
+    UEdge matchingEdge(const Node& node) const {
+      if (_mate[node] == INVALID) return INVALID;
+      Node n = node < _mate[node] ? node : _mate[node];
+      for (IncEdgeIt e(g, n); e != INVALID; ++e) {
+	if (g.oppositeNode(n, e) == _mate[n]) {
+	  return e;
+	}
+      }
+      return INVALID;
     } 
-    
-    ///Writes the stored matching to a \c Node valued \c Node map.
-
+
+    /// \brief Returns the class of the node in the Edmonds-Gallai
+    /// decomposition.
+    ///
+    /// Returns the class of the node in the Edmonds-Gallai
+    /// decomposition.
+    DecompType decomposition(const Node& n) {
+      return position[n] == A;
+    }
+
+    /// \brief Returns true when the node is in the barrier.
+    ///
+    /// Returns true when the node is in the barrier.
+    bool barrier(const Node& n) {
+      return position[n] == A;
+    }
+    
+    ///\brief Gives back the matching in a \c Node of mates.
+    ///
     ///Writes the stored matching to a \c Node valued \c Node map. The
     ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c
     ///map[v]==u will hold, and now \c uv is an edge of the matching.
-    template<typename NMapN>
-    void writeNMapNode (NMapN& map) const {
+    template <typename MateMap>
+    void mateMap(MateMap& map) const {
       for(NodeIt v(g); v!=INVALID; ++v) {
 	map.set(v,_mate[v]);   
       } 
     } 
-
-    ///Reads a matching from an \c UEdge valued \c Node map.
-
-    ///Reads a matching from an \c UEdge valued \c Node map. \c
-    ///map[v] must be an \c UEdge incident to \c v. This map must
-    ///have the property that if \c g.oppositeNode(u,map[u])==v then
-    ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge
-    ///joining \c u to \c v will be an edge of the matching.
-    template<typename NMapE>
-    void readNMapEdge(NMapE& map) {
-      for(NodeIt v(g); v!=INVALID; ++v) {
-	UEdge e=map[v];
-	if ( e!=INVALID )
-	  _mate.set(v,g.oppositeNode(v,e));
-      } 
-    } 
-    
-    ///Writes the matching stored to an \c UEdge valued \c Node map.
-
+    
+    ///\brief Gives back the matching in an \c UEdge valued \c Node
+    ///map.
+    ///
     ///Writes the stored matching to an \c UEdge valued \c Node
     ///map. \c map[v] will be an \c UEdge incident to \c v. This
@@ -246,9 +347,9 @@
     ///== v then \c map[u]==map[v] holds, and now this edge is an edge
     ///of the matching.
-    template<typename NMapE>
-    void writeNMapEdge (NMapE& map)  const {
+    template <typename MatchingMap>
+    void matchingMap(MatchingMap& map)  const {
       typename Graph::template NodeMap<bool> todo(g,true); 
       for(NodeIt v(g); v!=INVALID; ++v) {
-	if ( todo[v] && _mate[v]!=INVALID ) {
+	if (_mate[v]!=INVALID && v < _mate[v]) {
 	  Node u=_mate[v];
 	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
@@ -266,31 +367,13 @@
 
 
-    ///Reads a matching from a \c bool valued \c Edge map.
-    
-    ///Reads a matching from a \c bool valued \c Edge map. This map
-    ///must have the property that there are no two incident edges \c
-    ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
-    ///map[e]==true form the matching.
-    template<typename EMapB>
-    void readEMapBool(EMapB& map) {
-      for(UEdgeIt e(g); e!=INVALID; ++e) {
-	if ( map[e] ) {
-	  Node u=g.source(e);	  
-	  Node v=g.target(e);
-	  _mate.set(u,v);
-	  _mate.set(v,u);
-	} 
-      } 
-    }
-
-
-    ///Writes the matching stored to a \c bool valued \c Edge map.
-
+    ///\brief Gives back the matching in a \c bool valued \c UEdge
+    ///map.
+    ///
     ///Writes the matching stored to a \c bool valued \c Edge
     ///map. This map will have the property that there are no two
     ///incident edges \c e, \c f with \c map[e]==map[f]==true. The
     ///edges \c e with \c map[e]==true form the matching.
-    template<typename EMapB>
-    void writeEMapBool (EMapB& map) const {
+    template<typename MatchingMap>
+    void matching(MatchingMap& map) const {
       for(UEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
 
@@ -312,13 +395,25 @@
 
 
-    ///Writes the canonical decomposition of the graph after running
+    ///\brief Returns the canonical decomposition of the graph after running
     ///the algorithm.
-
+    ///
     ///After calling any run methods of the class, it writes the
     ///Gallai-Edmonds canonical decomposition of the graph. \c map
-    ///must be a node map of \ref pos_enum 's.
-    template<typename NMapEnum>
-    void writePos (NMapEnum& map) const {
-      for(NodeIt v(g); v!=INVALID; ++v)  map.set(v,position[v]);
+    ///must be a node map of \ref DecompType 's.
+    template <typename DecompositionMap>
+    void decomposition(DecompositionMap& map) const {
+      for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]);
+    }
+
+    ///\brief Returns a barrier on the nodes.
+    ///
+    ///After calling any run methods of the class, it writes a
+    ///canonical barrier on the nodes. The odd component number of the
+    ///remaining graph minus the barrier size is a lower bound for the
+    ///uncovered nodes in the graph. The \c map must be a node map of
+    ///bools.
+    template <typename BarrierMap>
+    void barrier(BarrierMap& barrier) {
+      for(NodeIt v(g); v!=INVALID; ++v) barrier.set(v,position[v] == A);    
     }
 
@@ -327,245 +422,201 @@
  
     void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
-		    UFE& blossom, UFE& tree);
+		    UFE& blossom, NV& rep, EFE& 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<Node> Q;   //queue of the totally unscanned nodes
+      Q.push(v);  
+      std::queue<Node> R;   
+      //queue of the nodes which must be scanned for a possible shrink
+      
+      while ( !Q.empty() ) {
+	Node x=Q.front();
+	Q.pop();
+	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, rep, tree, Q)) return;
+	}
+	R.push(x);
+      }
+      
+      while ( !R.empty() ) {
+	Node x=R.front();
+	R.pop();
+	
+	for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
+	  Node y=g.runningNode(e);
+
+	  if ( position[y] == D && blossom.find(x) != blossom.find(y) )  
+	    //Recall that we have only one tree.
+	    shrink( x, y, ear, blossom, rep, tree, Q);	
+	
+	  while ( !Q.empty() ) {
+	    Node z=Q.front();
+	    Q.pop();
+	    for( IncEdgeIt f(g,z); f!= INVALID; ++f ) {
+	      Node w=g.runningNode(f);
+	      //growOrAugment grows if y is covered by the matching and
+	      //augments if not. In this latter case it returns 1.
+	      if (position[w]==C && 
+		  growOrAugment(w, z, ear, blossom, rep, tree, Q)) return;
+	    }
+	    R.push(z);
+	  }
+	} //for e
+      } // while ( !R.empty() )
+    }
 
     void normShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
-		    UFE& blossom, UFE& tree);
+		    UFE& blossom, NV& rep, EFE& tree) {
+      //We have one tree, which we grow and shrink. If we augment then we
+      //return to the "for" cycle of runEdmonds().
+    
+      std::queue<Node> Q;   //queue of the unscanned nodes
+      Q.push(v);  
+      while ( !Q.empty() ) {
+
+	Node x=Q.front();
+	Q.pop();
+	
+	for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
+	  Node y=g.runningNode(e);
+	      
+	  switch ( position[y] ) {
+	  case D:          //x and y must be in the same tree
+	    if ( blossom.find(x) != blossom.find(y))
+	      //x and y are in the same tree
+	      shrink(x, y, ear, blossom, rep, tree, Q);
+	    break;
+	  case C:
+	    //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, rep, tree, Q)) return;
+	    break;
+	  default: break;
+	  }
+	}
+      }
+    }
 
     void shrink(Node x,Node y, typename Graph::template NodeMap<Node>& ear,  
-		UFE& blossom, UFE& tree,std::queue<Node>& Q);
+		UFE& blossom, NV& rep, EFE& tree,std::queue<Node>& Q) {
+      //x and y are the two adjacent vertices in two blossoms.
+   
+      typename Graph::template NodeMap<bool> path(g,false);
+    
+      Node b=rep[blossom.find(x)];
+      path.set(b,true);
+      b=_mate[b];
+      while ( b!=INVALID ) { 
+	b=rep[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=rep[blossom.find(top)];
+      Node bottom=x;
+      while ( !path[middle] )
+	shrinkStep(top, middle, bottom, ear, blossom, rep, 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=rep[blossom.find(top)];
+      bottom=y;
+      Node blossom_base=rep[blossom.find(base)];
+      while ( middle!=blossom_base )
+	shrinkStep(top, middle, bottom, ear, blossom, rep, tree, Q);
+      //Until we arrive to a node on the path, we update blossom, tree
+      //and the positions of the odd nodes.
+    
+      rep[blossom.find(base)] = base;
+    }
 
     void shrinkStep(Node& top, Node& middle, Node& bottom,
 		    typename Graph::template NodeMap<Node>& ear,  
-		    UFE& blossom, UFE& tree, std::queue<Node>& Q);
+		    UFE& blossom, NV& rep, EFE& tree, std::queue<Node>& Q) {
+      //We traverse a blossom and update everything.
+    
+      ear.set(top,bottom);
+      Node t=top;
+      while ( t!=middle ) {
+	Node u=_mate[t];
+	t=ear[u];
+	ear.set(t,u);
+      } 
+      bottom=_mate[middle];
+      position.set(bottom,D);
+      Q.push(bottom);
+      top=ear[bottom];		
+      Node oldmiddle=middle;
+      middle=rep[blossom.find(top)];
+      tree.erase(bottom);
+      tree.erase(oldmiddle);
+      blossom.insert(bottom);
+      blossom.join(bottom, oldmiddle);
+      blossom.join(top, oldmiddle);
+    }
+
+
 
     bool growOrAugment(Node& y, Node& x, typename Graph::template 
-		       NodeMap<Node>& ear, UFE& blossom, UFE& tree, 
-		       std::queue<Node>& Q);
+		       NodeMap<Node>& ear, UFE& blossom, NV& rep, EFE& tree, 
+		       std::queue<Node>& 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];
+	rep[blossom.insert(w)] = w;
+	position.set(y,A);
+	position.set(w,D);
+	int t = tree.find(rep[blossom.find(x)]);
+	tree.insert(y,t);  
+	tree.insert(w,t);  
+	Q.push(w);
+      } else {                      //augment 
+	augment(x, ear, blossom, rep, tree);
+	_mate.set(x,y);
+	_mate.set(y,x);
+	return true;
+      }
+      return false;
+    }
 
     void augment(Node x, typename Graph::template NodeMap<Node>& ear,  
-		 UFE& blossom, UFE& tree);
+		 UFE& blossom, NV& rep, EFE& tree) {
+      Node v=_mate[x];
+      while ( v!=INVALID ) {
+	
+	Node u=ear[v];
+	_mate.set(v,u);
+	Node tmp=v;
+	v=_mate[u];
+	_mate.set(u,tmp);
+      }
+      int y = tree.find(rep[blossom.find(x)]);
+      for (typename EFE::ItemIt tit(tree, y); tit != INVALID; ++tit) {   
+	if ( position[tit] == D ) {
+	  int b = blossom.find(tit);
+	  for (typename UFE::ItemIt bit(blossom, b); bit != INVALID; ++bit) { 
+	    position.set(bit, C);
+	  }
+	  blossom.eraseClass(b);
+	} else position.set(tit, C);
+      }
+      tree.eraseClass(y);
+
+    }
 
   };
-
-
-  // **********************************************************************
-  //  IMPLEMENTATIONS
-  // **********************************************************************
-
-
-  template <typename Graph>
-  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template 
-				      NodeMap<Node>& 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<Node> Q;   //queue of the totally unscanned nodes
-    Q.push(v);  
-    std::queue<Node> R;   
-    //queue of the nodes which must be scanned for a possible shrink
-      
-    while ( !Q.empty() ) {
-      Node x=Q.front();
-      Q.pop();
-      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() ) {
-      Node x=R.front();
-      R.pop();
-	
-      for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
-	Node y=g.runningNode(e);
-
-	if ( position[y] == D && blossom.find(x) != blossom.find(y) )  
-	  //Recall that we have only one tree.
-	  shrink( x, y, ear, blossom, tree, Q);	
-	
-	while ( !Q.empty() ) {
-	  Node z=Q.front();
-	  Q.pop();
-	  for( IncEdgeIt f(g,z); f!= INVALID; ++f ) {
-	    Node w=g.runningNode(f);
-	    //growOrAugment grows if y is covered by the matching and
-	    //augments if not. In this latter case it returns 1.
-	    if ( position[w]==C && growOrAugment(w, z, ear, blossom, tree, Q) )
-              return;
-	  }
-	  R.push(z);
-	}
-      } //for e
-    } // while ( !R.empty() )
-  }
-
-
-  template <typename Graph>
-  void MaxMatching<Graph>::normShrink(Node v,
-				      typename Graph::template
-				      NodeMap<Node>& 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<Node> Q;   //queue of the unscanned nodes
-    Q.push(v);  
-    while ( !Q.empty() ) {
-
-      Node x=Q.front();
-      Q.pop();
-	
-      for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
-	Node y=g.runningNode(e);
-	      
-	switch ( position[y] ) {
-	case D:          //x and y must be in the same tree
-	  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:
-	  //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 <typename Graph>
-    void MaxMatching<Graph>::shrink(Node x,Node y, typename 
-				    Graph::template NodeMap<Node>& ear,  
-				    UFE& blossom, UFE& tree, std::queue<Node>& Q) {
-    //x and y are the two adjacent vertices in two blossoms.
-   
-    typename Graph::template NodeMap<bool> 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 <typename Graph>
-  void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom,
-				      typename Graph::template
-				      NodeMap<Node>& ear,  
-				      UFE& blossom, UFE& tree,
-				      std::queue<Node>& Q) {
-    //We traverse a blossom and update everything.
-    
-    ear.set(top,bottom);
-    Node t=top;
-    while ( t!=middle ) {
-      Node u=_mate[t];
-      t=ear[u];
-      ear.set(t,u);
-    } 
-    bottom=_mate[middle];
-    position.set(bottom,D);
-    Q.push(bottom);
-    top=ear[bottom];		
-    Node oldmiddle=middle;
-    middle=blossom.find(top);
-    tree.erase(bottom);
-    tree.erase(oldmiddle);
-    blossom.insert(bottom);
-    blossom.join(bottom, oldmiddle);
-    blossom.join(top, oldmiddle);
-  }
-
-
-  template <typename Graph>
-  bool MaxMatching<Graph>::growOrAugment(Node& y, Node& x, typename Graph::template
-					 NodeMap<Node>& ear, UFE& blossom, UFE& tree,
-					 std::queue<Node>& 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 <typename Graph>
-  void MaxMatching<Graph>::augment(Node x,
-				   typename Graph::template NodeMap<Node>& ear,  
-				   UFE& blossom, UFE& tree) { 
-    Node v=_mate[x];
-    while ( v!=INVALID ) {
-	
-      Node u=ear[v];
-      _mate.set(v,u);
-      Node tmp=v;
-      v=_mate[u];
-      _mate.set(u,tmp);
-    }
-    Node y=blossom.find(x);
-    for (typename UFE::ItemIt tit(tree, y); tit != INVALID; ++tit) {   
-      if ( position[tit] == D ) {
-	for (typename UFE::ItemIt bit(blossom, tit); bit != INVALID; ++bit) {  
-	  position.set( bit ,C);
-	}
-	blossom.eraseClass(tit);
-      } else position.set( tit ,C);
-    }
-    tree.eraseClass(y);
-
-  }
-
   
 } //END OF NAMESPACE LEMON
Index: lemon/unionfind.h
===================================================================
--- lemon/unionfind.h	(revision 2427)
+++ lemon/unionfind.h	(revision 2505)
@@ -179,24 +179,54 @@
   private:
     
+    ItemIntMap& index;
+
     // If the parent stores negative value for an item then that item
-    // is root item and it has -items[it].parent component size.  Else
+    // is root item and it has ~(items[it].parent) component id.  Else
     // the items[it].parent contains the index of the parent.
     //
-    // The \c nextItem and \c prevItem provides the double-linked
-    // cyclic list of one component's items. The \c prevClass and
-    // \c nextClass gives the double linked list of the representant
-    // items. 
+    // The \c next and \c prev provides the double-linked
+    // cyclic list of one component's items.
     struct ItemT {
       int parent;
       Item item;
 
-      int nextItem, prevItem;
-      int nextClass, prevClass;
+      int next, prev;
     };
 
     std::vector<ItemT> items;
-    ItemIntMap& index;
-
-    int firstClass;
+    int firstFreeItem;
+
+    struct ClassT {
+      int size;
+      int firstItem;
+      int next, prev;
+    };
+    
+    std::vector<ClassT> classes;
+    int firstClass, firstFreeClass;
+
+    int newClass() {
+      if (firstFreeClass == -1) {
+	int cdx = classes.size();
+	classes.push_back(ClassT());
+	return cdx;
+      } else {
+	int cdx = firstFreeClass;
+	firstFreeClass = classes[firstFreeClass].next;
+	return cdx;
+      }
+    }
+
+    int newItem() {
+      if (firstFreeItem == -1) {
+	int idx = items.size();
+	items.push_back(ItemT());
+	return idx;
+      } else {
+	int idx = firstFreeItem;
+	firstFreeItem = items[firstFreeItem].next;
+	return idx;
+      }
+    }
 
 
@@ -218,28 +248,65 @@
     }
 
-    void unlaceClass(int k) {
-      if (items[k].prevClass != -1) {
-        items[items[k].prevClass].nextClass = items[k].nextClass;
+    int classIndex(int idx) const {
+      return ~(items[repIndex(idx)].parent);
+    }
+
+    void singletonItem(int idx) {
+      items[idx].next = idx;
+      items[idx].prev = idx;
+    }
+
+    void laceItem(int idx, int rdx) {
+      items[idx].prev = rdx;
+      items[idx].next = items[rdx].next;
+      items[items[rdx].next].prev = idx;
+      items[rdx].next = idx;
+    }
+
+    void unlaceItem(int idx) {
+      items[items[idx].prev].next = items[idx].next;
+      items[items[idx].next].prev = items[idx].prev;
+      
+      items[idx].next = firstFreeItem;
+      firstFreeItem = idx;
+    }
+
+    void spliceItems(int ak, int bk) {
+      items[items[ak].prev].next = bk;
+      items[items[bk].prev].next = ak;
+      int tmp = items[ak].prev;
+      items[ak].prev = items[bk].prev;
+      items[bk].prev = tmp;
+        
+    }
+
+    void laceClass(int cls) {
+      if (firstClass != -1) {
+        classes[firstClass].prev = cls;
+      }
+      classes[cls].next = firstClass;
+      classes[cls].prev = -1;
+      firstClass = cls;
+    } 
+
+    void unlaceClass(int cls) {
+      if (classes[cls].prev != -1) {
+        classes[classes[cls].prev].next = classes[cls].next;
       } else {
-        firstClass = items[k].nextClass;
-      }
-      if (items[k].nextClass != -1) {
-        items[items[k].nextClass].prevClass = items[k].prevClass;
-      }
+        firstClass = classes[cls].next;
+      }
+      if (classes[cls].next != -1) {
+        classes[classes[cls].next].prev = classes[cls].prev;
+      }
+      
+      classes[cls].next = firstFreeClass;
+      firstFreeClass = cls;
     } 
 
-    void spliceItems(int ak, int bk) {
-      items[items[ak].prevItem].nextItem = bk;
-      items[items[bk].prevItem].nextItem = ak;
-      int tmp = items[ak].prevItem;
-      items[ak].prevItem = items[bk].prevItem;
-      items[bk].prevItem = tmp;
-        
-    }
-
   public:
 
     UnionFindEnum(ItemIntMap& _index) 
-      : items(), index(_index), firstClass(-1) {}
+      : index(_index), items(), firstFreeItem(-1), 
+	firstClass(-1), firstFreeClass(-1) {}
     
     /// \brief Inserts the given element into a new component.
@@ -248,23 +315,23 @@
     /// given element.
     ///
-    void insert(const Item& item) {
-      ItemT t;
-
-      int idx = items.size();
+    int insert(const Item& item) {
+      int idx = newItem();
+
       index.set(item, idx);
 
-      t.nextItem = idx;
-      t.prevItem = idx;
-      t.item = item;
-      t.parent = -1;
-      
-      t.nextClass = firstClass;
-      if (firstClass != -1) {
-        items[firstClass].prevClass = idx;
-      }
-      t.prevClass = -1;
-      firstClass = idx;
-
-      items.push_back(t);
+      singletonItem(idx);
+      items[idx].item = item;
+
+      int cdx = newClass();
+
+      items[idx].parent = ~cdx;
+
+      laceClass(cdx);
+      classes[cdx].size = 1;
+      classes[cdx].firstItem = idx;
+
+      firstClass = cdx;
+      
+      return cdx;
     }
 
@@ -273,22 +340,16 @@
     /// This methods inserts the element \e a into the component of the
     /// element \e comp. 
-    void insert(const Item& item, const Item& comp) {
-      int k = repIndex(index[comp]);
-      ItemT t;
-
-      int idx = items.size();
+    void insert(const Item& item, int cls) {
+      int rdx = classes[cls].firstItem;
+      int idx = newItem();
+
       index.set(item, idx);
 
-      t.prevItem = k;
-      t.nextItem = items[k].nextItem;
-      items[items[k].nextItem].prevItem = idx;
-      items[k].nextItem = idx;
-
-      t.item = item;
-      t.parent = k;
-
-      --items[k].parent;
-
-      items.push_back(t);
+      laceItem(idx, rdx);
+
+      items[idx].item = item;
+      items[idx].parent = rdx;
+
+      ++classes[~(items[rdx].parent)].size;
     }
 
@@ -299,11 +360,12 @@
       items.clear();
       firstClass = -1;
-    }
-
-    /// \brief Finds the leader of the component of the given element.
-    ///
-    /// The method returns the leader of the component of the given element.
-    const Item& find(const Item &item) const {
-      return items[repIndex(index[item])].item;
+      firstFreeItem = -1;
+    }
+
+    /// \brief Finds the component of the given element.
+    ///
+    /// The method returns the component id of the given element.
+    int find(const Item &item) const {
+      return ~(items[repIndex(index[item])].parent);
     }
 
@@ -313,6 +375,6 @@
     /// Joins the component of element \e a and component of
     /// element \e b. If \e a and \e b are in the same component then
-    /// returns false else returns true.
-    bool join(const Item& a, const Item& b) {
+    /// returns -1 else returns the remaining class.
+    int join(const Item& a, const Item& b) {
 
       int ak = repIndex(index[a]);
@@ -320,81 +382,62 @@
 
       if (ak == bk) {
-	return false;
-      }
-
-      if ( items[ak].parent < items[bk].parent ) {
-        unlaceClass(bk);
-        items[ak].parent += items[bk].parent;
+	return -1;
+      }
+
+      int acx = ~(items[ak].parent);
+      int bcx = ~(items[bk].parent);
+
+      int rcx;
+
+      if (classes[acx].size > classes[bcx].size) {
+	classes[acx].size += classes[bcx].size;
 	items[bk].parent = ak;
+        unlaceClass(bcx);
+	rcx = acx;
       } else {
-        unlaceClass(ak);
-        items[bk].parent += items[ak].parent;
+	classes[bcx].size += classes[acx].size;
 	items[ak].parent = bk;
+        unlaceClass(acx);
+	rcx = bcx;
       }
       spliceItems(ak, bk);
 
-      return true;
-    }
-
-    /// \brief Returns the size of the component of element \e a.
-    ///
-    /// Returns the size of the component of element \e a.
-    int size(const Item &item) const {
-      return - items[repIndex(index[item])].parent;
-    }
-
-    /// \brief Splits up the component of the element. 
-    ///
-    /// Splitting the component of the element into sigleton
-    /// components (component of size one).
-    void split(const Item &item) {
-      int k = repIndex(index[item]);
-      int idx = items[k].nextItem;
-      while (idx != k) {
-        int next = items[idx].nextItem;
+      return rcx;
+    }
+
+    /// \brief Returns the size of the class.
+    ///
+    /// Returns the size of the class.
+    int size(int cls) const {
+      return classes[cls].size;
+    }
+
+    /// \brief Splits up the component. 
+    ///
+    /// Splitting the component into singleton components (component
+    /// of size one).
+    void split(int cls) {
+      int fdx = classes[cls].firstItem;
+      int idx = items[fdx].next;
+      while (idx != fdx) {
+        int next = items[idx].next;
+
+	singletonItem(idx);
+
+	int cdx = newClass();        
+        items[idx].parent = ~cdx;
+
+	laceClass(cdx);
+	classes[cdx].size = 1;
+	classes[cdx].firstItem = idx;
         
-        items[idx].parent = -1;
-        items[idx].prevItem = idx;
-        items[idx].nextItem = idx;
-        
-        items[idx].nextClass = firstClass;
-        items[firstClass].prevClass = idx;
-        firstClass = idx;
-
         idx = next;
       }
 
-      items[idx].parent = -1;
-      items[idx].prevItem = idx;
-      items[idx].nextItem = idx;
-      
-      items[firstClass].prevClass = -1;
-    }
-
-    /// \brief Sets the given element to the leader element of its component.
-    ///
-    /// Sets the given element to the leader element of its component.
-    void makeRep(const Item &item) {
-      int nk = index[item];
-      int k = repIndex(nk);
-      if (nk == k) return;
-      
-      if (items[k].prevClass != -1) {
-        items[items[k].prevClass].nextClass = nk;
-      } else {
-        firstClass = nk;
-      }
-      if (items[k].nextClass != -1) {
-        items[items[k].nextClass].prevClass = nk;
-      }
-      
-      int idx = items[k].nextItem;
-      while (idx != k) {
-        items[idx].parent = nk;
-        idx = items[idx].nextItem;
-      }
-      
-      items[nk].parent = items[k].parent;
-      items[k].parent = nk;
+      items[idx].prev = idx;
+      items[idx].next = idx;
+
+      classes[~(items[idx].parent)].size = 1;
+      
     }
 
@@ -406,61 +449,31 @@
     /// \warning It is an error to remove an element which is not in
     /// the structure.
-    void erase(const Item &item) {
+    /// \warning This running time of this operation is proportional to the
+    /// number of the items in this class.
+    void erase(const Item& item) {
       int idx = index[item];
-      if (rep(idx)) {
-        int k = idx;
-        if (items[k].parent == -1) {
-          unlaceClass(idx);
-          return;
-        } else {
-          int nk = items[k].nextItem;
-          if (items[k].prevClass != -1) {
-            items[items[k].prevClass].nextClass = nk;
-          } else {
-            firstClass = nk;
-          }
-          if (items[k].nextClass != -1) {
-            items[items[k].nextClass].prevClass = nk;
-          }
-      
-          int l = items[k].nextItem;
-          while (l != k) {
-            items[l].parent = nk;
-            l = items[l].nextItem;
-          }
+      int fdx = items[idx].next;
+
+      int cdx = classIndex(idx);
+      if (idx == fdx) {
+	unlaceClass(cdx);
+	items[idx].next = firstFreeItem;
+	firstFreeItem = idx;
+	return;
+      } else {
+	classes[cdx].firstItem = fdx;
+	--classes[cdx].size;
+	items[fdx].parent = ~cdx;
+
+	unlaceItem(idx);
+	idx = items[fdx].next;
+	while (idx != fdx) {
+	  items[idx].parent = fdx;
+	  idx = items[idx].next;
+	}
           
-          items[nk].parent = items[k].parent + 1;
-        }
-      } else {
-        
-        int k = repIndex(idx);
-        idx = items[k].nextItem;
-        while (idx != k) {
-          items[idx].parent = k;
-          idx = items[idx].nextItem;
-        }
-
-        ++items[k].parent;
-      }
-
-      idx = index[item];      
-      items[items[idx].prevItem].nextItem = items[idx].nextItem;
-      items[items[idx].nextItem].prevItem = items[idx].prevItem;
+      }
 
     }    
-
-    /// \brief Moves the given element to another component.
-    ///
-    /// This method moves the element \e a from its component
-    /// to the component of \e comp.
-    /// If \e a and \e comp are in the same component then
-    /// it returns false otherwise it returns true.
-    bool move(const Item &item, const Item &comp) {
-      if (repIndex(index[item]) == repIndex(index[comp])) return false;
-      erase(item);
-      insert(item, comp);
-      return true;
-    }
-
 
     /// \brief Removes the component of the given element from the structure.
@@ -470,6 +483,9 @@
     /// \warning It is an error to give an element which is not in the
     /// structure.
-    void eraseClass(const Item &item) {
-      unlaceClass(repIndex(index[item]));
+    void eraseClass(int cls) {
+      int fdx = classes[cls].firstItem;
+      unlaceClass(cls);
+      items[items[fdx].prev].next = firstFreeItem;
+      firstFreeItem = fdx;
     }
 
@@ -477,5 +493,5 @@
     ///
     /// ClassIt is a lemon style iterator for the components. It iterates
-    /// on the representant items of the classes.
+    /// on the ids of the classes.
     class ClassIt {
     public:
@@ -484,5 +500,5 @@
       /// Constructor of the iterator
       ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
-        idx = unionFind->firstClass;
+        cdx = unionFind->firstClass;
       }
 
@@ -490,5 +506,5 @@
       ///
       /// Constructor to get invalid iterator
-      ClassIt(Invalid) : unionFind(0), idx(-1) {}
+      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
       
       /// \brief Increment operator
@@ -496,5 +512,5 @@
       /// It steps to the next representant item.
       ClassIt& operator++() {
-        idx = unionFind->items[idx].nextClass;
+        cdx = unionFind->classes[cdx].next;
         return *this;
       }
@@ -503,6 +519,6 @@
       ///
       /// It converts the iterator to the current representant item.
-      operator const Item&() const {
-        return unionFind->items[idx].item;
+      operator int() const {
+        return cdx;
       }
 
@@ -511,5 +527,5 @@
       /// Equality operator
       bool operator==(const ClassIt& i) { 
-        return i.idx == idx;
+        return i.cdx == cdx;
       }
 
@@ -518,10 +534,10 @@
       /// Inequality operator
       bool operator!=(const ClassIt& i) { 
-        return i.idx != idx;
+        return i.cdx != cdx;
       }
       
     private:
       const UnionFindEnum* unionFind;
-      int idx;
+      int cdx;
     };
 
@@ -546,6 +562,6 @@
       /// Constructor of the iterator. The iterator iterates
       /// on the class of the \c item.
-      ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {
-        idx = unionFind->repIndex(unionFind->index[item]);
+      ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
+        fdx = idx = unionFind->classes[cls].firstItem;
       }
 
@@ -559,6 +575,6 @@
       /// It steps to the next item in the class.
       ItemIt& operator++() {
-        idx = unionFind->items[idx].nextItem;
-        if (unionFind->rep(idx)) idx = -1;
+        idx = unionFind->items[idx].next;
+        if (idx == fdx) idx = -1;
         return *this;
       }
@@ -587,9 +603,308 @@
     private:
       const UnionFindEnum* unionFind;
-      int idx;
+      int idx, fdx;
     };
 
   };
 
+  /// \ingroup auxdat
+  ///
+  /// \brief A \e Extend-Find data structure implementation which
+  /// is able to enumerate the components.
+  ///
+  /// The class implements an \e Extend-Find data structure which is
+  /// able to enumerate the components and the items in a
+  /// component. The data structure is a simplification of the
+  /// Union-Find structure, and it does not allow to merge two components.
+  ///
+  /// \pre You need to add all the elements by the \ref insert()
+  /// method.
+  template <typename _ItemIntMap>
+  class ExtendFindEnum {
+  public:
+    
+    typedef _ItemIntMap ItemIntMap;
+    typedef typename ItemIntMap::Key Item;
+
+  private:
+    
+    ItemIntMap& index;
+
+    struct ItemT {
+      int cls;
+      Item item;
+      int next, prev;
+    };
+
+    std::vector<ItemT> items;
+    int firstFreeItem;
+
+    struct ClassT {
+      int firstItem;
+      int next, prev;
+    };
+
+    std::vector<ClassT> classes;
+
+    int firstClass, firstFreeClass;
+
+    int newClass() {
+      if (firstFreeClass != -1) {
+	int cdx = firstFreeClass;
+	firstFreeClass = classes[cdx].next;
+	return cdx;
+      } else {
+	classes.push_back(ClassT());
+	return classes.size() - 1;
+      }
+    }
+
+    int newItem() {
+      if (firstFreeItem != -1) {
+	int idx = firstFreeItem;
+	firstFreeItem = items[idx].next;
+	return idx;
+      } else {
+	items.push_back(ItemT());
+	return items.size() - 1;
+      }
+    }
+
+  public:
+
+    /// \brief Constructor
+    ExtendFindEnum(ItemIntMap& _index) 
+      : index(_index), items(), firstFreeItem(-1), 
+	classes(), firstClass(-1), firstFreeClass(-1) {}
+    
+    /// \brief Inserts the given element into a new component.
+    ///
+    /// This method creates a new component consisting only of the
+    /// given element.
+    int insert(const Item& item) {
+      int cdx = newClass();
+      classes[cdx].prev = -1;
+      classes[cdx].next = firstClass;
+      firstClass = cdx;
+      
+      int idx = newItem();
+      items[idx].item = item;
+      items[idx].cls = cdx;
+      items[idx].prev = idx;
+      items[idx].next = idx;
+
+      classes[cdx].firstItem = idx;
+
+      index.set(item, idx);
+      
+      return cdx;
+    }
+
+    /// \brief Inserts the given element into the given component.
+    ///
+    /// This methods inserts the element \e item a into the \e cls class.
+    void insert(const Item& item, int cls) {
+      int idx = newItem();
+      int rdx = classes[cls].firstItem;
+      items[idx].item = item;
+      items[idx].cls = cls;
+
+      items[idx].prev = rdx;
+      items[idx].next = items[rdx].next;
+      items[items[rdx].next].prev = idx;
+      items[rdx].next = idx;
+
+      index.set(item, idx);
+    }
+
+    /// \brief Clears the union-find data structure
+    ///
+    /// Erase each item from the data structure.
+    void clear() {
+      items.clear();
+      classes.clear;
+      firstClass = firstFreeClass = firstFreeItem = -1;
+    }
+
+    /// \brief Gives back the class of the \e item.
+    ///
+    /// Gives back the class of the \e item.
+    int find(const Item &item) const {
+      return items[index[item]].cls;
+    }
+    
+    /// \brief Removes the given element from the structure.
+    ///
+    /// Removes the element from its component and if the component becomes
+    /// empty then removes that component from the component list.
+    ///
+    /// \warning It is an error to remove an element which is not in
+    /// the structure.
+    void erase(const Item &item) {
+      int idx = index[item];
+      int cdx = items[idx].cls;
+      
+      if (idx == items[idx].next) {
+	if (classes[cdx].prev != -1) {
+	  classes[classes[cdx].prev].next = classes[cdx].next; 
+	} else {
+	  firstClass = classes[cdx].next;
+	}
+	if (classes[cdx].next != -1) {
+	  classes[classes[cdx].next].prev = classes[cdx].prev; 
+	}
+	classes[cdx].next = firstFreeClass;
+	firstFreeClass = cdx;
+      } else {
+	classes[cdx].firstItem = items[idx].next;
+	items[items[idx].next].prev = items[idx].prev;
+	items[items[idx].prev].next = items[idx].next;
+      }
+      items[idx].next = firstFreeItem;
+      firstFreeItem = idx;
+	
+    }    
+
+    
+    /// \brief Removes the component of the given element from the structure.
+    ///
+    /// Removes the component of the given element from the structure.
+    ///
+    /// \warning It is an error to give an element which is not in the
+    /// structure.
+    void eraseClass(int cdx) {
+      int idx = classes[cdx].firstItem;
+      items[items[idx].prev].next = firstFreeItem;
+      firstFreeItem = idx;
+
+      if (classes[cdx].prev != -1) {
+	classes[classes[cdx].prev].next = classes[cdx].next; 
+      } else {
+	firstClass = classes[cdx].next;
+      }
+      if (classes[cdx].next != -1) {
+	classes[classes[cdx].next].prev = classes[cdx].prev; 
+      }
+      classes[cdx].next = firstFreeClass;
+      firstFreeClass = cdx;
+    }
+
+    /// \brief Lemon style iterator for the classes.
+    ///
+    /// ClassIt is a lemon style iterator for the components. It iterates
+    /// on the ids of classes.
+    class ClassIt {
+    public:
+      /// \brief Constructor of the iterator
+      ///
+      /// Constructor of the iterator
+      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
+        cdx = extendFind->firstClass;
+      }
+
+      /// \brief Constructor to get invalid iterator
+      ///
+      /// Constructor to get invalid iterator
+      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
+      
+      /// \brief Increment operator
+      ///
+      /// It steps to the next representant item.
+      ClassIt& operator++() {
+        cdx = extendFind->classes[cdx].next;
+        return *this;
+      }
+      
+      /// \brief Conversion operator
+      ///
+      /// It converts the iterator to the current class id.
+      operator int() const {
+        return cdx;
+      }
+
+      /// \brief Equality operator
+      ///
+      /// Equality operator
+      bool operator==(const ClassIt& i) { 
+        return i.cdx == cdx;
+      }
+
+      /// \brief Inequality operator
+      ///
+      /// Inequality operator
+      bool operator!=(const ClassIt& i) { 
+        return i.cdx != cdx;
+      }
+      
+    private:
+      const ExtendFindEnum* extendFind;
+      int cdx;
+    };
+
+    /// \brief Lemon style iterator for the items of a component.
+    ///
+    /// ClassIt is a lemon style iterator for the components. It iterates
+    /// on the items of a class. By example if you want to iterate on
+    /// each items of each classes then you may write the next code.
+    ///\code
+    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
+    ///   std::cout << "Class: ";
+    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
+    ///     std::cout << toString(iit) << ' ' << std::endl;
+    ///   }
+    ///   std::cout << std::endl;
+    /// }
+    ///\endcode
+    class ItemIt {
+    public:
+      /// \brief Constructor of the iterator
+      ///
+      /// Constructor of the iterator. The iterator iterates
+      /// on the class of the \c item.
+      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
+        fdx = idx = extendFind->classes[cls].firstItem;
+      }
+
+      /// \brief Constructor to get invalid iterator
+      ///
+      /// Constructor to get invalid iterator
+      ItemIt(Invalid) : extendFind(0), idx(-1) {}
+      
+      /// \brief Increment operator
+      ///
+      /// It steps to the next item in the class.
+      ItemIt& operator++() {
+        idx = extendFind->items[idx].next;
+	if (fdx == idx) idx = -1;
+        return *this;
+      }
+      
+      /// \brief Conversion operator
+      ///
+      /// It converts the iterator to the current item.
+      operator const Item&() const {
+        return extendFind->items[idx].item;
+      }
+
+      /// \brief Equality operator
+      ///
+      /// Equality operator
+      bool operator==(const ItemIt& i) { 
+        return i.idx == idx;
+      }
+
+      /// \brief Inequality operator
+      ///
+      /// Inequality operator
+      bool operator!=(const ItemIt& i) { 
+        return i.idx != idx;
+      }
+      
+    private:
+      const ExtendFindEnum* extendFind;
+      int idx, fdx;
+    };
+
+  };
 
   //! @}
Index: test/max_matching_test.cc
===================================================================
--- test/max_matching_test.cc	(revision 2391)
+++ test/max_matching_test.cc	(revision 2505)
@@ -67,9 +67,10 @@
   
   MaxMatching<Graph> max_matching(g);
-  max_matching.runEdmonds(0);
+  max_matching.init();
+  max_matching.startDense();
   
   int s=0;
   Graph::NodeMap<Node> mate(g,INVALID);
-  max_matching.writeNMapNode(mate);
+  max_matching.mateMap(mate);
   for(NodeIt v(g); v!=INVALID; ++v) {
     if ( mate[v]!=INVALID ) ++s;
@@ -83,11 +84,11 @@
   check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
 
-  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g);
-  max_matching.writePos(pos0);
+  Graph::NodeMap<MaxMatching<Graph>::DecompType> pos0(g);
+  max_matching.decomposition(pos0);
   
-  max_matching.resetMatching();
-  max_matching.runEdmonds(1);
+  max_matching.init();
+  max_matching.startSparse();
   s=0;
-  max_matching.writeNMapNode(mate);
+  max_matching.mateMap(mate);
   for(NodeIt v(g); v!=INVALID; ++v) {
     if ( mate[v]!=INVALID ) ++s;
@@ -95,10 +96,10 @@
   check ( int(s/2) == size, "The size does not equal!" );
 
-  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
-  max_matching.writePos(pos1);
+  Graph::NodeMap<MaxMatching<Graph>::DecompType> pos1(g);
+  max_matching.decomposition(pos1);
 
   max_matching.run();
   s=0;
-  max_matching.writeNMapNode(mate);
+  max_matching.mateMap(mate);
   for(NodeIt v(g); v!=INVALID; ++v) {
     if ( mate[v]!=INVALID ) ++s;
@@ -106,11 +107,10 @@
   check ( int(s/2) == size, "The size does not equal!" ); 
   
-  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
-  max_matching.writePos(pos2);
+  Graph::NodeMap<MaxMatching<Graph>::DecompType> pos2(g);
+  max_matching.decomposition(pos2);
 
-  max_matching.resetMatching();
   max_matching.run();
   s=0;
-  max_matching.writeNMapNode(mate);
+  max_matching.mateMap(mate);
   for(NodeIt v(g); v!=INVALID; ++v) {
     if ( mate[v]!=INVALID ) ++s;
@@ -118,6 +118,6 @@
   check ( int(s/2) == size, "The size does not equal!" ); 
   
-  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
-  max_matching.writePos(pos);
+  Graph::NodeMap<MaxMatching<Graph>::DecompType> pos(g);
+  max_matching.decomposition(pos);
    
   bool ismatching=true;
@@ -140,6 +140,8 @@
   bool noedge=true;
   for(UEdgeIt e(g); e!=INVALID; ++e) {
-   if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) || 
-	 (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) )
+   if ( (pos[g.target(e)]==max_matching.C && 
+	 pos[g.source(e)]==max_matching.D) || 
+	 (pos[g.target(e)]==max_matching.D && 
+	  pos[g.source(e)]==max_matching.C) )
       noedge=false; 
   }
Index: test/unionfind_test.cc
===================================================================
--- test/unionfind_test.cc	(revision 2391)
+++ test/unionfind_test.cc	(revision 2505)
@@ -50,5 +50,5 @@
   U.insert(2);
 
-  check(U.join(1,2),"Test failed.");
+  check(U.join(1,2) != -1,"Test failed.");
 
   U.insert(3);
@@ -58,65 +58,57 @@
   U.insert(7);
 
-  check(U.join(1,4),"Test failed.");
-  check(!U.join(2,4),"Test failed.");
-  check(U.join(3,5),"Test failed.");
 
-  U.insert(8,5);
+  check(U.join(1,4) != -1,"Test failed.");
+  check(U.join(2,4) == -1,"Test failed.");
+  check(U.join(3,5) != -1,"Test failed.");
 
-  check(U.size(4) == 3,"Test failed.");
-  check(U.size(5) == 3,"Test failed.");
-  check(U.size(6) == 1,"Test failed.");
-  check(U.size(2) == 3,"Test failed.");
+
+  U.insert(8,U.find(5));
+
+
+  check(U.size(U.find(4)) == 3,"Test failed.");
+  check(U.size(U.find(5)) == 3,"Test failed.");
+  check(U.size(U.find(6)) == 1,"Test failed.");
+  check(U.size(U.find(2)) == 3,"Test failed.");
+
 
   U.insert(9);
-  U.insert(10,9);
+  U.insert(10,U.find(9));
 
-  check(U.join(8,10),"Test failed.");
 
-  check(U.move(9,4),"Test failed.");
-  check(!U.move(9,2),"Test failed.");
+  check(U.join(8,10) != -1,"Test failed.");
 
-  check(U.size(4) == 4,"Test failed.");
-  check(U.size(9) == 4,"Test failed.");
 
-  check(U.move(5,6),"Test failed.");
+  check(U.size(U.find(4)) == 3,"Test failed.");
+  check(U.size(U.find(9)) == 5,"Test failed.");
 
-  check(U.size(5) == 2,"Test failed.");
-  check(U.size(8) == 3,"Test failed.");
-
-  check(U.move(7,10),"Test failed.");
-  check(U.size(7) == 4,"Test failed.");
+  check(U.size(U.find(8)) == 5,"Test failed.");
 
   U.erase(9);
   U.erase(1);
 
-  check(U.size(4) == 2,"Test failed.");
-  check(U.size(2) == 2,"Test failed.");
+  check(U.size(U.find(10)) == 4,"Test failed.");
+  check(U.size(U.find(2)) == 2,"Test failed.");
 
   U.erase(6);
-  U.split(8);
-
-  check(U.size(4) == 2,"Test failed.");
-  check(U.size(3) == 1,"Test failed.");
-  check(U.size(2) == 2,"Test failed.");
-
-  check(U.join(3,4),"Test failed.");
-  check(!U.join(2,4),"Test failed.");
-
-  check(U.size(4) == 3,"Test failed.");
-  check(U.size(3) == 3,"Test failed.");
-  check(U.size(2) == 3,"Test failed.");
-
-  U.makeRep(4);
-  U.makeRep(3);
-  U.makeRep(2);
-
-  check(U.size(4) == 3,"Test failed.");
-  check(U.size(3) == 3,"Test failed.");
-  check(U.size(2) == 3,"Test failed.");
+  U.split(U.find(8));
 
 
-  U.eraseClass(4);
-  U.eraseClass(7);
+  check(U.size(U.find(4)) == 2,"Test failed.");
+  check(U.size(U.find(3)) == 1,"Test failed.");
+  check(U.size(U.find(2)) == 2,"Test failed.");
 
+
+  check(U.join(3,4) != -1,"Test failed.");
+  check(U.join(2,4) == -1,"Test failed.");
+
+
+  check(U.size(U.find(4)) == 3,"Test failed.");
+  check(U.size(U.find(3)) == 3,"Test failed.");
+  check(U.size(U.find(2)) == 3,"Test failed.");
+
+  U.eraseClass(U.find(4));
+  U.eraseClass(U.find(7));
+
+  return 0;
 }
