jacint@1077: /* -*- C++ -*- jacint@1077: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). jacint@1077: * jacint@1077: * Permission to use, modify and distribute this software is granted jacint@1077: * provided that this copyright notice appears in all copies. For jacint@1077: * precise terms see the accompanying LICENSE file. jacint@1077: * jacint@1077: * This software is provided "AS IS" with no warranty of any kind, jacint@1077: * express or implied, and with no claim as to its suitability for any jacint@1077: * purpose. jacint@1077: * jacint@1077: */ jacint@1077: jacint@1077: #ifndef LEMON_MAX_MATCHING_H jacint@1077: #define LEMON_MAX_MATCHING_H jacint@1077: jacint@1077: #include deba@1993: #include jacint@1093: #include jacint@1077: #include jacint@1077: deba@2042: ///\ingroup matching jacint@1077: ///\file deba@2042: ///\brief Maximum matching algorithm in undirected graph. jacint@1077: jacint@1077: namespace lemon { jacint@1077: deba@2042: /// \ingroup matching jacint@1077: jacint@1077: ///Edmonds' alternating forest maximum matching algorithm. jacint@1077: jacint@1077: ///This class provides Edmonds' alternating forest matching jacint@1077: ///algorithm. The starting matching (if any) can be passed to the jacint@1077: ///algorithm using read-in functions \ref readNMapNode, \ref jacint@1077: ///readNMapEdge or \ref readEMapBool depending on the container. The jacint@1077: ///resulting maximum matching can be attained by write-out functions jacint@1077: ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool jacint@1077: ///depending on the preferred container. jacint@1077: /// jacint@1077: ///The dual side of a matching is a map of the nodes to jacint@1077: ///MaxMatching::pos_enum, having values D, A and C showing the jacint@1077: ///Gallai-Edmonds decomposition of the graph. The nodes in D induce jacint@1077: ///a graph with factor-critical components, the nodes in A form the jacint@1077: ///barrier, and the nodes in C induce a graph having a perfect jacint@1077: ///matching. This decomposition can be attained by calling \ref jacint@1090: ///writePos after running the algorithm. jacint@1077: /// jacint@1077: ///\param Graph The undirected graph type the algorithm runs on. jacint@1077: /// jacint@1077: ///\author Jacint Szabo jacint@1077: template jacint@1077: class MaxMatching { jacint@1165: jacint@1165: protected: jacint@1165: jacint@1077: typedef typename Graph::Node Node; jacint@1077: typedef typename Graph::Edge Edge; klao@1909: typedef typename Graph::UEdge UEdge; klao@1909: typedef typename Graph::UEdgeIt UEdgeIt; jacint@1077: typedef typename Graph::NodeIt NodeIt; jacint@1077: typedef typename Graph::IncEdgeIt IncEdgeIt; jacint@1077: deba@2205: typedef typename Graph::template NodeMap UFECrossRef; deba@2308: typedef UnionFindEnum UFE; jacint@1077: jacint@1077: public: jacint@1077: jacint@1077: ///Indicates the Gallai-Edmonds decomposition of the graph. jacint@1077: jacint@1077: ///Indicates the Gallai-Edmonds decomposition of the graph, which jacint@1077: ///shows an upper bound on the size of a maximum matching. The jacint@1077: ///nodes with pos_enum \c D induce a graph with factor-critical jacint@1077: ///components, the nodes in \c A form the canonical barrier, and the jacint@1077: ///nodes in \c C induce a graph having a perfect matching. jacint@1077: enum pos_enum { jacint@1077: D=0, jacint@1077: A=1, jacint@1077: C=2 jacint@1077: }; jacint@1077: jacint@1165: protected: jacint@1077: jacint@1077: static const int HEUR_density=2; jacint@1077: const Graph& g; jacint@1093: typename Graph::template NodeMap _mate; jacint@1077: typename Graph::template NodeMap position; jacint@1077: jacint@1077: public: jacint@1077: jacint@1093: MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {} jacint@1077: jacint@1077: ///Runs Edmonds' algorithm. jacint@1077: jacint@1077: ///Runs Edmonds' algorithm for sparse graphs (number of edges < jacint@1077: ///2*number of nodes), and a heuristical Edmonds' algorithm with a jacint@1090: ///heuristic of postponing shrinks for dense graphs. alpar@1587: void run() { klao@1909: if ( countUEdges(g) < HEUR_density*countNodes(g) ) { alpar@1587: greedyMatching(); alpar@1587: runEdmonds(0); alpar@1587: } else runEdmonds(1); alpar@1587: } alpar@1587: jacint@1077: jacint@1077: ///Runs Edmonds' algorithm. jacint@1077: jacint@1077: ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs jacint@1077: ///Edmonds' algorithm with a heuristic of postponing shrinks, jacint@1090: ///giving a faster algorithm for dense graphs. alpar@1587: void runEdmonds( int heur = 1 ) { alpar@1587: jacint@2023: //each vertex is put to C alpar@1587: for(NodeIt v(g); v!=INVALID; ++v) alpar@1587: position.set(v,C); alpar@1587: alpar@1587: typename Graph::template NodeMap ear(g,INVALID); alpar@1587: //undefined for the base nodes of the blossoms (i.e. for the alpar@1587: //representative elements of UFE blossom) and for the nodes in C alpar@1587: deba@2205: UFECrossRef blossom_base(g); alpar@1587: UFE blossom(blossom_base); deba@2205: deba@2205: UFECrossRef tree_base(g); alpar@1587: UFE tree(tree_base); deba@2205: alpar@1587: //If these UFE's would be members of the class then also alpar@1587: //blossom_base and tree_base should be a member. alpar@1587: jacint@2023: //We build only one tree and the other vertices uncovered by the jacint@2023: //matching belong to C. (They can be considered as singleton jacint@2023: //trees.) If this tree can be augmented or no more jacint@2023: //grow/augmentation/shrink is possible then we return to this jacint@2023: //"for" cycle. alpar@1587: for(NodeIt v(g); v!=INVALID; ++v) { alpar@1587: if ( position[v]==C && _mate[v]==INVALID ) { alpar@1587: blossom.insert(v); alpar@1587: tree.insert(v); alpar@1587: position.set(v,D); alpar@1587: if ( heur == 1 ) lateShrink( v, ear, blossom, tree ); alpar@1587: else normShrink( v, ear, blossom, tree ); alpar@1587: } alpar@1587: } alpar@1587: } alpar@1587: jacint@1077: jacint@1077: ///Finds a greedy matching starting from the actual matching. jacint@1077: jacint@1077: ///Starting form the actual matching stored, it finds a maximal jacint@1077: ///greedy matching. alpar@1587: void greedyMatching() { alpar@1587: for(NodeIt v(g); v!=INVALID; ++v) alpar@1587: if ( _mate[v]==INVALID ) { alpar@1587: for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { alpar@1587: Node y=g.runningNode(e); alpar@1587: if ( _mate[y]==INVALID && y!=v ) { alpar@1587: _mate.set(v,y); alpar@1587: _mate.set(y,v); alpar@1587: break; alpar@1587: } alpar@1587: } alpar@1587: } alpar@1587: } jacint@1077: jacint@1077: ///Returns the size of the actual matching stored. jacint@1077: jacint@1077: ///Returns the size of the actual matching stored. After \ref jacint@1077: ///run() it returns the size of a maximum matching in the graph. alpar@1587: int size() const { alpar@1587: int s=0; alpar@1587: for(NodeIt v(g); v!=INVALID; ++v) { alpar@1587: if ( _mate[v]!=INVALID ) { alpar@1587: ++s; alpar@1587: } alpar@1587: } alpar@1587: return s/2; alpar@1587: } alpar@1587: jacint@1077: jacint@1077: ///Resets the actual matching to the empty matching. jacint@1077: jacint@1077: ///Resets the actual matching to the empty matching. jacint@1077: /// alpar@1587: void resetMatching() { alpar@1587: for(NodeIt v(g); v!=INVALID; ++v) alpar@1587: _mate.set(v,INVALID); alpar@1587: } jacint@1077: jacint@1093: ///Returns the mate of a node in the actual matching. jacint@1093: jacint@1093: ///Returns the mate of a \c node in the actual matching. jacint@1093: ///Returns INVALID if the \c node is not covered by the actual matching. jacint@1093: Node mate(Node& node) const { jacint@1093: return _mate[node]; jacint@1093: } jacint@1093: jacint@1165: ///Reads a matching from a \c Node valued \c Node map. jacint@1077: jacint@1165: ///Reads a matching from a \c Node valued \c Node map. This map jacint@1165: ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u jacint@1165: ///must hold, and \c uv will be an edge of the matching. jacint@1077: template jacint@1077: void readNMapNode(NMapN& map) { jacint@1077: for(NodeIt v(g); v!=INVALID; ++v) { jacint@1093: _mate.set(v,map[v]); jacint@1077: } jacint@1077: } jacint@1077: jacint@1165: ///Writes the stored matching to a \c Node valued \c Node map. jacint@1077: jacint@1165: ///Writes the stored matching to a \c Node valued \c Node map. The jacint@1077: ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c jacint@1077: ///map[v]==u will hold, and now \c uv is an edge of the matching. jacint@1077: template jacint@1077: void writeNMapNode (NMapN& map) const { jacint@1077: for(NodeIt v(g); v!=INVALID; ++v) { jacint@1093: map.set(v,_mate[v]); jacint@1077: } jacint@1077: } jacint@1077: klao@1909: ///Reads a matching from an \c UEdge valued \c Node map. jacint@1077: klao@1909: ///Reads a matching from an \c UEdge valued \c Node map. \c klao@1909: ///map[v] must be an \c UEdge incident to \c v. This map must jacint@1165: ///have the property that if \c g.oppositeNode(u,map[u])==v then jacint@1165: ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge marci@1172: ///joining \c u to \c v will be an edge of the matching. jacint@1077: template jacint@1077: void readNMapEdge(NMapE& map) { jacint@2023: for(NodeIt v(g); v!=INVALID; ++v) { jacint@2023: UEdge e=map[v]; jacint@1165: if ( e!=INVALID ) jacint@1166: _mate.set(v,g.oppositeNode(v,e)); jacint@1077: } jacint@1077: } jacint@1077: klao@1909: ///Writes the matching stored to an \c UEdge valued \c Node map. jacint@1077: klao@1909: ///Writes the stored matching to an \c UEdge valued \c Node klao@1909: ///map. \c map[v] will be an \c UEdge incident to \c v. This jacint@1165: ///map will have the property that if \c g.oppositeNode(u,map[u]) jacint@1165: ///== v then \c map[u]==map[v] holds, and now this edge is an edge jacint@1165: ///of the matching. jacint@1077: template jacint@1077: void writeNMapEdge (NMapE& map) const { jacint@1077: typename Graph::template NodeMap todo(g,true); jacint@1077: for(NodeIt v(g); v!=INVALID; ++v) { jacint@1093: if ( todo[v] && _mate[v]!=INVALID ) { jacint@1093: Node u=_mate[v]; jacint@1077: for(IncEdgeIt e(g,v); e!=INVALID; ++e) { klao@1158: if ( g.runningNode(e) == u ) { jacint@1077: map.set(u,e); jacint@1077: map.set(v,e); jacint@1077: todo.set(u,false); jacint@1077: todo.set(v,false); jacint@1077: break; jacint@1077: } jacint@1077: } jacint@1077: } jacint@1077: } jacint@1077: } jacint@1077: jacint@1077: jacint@1165: ///Reads a matching from a \c bool valued \c Edge map. jacint@1077: jacint@1165: ///Reads a matching from a \c bool valued \c Edge map. This map jacint@1165: ///must have the property that there are no two incident edges \c jacint@1165: ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c jacint@1077: ///map[e]==true form the matching. jacint@1077: template jacint@1077: void readEMapBool(EMapB& map) { klao@1909: for(UEdgeIt e(g); e!=INVALID; ++e) { jacint@1077: if ( map[e] ) { jacint@1077: Node u=g.source(e); jacint@1077: Node v=g.target(e); jacint@1093: _mate.set(u,v); jacint@1093: _mate.set(v,u); jacint@1077: } jacint@1077: } jacint@1077: } jacint@1077: jacint@1077: jacint@1165: ///Writes the matching stored to a \c bool valued \c Edge map. jacint@1077: jacint@1165: ///Writes the matching stored to a \c bool valued \c Edge jacint@1165: ///map. This map will have the property that there are no two jacint@1165: ///incident edges \c e, \c f with \c map[e]==map[f]==true. The jacint@1165: ///edges \c e with \c map[e]==true form the matching. jacint@1077: template jacint@1077: void writeEMapBool (EMapB& map) const { klao@1909: for(UEdgeIt e(g); e!=INVALID; ++e) map.set(e,false); jacint@1077: jacint@1077: typename Graph::template NodeMap todo(g,true); jacint@1077: for(NodeIt v(g); v!=INVALID; ++v) { jacint@1093: if ( todo[v] && _mate[v]!=INVALID ) { jacint@1093: Node u=_mate[v]; jacint@1077: for(IncEdgeIt e(g,v); e!=INVALID; ++e) { klao@1158: if ( g.runningNode(e) == u ) { jacint@1077: map.set(e,true); jacint@1077: todo.set(u,false); jacint@1077: todo.set(v,false); jacint@1077: break; jacint@1077: } jacint@1077: } jacint@1077: } jacint@1077: } jacint@1077: } jacint@1077: jacint@1077: jacint@1077: ///Writes the canonical decomposition of the graph after running jacint@1077: ///the algorithm. jacint@1077: jacint@1090: ///After calling any run methods of the class, it writes the jacint@1090: ///Gallai-Edmonds canonical decomposition of the graph. \c map jacint@1090: ///must be a node map of \ref pos_enum 's. jacint@1077: template jacint@1077: void writePos (NMapEnum& map) const { jacint@1077: for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]); jacint@1077: } jacint@1077: jacint@1077: private: jacint@1077: jacint@1165: jacint@1077: void lateShrink(Node v, typename Graph::template NodeMap& ear, jacint@1077: UFE& blossom, UFE& tree); jacint@1077: alpar@1234: void normShrink(Node v, typename Graph::template NodeMap& ear, jacint@1077: UFE& blossom, UFE& tree); jacint@1077: jacint@2023: void shrink(Node x,Node y, typename Graph::template NodeMap& ear, jacint@2023: UFE& blossom, UFE& tree,std::queue& Q); jacint@1077: alpar@1234: void shrinkStep(Node& top, Node& middle, Node& bottom, alpar@1234: typename Graph::template NodeMap& ear, jacint@1077: UFE& blossom, UFE& tree, std::queue& Q); jacint@1077: jacint@2023: bool growOrAugment(Node& y, Node& x, typename Graph::template jacint@2023: NodeMap& ear, UFE& blossom, UFE& tree, jacint@2023: std::queue& Q); jacint@2023: alpar@1234: void augment(Node x, typename Graph::template NodeMap& ear, jacint@1077: UFE& blossom, UFE& tree); jacint@1077: jacint@1077: }; jacint@1077: jacint@1077: jacint@1077: // ********************************************************************** jacint@1077: // IMPLEMENTATIONS jacint@1077: // ********************************************************************** jacint@1077: jacint@1077: jacint@1077: template jacint@2023: void MaxMatching::lateShrink(Node v, typename Graph::template jacint@2023: NodeMap& ear, UFE& blossom, UFE& tree) { jacint@2023: //We have one tree which we grow, and also shrink but only if it cannot be jacint@2023: //postponed. If we augment then we return to the "for" cycle of jacint@2023: //runEdmonds(). jacint@1077: jacint@1077: std::queue Q; //queue of the totally unscanned nodes jacint@1077: Q.push(v); jacint@1077: std::queue R; jacint@1077: //queue of the nodes which must be scanned for a possible shrink jacint@1077: jacint@1077: while ( !Q.empty() ) { jacint@1077: Node x=Q.front(); jacint@1077: Q.pop(); jacint@2023: for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { jacint@2023: Node y=g.runningNode(e); jacint@2023: //growOrAugment grows if y is covered by the matching and jacint@2023: //augments if not. In this latter case it returns 1. jacint@2023: if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return; jacint@2023: } jacint@2023: R.push(x); jacint@1077: } jacint@1077: jacint@1077: while ( !R.empty() ) { jacint@1077: Node x=R.front(); jacint@1077: R.pop(); jacint@1077: jacint@1077: for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) { klao@1158: Node y=g.runningNode(e); jacint@1077: jacint@2023: if ( position[y] == D && blossom.find(x) != blossom.find(y) ) jacint@2023: //Recall that we have only one tree. jacint@2023: shrink( x, y, ear, blossom, tree, Q); jacint@1077: jacint@1077: while ( !Q.empty() ) { jacint@1077: Node x=Q.front(); jacint@1077: Q.pop(); jacint@2023: for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { jacint@2023: Node y=g.runningNode(e); jacint@2023: //growOrAugment grows if y is covered by the matching and jacint@2023: //augments if not. In this latter case it returns 1. jacint@2023: if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return; jacint@2023: } jacint@2023: R.push(x); jacint@1077: } jacint@1077: } //for e jacint@1077: } // while ( !R.empty() ) jacint@1077: } jacint@1077: jacint@1077: jacint@1077: template alpar@1234: void MaxMatching::normShrink(Node v, alpar@1234: typename Graph::template alpar@1234: NodeMap& ear, jacint@1077: UFE& blossom, UFE& tree) { jacint@2023: //We have one tree, which we grow and shrink. If we augment then we jacint@2023: //return to the "for" cycle of runEdmonds(). jacint@2023: jacint@1077: std::queue Q; //queue of the unscanned nodes jacint@1077: Q.push(v); jacint@1077: while ( !Q.empty() ) { jacint@1077: jacint@1077: Node x=Q.front(); jacint@1077: Q.pop(); jacint@1077: jacint@1077: for( IncEdgeIt e(g,x); e!=INVALID; ++e ) { klao@1158: Node y=g.runningNode(e); jacint@1077: jacint@1077: switch ( position[y] ) { jacint@1077: case D: //x and y must be in the same tree jacint@2023: if ( blossom.find(x) != blossom.find(y) ) jacint@2023: //x and y are in the same tree jacint@2023: shrink( x, y, ear, blossom, tree, Q); jacint@1077: break; jacint@1077: case C: jacint@2023: //growOrAugment grows if y is covered by the matching and jacint@2023: //augments if not. In this latter case it returns 1. jacint@2023: if ( growOrAugment(y, x, ear, blossom, tree, Q) ) return; jacint@1077: break; jacint@1077: default: break; jacint@2023: } jacint@1077: } jacint@1077: } jacint@1077: } jacint@2023: jacint@1077: jacint@1077: template jacint@2023: void MaxMatching::shrink(Node x,Node y, typename jacint@2023: Graph::template NodeMap& ear, jacint@2023: UFE& blossom, UFE& tree, std::queue& Q) { jacint@2023: //x and y are the two adjacent vertices in two blossoms. jacint@2023: jacint@2023: typename Graph::template NodeMap path(g,false); jacint@2023: jacint@2023: Node b=blossom.find(x); jacint@2023: path.set(b,true); jacint@2023: b=_mate[b]; jacint@2023: while ( b!=INVALID ) { jacint@2023: b=blossom.find(ear[b]); jacint@2023: path.set(b,true); jacint@2023: b=_mate[b]; jacint@2023: } //we go until the root through bases of blossoms and odd vertices jacint@2023: jacint@2023: Node top=y; jacint@2023: Node middle=blossom.find(top); jacint@2023: Node bottom=x; jacint@2023: while ( !path[middle] ) jacint@2023: shrinkStep(top, middle, bottom, ear, blossom, tree, Q); jacint@2023: //Until we arrive to a node on the path, we update blossom, tree jacint@2023: //and the positions of the odd nodes. jacint@2023: jacint@2023: Node base=middle; jacint@2023: top=x; jacint@2023: middle=blossom.find(top); jacint@2023: bottom=y; jacint@2023: Node blossom_base=blossom.find(base); jacint@2023: while ( middle!=blossom_base ) jacint@2023: shrinkStep(top, middle, bottom, ear, blossom, tree, Q); jacint@2023: //Until we arrive to a node on the path, we update blossom, tree jacint@2023: //and the positions of the odd nodes. jacint@2023: jacint@2023: blossom.makeRep(base); jacint@1077: } jacint@1077: jacint@2023: jacint@2023: jacint@1077: template alpar@1234: void MaxMatching::shrinkStep(Node& top, Node& middle, Node& bottom, alpar@1234: typename Graph::template alpar@1234: NodeMap& ear, alpar@1234: UFE& blossom, UFE& tree, alpar@1234: std::queue& Q) { jacint@2023: //We traverse a blossom and update everything. jacint@2023: jacint@1077: ear.set(top,bottom); jacint@1077: Node t=top; jacint@1077: while ( t!=middle ) { jacint@1093: Node u=_mate[t]; jacint@1077: t=ear[u]; jacint@1077: ear.set(t,u); jacint@1077: } jacint@1093: bottom=_mate[middle]; jacint@1077: position.set(bottom,D); jacint@1077: Q.push(bottom); jacint@1077: top=ear[bottom]; jacint@1077: Node oldmiddle=middle; jacint@1077: middle=blossom.find(top); jacint@1077: tree.erase(bottom); jacint@1077: tree.erase(oldmiddle); jacint@1077: blossom.insert(bottom); jacint@1077: blossom.join(bottom, oldmiddle); jacint@1077: blossom.join(top, oldmiddle); jacint@1077: } jacint@1077: jacint@2023: jacint@2023: template jacint@2023: bool MaxMatching::growOrAugment(Node& y, Node& x, typename Graph::template jacint@2023: NodeMap& ear, UFE& blossom, UFE& tree, jacint@2023: std::queue& Q) { jacint@2023: //x is in a blossom in the tree, y is outside. If y is covered by jacint@2023: //the matching we grow, otherwise we augment. In this case we jacint@2023: //return 1. jacint@2023: jacint@2023: if ( _mate[y]!=INVALID ) { //grow jacint@2023: ear.set(y,x); jacint@2023: Node w=_mate[y]; jacint@2023: blossom.insert(w); jacint@2023: position.set(y,A); jacint@2023: position.set(w,D); jacint@2023: tree.insert(y); jacint@2023: tree.insert(w); jacint@2023: tree.join(y,blossom.find(x)); jacint@2023: tree.join(w,y); jacint@2023: Q.push(w); jacint@2023: } else { //augment jacint@2023: augment(x, ear, blossom, tree); jacint@2023: _mate.set(x,y); jacint@2023: _mate.set(y,x); jacint@2023: return true; jacint@2023: } jacint@2023: return false; jacint@2023: } jacint@2023: jacint@2023: jacint@1077: template alpar@1234: void MaxMatching::augment(Node x, alpar@1234: typename Graph::template NodeMap& ear, jacint@1077: UFE& blossom, UFE& tree) { jacint@1093: Node v=_mate[x]; jacint@1077: while ( v!=INVALID ) { jacint@1077: jacint@1077: Node u=ear[v]; jacint@1093: _mate.set(v,u); jacint@1077: Node tmp=v; jacint@1093: v=_mate[u]; jacint@1093: _mate.set(u,tmp); jacint@1077: } jacint@2023: Node y=blossom.find(x); deba@2205: for (typename UFE::ItemIt tit(tree, y); tit != INVALID; ++tit) { deba@2205: if ( position[tit] == D ) { deba@2205: for (typename UFE::ItemIt bit(blossom, tit); bit != INVALID; ++bit) { deba@2205: position.set( bit ,C); jacint@1077: } deba@2205: blossom.eraseClass(tit); deba@2205: } else position.set( tit ,C); jacint@1077: } jacint@2023: tree.eraseClass(y); jacint@1077: jacint@1077: } jacint@1077: jacint@1077: jacint@1077: } //END OF NAMESPACE LEMON jacint@1077: jacint@1165: #endif //LEMON_MAX_MATCHING_H