# HG changeset patch # User deba # Date 1193775670 0 # Node ID 1bb471764ab87a262de179cefe708ebb27aa2bf9 # Parent 46a82ce84cc6bbe2432ce3ecc0996b2f1851a33a Redesign interface of MaxMatching and UnionFindEnum New class ExtendFindEnum Faster MaxMatching diff -r 46a82ce84cc6 -r 1bb471764ab8 lemon/max_matching.h --- a/lemon/max_matching.h Tue Oct 30 10:51:07 2007 +0000 +++ b/lemon/max_matching.h Tue Oct 30 20:21:10 2007 +0000 @@ -30,25 +30,21 @@ namespace lemon { - /// \ingroup matching + ///\ingroup matching - ///Edmonds' alternating forest maximum matching algorithm. - + ///\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. /// @@ -67,17 +63,21 @@ typedef typename Graph::template NodeMap UFECrossRef; typedef UnionFindEnum UFE; + typedef std::vector NV; + + typedef typename Graph::template NodeMap EFECrossRef; + typedef ExtendFindEnum 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, C=2 @@ -88,71 +88,32 @@ static const int HEUR_density=2; const Graph& g; typename Graph::template NodeMap _mate; - typename Graph::template NodeMap position; + typename Graph::template NodeMap position; public: - MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {} + MaxMatching(const Graph& _g) + : g(_g), _mate(_g), 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 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. + ///\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) { - 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 ); - } + _mate.set(v,INVALID); + position.set(v,C); } } - - ///Finds a greedy matching starting from the actual matching. - - ///Starting form the actual matching stored, it finds a maximal - ///greedy matching. - void greedyMatching() { + ///\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 ) { for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { @@ -166,8 +127,153 @@ } } - ///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 + 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 + 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 + 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 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 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. int size() const { @@ -181,75 +287,70 @@ } - ///Resets the actual matching to the empty matching. - - ///Resets the actual matching to the empty matching. + ///\brief Returns the mate of a node in the actual matching. /// - void resetMatching() { - for(NodeIt v(g); v!=INVALID; ++v) - _mate.set(v,INVALID); - } - - ///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. + ///\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; + } - ///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 - void readNMapNode(NMapN& map) { - for(NodeIt v(g); v!=INVALID; ++v) { - _mate.set(v,map[v]); - } - } + /// \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; + } - ///Writes the stored matching to a \c Node valued \c Node map. - + ///\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 - void writeNMapNode (NMapN& map) const { + template + 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 - 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 ///map will have the property that if \c g.oppositeNode(u,map[u]) ///== v then \c map[u]==map[v] holds, and now this edge is an edge ///of the matching. - template - void writeNMapEdge (NMapE& map) const { + template + void matchingMap(MatchingMap& map) const { typename Graph::template NodeMap 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) { if ( g.runningNode(e) == u ) { @@ -265,33 +366,15 @@ } - ///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 - 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 - void writeEMapBool (EMapB& map) const { + template + void matching(MatchingMap& map) const { for(UEdgeIt e(g); e!=INVALID; ++e) map.set(e,false); typename Graph::template NodeMap todo(g,true); @@ -311,262 +394,230 @@ } - ///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 - 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 + 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 + void barrier(BarrierMap& barrier) { + for(NodeIt v(g); v!=INVALID; ++v) barrier.set(v,position[v] == A); } private: void lateShrink(Node v, typename Graph::template NodeMap& 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 Q; //queue of the totally unscanned nodes + Q.push(v); + std::queue 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& 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 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& ear, - UFE& blossom, UFE& tree,std::queue& Q); + UFE& blossom, NV& rep, EFE& tree,std::queue& Q) { + //x and y are the two adjacent vertices in two blossoms. + + typename Graph::template NodeMap 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& ear, - UFE& blossom, UFE& tree, std::queue& Q); + UFE& blossom, NV& rep, EFE& tree, std::queue& 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& ear, UFE& blossom, UFE& tree, - std::queue& Q); + NodeMap& ear, UFE& blossom, NV& rep, EFE& tree, + std::queue& 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& 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 - void MaxMatching::lateShrink(Node v, typename Graph::template - NodeMap& 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 Q; //queue of the totally unscanned nodes - Q.push(v); - std::queue 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 - void MaxMatching::normShrink(Node v, - typename Graph::template - NodeMap& 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 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 - void MaxMatching::shrink(Node x,Node y, typename - Graph::template NodeMap& ear, - UFE& blossom, UFE& tree, std::queue& Q) { - //x and y are the two adjacent vertices in two blossoms. - - typename Graph::template NodeMap 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 - void MaxMatching::shrinkStep(Node& top, Node& middle, Node& bottom, - typename Graph::template - NodeMap& ear, - UFE& blossom, UFE& tree, - std::queue& 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 - bool MaxMatching::growOrAugment(Node& y, Node& x, typename Graph::template - NodeMap& ear, UFE& blossom, UFE& tree, - std::queue& 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 - void MaxMatching::augment(Node x, - typename Graph::template NodeMap& 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 diff -r 46a82ce84cc6 -r 1bb471764ab8 lemon/unionfind.h --- a/lemon/unionfind.h Tue Oct 30 10:51:07 2007 +0000 +++ b/lemon/unionfind.h Tue Oct 30 20:21:10 2007 +0000 @@ -178,26 +178,56 @@ 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 items; - ItemIntMap& index; + int firstFreeItem; - int firstClass; + struct ClassT { + int size; + int firstItem; + int next, prev; + }; + + std::vector 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; + } + } bool rep(int idx) const { @@ -217,79 +247,110 @@ return k; } - void unlaceClass(int k) { - if (items[k].prevClass != -1) { - items[items[k].prevClass].nextClass = items[k].nextClass; - } else { - firstClass = 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; } - if (items[k].nextClass != -1) { - items[items[k].nextClass].prevClass = items[k].prevClass; - } + classes[cls].next = firstClass; + classes[cls].prev = -1; + firstClass = 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; - - } + void unlaceClass(int cls) { + if (classes[cls].prev != -1) { + classes[classes[cls].prev].next = classes[cls].next; + } else { + firstClass = classes[cls].next; + } + if (classes[cls].next != -1) { + classes[classes[cls].next].prev = classes[cls].prev; + } + + classes[cls].next = firstFreeClass; + firstFreeClass = cls; + } 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. /// /// This method creates a new component consisting only of the /// given element. /// - void insert(const Item& item) { - ItemT t; + int insert(const Item& item) { + int idx = newItem(); - int idx = items.size(); index.set(item, idx); - t.nextItem = idx; - t.prevItem = idx; - t.item = item; - t.parent = -1; + 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; - t.nextClass = firstClass; - if (firstClass != -1) { - items[firstClass].prevClass = idx; - } - t.prevClass = -1; - firstClass = idx; - - items.push_back(t); + return cdx; } /// \brief Inserts the given element into the component of the others. /// /// 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; + void insert(const Item& item, int cls) { + int rdx = classes[cls].firstItem; + int idx = newItem(); - int idx = items.size(); index.set(item, idx); - t.prevItem = k; - t.nextItem = items[k].nextItem; - items[items[k].nextItem].prevItem = idx; - items[k].nextItem = idx; + laceItem(idx, rdx); - t.item = item; - t.parent = k; + items[idx].item = item; + items[idx].parent = rdx; - --items[k].parent; - - items.push_back(t); + ++classes[~(items[rdx].parent)].size; } /// \brief Clears the union-find data structure @@ -298,13 +359,14 @@ void clear() { items.clear(); firstClass = -1; + firstFreeItem = -1; } - /// \brief Finds the leader of the component of the given element. + /// \brief Finds 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; + /// The method returns the component id of the given element. + int find(const Item &item) const { + return ~(items[repIndex(index[item])].parent); } /// \brief Joining the component of element \e a and element \e b. @@ -312,90 +374,71 @@ /// This is the \e union operation of the Union-Find structure. /// 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]); int bk = repIndex(index[b]); if (ak == bk) { - return false; + return -1; } - if ( items[ak].parent < items[bk].parent ) { - unlaceClass(bk); - items[ak].parent += items[bk].parent; + 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; + return rcx; } - /// \brief Returns the size of the component of element \e a. + /// \brief Returns the size of the class. /// - /// Returns the size of the component of element \e a. - int size(const Item &item) const { - return - items[repIndex(index[item])].parent; + /// Returns the size of the class. + int size(int cls) const { + return classes[cls].size; } - /// \brief Splits up the component of the element. + /// \brief Splits up the component. /// - /// 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; + /// 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[idx].prev = idx; + items[idx].next = idx; + + classes[~(items[idx].parent)].size = 1; - 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; } /// \brief Removes the given element from the structure. @@ -405,124 +448,97 @@ /// /// \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. /// /// 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(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; } /// \brief Lemon style iterator for the representant items. /// /// 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: /// \brief Constructor of the iterator /// /// Constructor of the iterator ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) { - idx = unionFind->firstClass; + cdx = unionFind->firstClass; } /// \brief Constructor to get invalid iterator /// /// Constructor to get invalid iterator - ClassIt(Invalid) : unionFind(0), idx(-1) {} + ClassIt(Invalid) : unionFind(0), cdx(-1) {} /// \brief Increment operator /// /// It steps to the next representant item. ClassIt& operator++() { - idx = unionFind->items[idx].nextClass; + cdx = unionFind->classes[cdx].next; return *this; } /// \brief Conversion operator /// /// It converts the iterator to the current representant item. - operator const Item&() const { - return unionFind->items[idx].item; + operator int() const { + return cdx; } /// \brief Equality operator /// /// Equality operator bool operator==(const ClassIt& i) { - return i.idx == idx; + return i.cdx == cdx; } /// \brief Inequality operator /// /// Inequality operator bool operator!=(const ClassIt& i) { - return i.idx != idx; + return i.cdx != cdx; } private: const UnionFindEnum* unionFind; - int idx; + int cdx; }; /// \brief Lemon style iterator for the items of a component. @@ -545,8 +561,8 @@ /// /// 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; } /// \brief Constructor to get invalid iterator @@ -558,8 +574,8 @@ /// /// 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; } @@ -586,11 +602,310 @@ 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 + 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 items; + int firstFreeItem; + + struct ClassT { + int firstItem; + int next, prev; + }; + + std::vector 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; + }; + + }; //! @} diff -r 46a82ce84cc6 -r 1bb471764ab8 test/max_matching_test.cc --- a/test/max_matching_test.cc Tue Oct 30 10:51:07 2007 +0000 +++ b/test/max_matching_test.cc Tue Oct 30 20:21:10 2007 +0000 @@ -66,11 +66,12 @@ g.addEdge(nodes[6], nodes[12]); MaxMatching max_matching(g); - max_matching.runEdmonds(0); + max_matching.init(); + max_matching.startDense(); int s=0; Graph::NodeMap mate(g,INVALID); - max_matching.writeNMapNode(mate); + max_matching.mateMap(mate); for(NodeIt v(g); v!=INVALID; ++v) { if ( mate[v]!=INVALID ) ++s; } @@ -82,43 +83,42 @@ check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" ); - Graph::NodeMap::pos_enum> pos0(g); - max_matching.writePos(pos0); + Graph::NodeMap::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; } check ( int(s/2) == size, "The size does not equal!" ); - Graph::NodeMap::pos_enum> pos1(g); - max_matching.writePos(pos1); + Graph::NodeMap::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; } check ( int(s/2) == size, "The size does not equal!" ); - Graph::NodeMap::pos_enum> pos2(g); - max_matching.writePos(pos2); + Graph::NodeMap::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; } check ( int(s/2) == size, "The size does not equal!" ); - Graph::NodeMap::pos_enum> pos(g); - max_matching.writePos(pos); + Graph::NodeMap::DecompType> pos(g); + max_matching.decomposition(pos); bool ismatching=true; for(NodeIt v(g); v!=INVALID; ++v) { @@ -139,8 +139,10 @@ 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; } check ( noedge, "There are edges between D and C!" ); diff -r 46a82ce84cc6 -r 1bb471764ab8 test/unionfind_test.cc --- a/test/unionfind_test.cc Tue Oct 30 10:51:07 2007 +0000 +++ b/test/unionfind_test.cc Tue Oct 30 20:21:10 2007 +0000 @@ -49,7 +49,7 @@ U.insert(1); U.insert(2); - check(U.join(1,2),"Test failed."); + check(U.join(1,2) != -1,"Test failed."); U.insert(3); U.insert(4); @@ -57,66 +57,58 @@ U.insert(6); 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); + U.split(U.find(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(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.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.join(3,4) != -1,"Test failed."); + check(U.join(2,4) == -1,"Test failed."); - check(U.size(4) == 3,"Test failed."); - check(U.size(3) == 3,"Test failed."); - check(U.size(2) == 3,"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(4); - U.eraseClass(7); + U.eraseClass(U.find(4)); + U.eraseClass(U.find(7)); + return 0; }