Changeset 2505:1bb471764ab8 in lemon-0.x

Timestamp:

10/30/07 21:21:10 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3351

Message:

Redesign interface of MaxMatching? and UnionFindEnum?
New class ExtendFindEnum?

Faster MaxMatching?

Files:

• lemon/max_matching.h (modified) (9 diffs)
• lemon/unionfind.h (modified) (19 diffs)
• test/max_matching_test.cc (modified) (6 diffs)
• test/unionfind_test.cc (modified) (2 diffs)

lemon/max_matching.h

@@ -31 +31 @@
 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 +64 @@
     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 +89 @@
     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 +128 @@
     }
 
-    ///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 +288 @@
 
 
-    ///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 +347 @@
     ///== 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 +367 @@
 
 
-    ///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 +395 @@
 
 
-    ///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 +422 @@
  
     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

lemon/unionfind.h

@@ -179 +179 @@
   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 +248 @@
     }
 
-    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 +315 @@
     /// 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 +340 @@
     /// 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 +360 @@
       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 +375 @@
     /// 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 +382 @@
 
       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 +449 @@
     /// \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 +483 @@
     /// \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 +493 @@
     ///
     /// 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 +500 @@
       /// Constructor of the iterator
       ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
-        idx = unionFind->firstClass;
+        cdx = unionFind->firstClass;
       }
 
@@ -490 +506 @@
       ///
       /// Constructor to get invalid iterator
-      ClassIt(Invalid) : unionFind(0), idx(-1) {}
+      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
       
       /// \brief Increment operator
@@ -496 +512 @@
       /// It steps to the next representant item.
       ClassIt& operator++() {
-        idx = unionFind->items[idx].nextClass;
+        cdx = unionFind->classes[cdx].next;
         return *this;
       }
@@ -503 +519 @@
       ///
       /// It converts the iterator to the current representant item.
-      operator const Item&() const {
-        return unionFind->items[idx].item;
+      operator int() const {
+        return cdx;
       }
 
@@ -511 +527 @@
       /// Equality operator
       bool operator==(const ClassIt& i) { 
-        return i.idx == idx;
+        return i.cdx == cdx;
       }
 
@@ -518 +534 @@
       /// Inequality operator
       bool operator!=(const ClassIt& i) { 
-        return i.idx != idx;
+        return i.cdx != cdx;
       }
       
     private:
       const UnionFindEnum* unionFind;
-      int idx;
+      int cdx;
     };
 
@@ -546 +562 @@
       /// 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 +575 @@
       /// 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 +603 @@
     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;
+    };
+
+  };
 
   //! @}

test/max_matching_test.cc

@@ -67 +67 @@
   
   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 +84 @@
   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 +96 @@
   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 +107 @@
   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 +118 @@
   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 +140 @@
   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; 
   }

test/unionfind_test.cc

@@ -50 +50 @@
   U.insert(2);
 
-  check(U.join(1,2),"Test failed.");
+  check(U.join(1,2) != -1,"Test failed.");
 
   U.insert(3);
@@ -58 +58 @@
   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;
 }