alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/unionfind.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@921: #ifndef LEMON_UNION_FIND_H alpar@921: #define LEMON_UNION_FIND_H beckerjc@483: klao@491: //!\ingroup auxdat beckerjc@483: //!\file beckerjc@483: //!\brief Union-Find data structures. alpar@774: //! alpar@774: //!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but alpar@774: //!fails to run (Segmentation fault). beckerjc@483: beckerjc@483: beckerjc@483: #include beckerjc@483: #include beckerjc@483: #include beckerjc@483: #include beckerjc@483: alpar@921: #include beckerjc@483: alpar@921: namespace lemon { beckerjc@483: beckerjc@483: //! \addtogroup auxdat beckerjc@483: //! @{ beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief A \e Union-Find data structure implementation beckerjc@483: * beckerjc@483: * The class implements the \e Union-Find data structure. beckerjc@483: * The union operation uses rank heuristic, while athos@649: * the find operation uses path compression. beckerjc@483: * This is a very simple but efficient implementation, providing beckerjc@483: * only four methods: join (union), find, insert and size. beckerjc@483: * For more features see the \ref UnionFindEnum class. beckerjc@483: * alpar@810: * It is primarily used in Kruskal algorithm for finding minimal alpar@810: * cost spanning tree in a graph. alpar@810: * \sa kruskal() alpar@810: * beckerjc@483: * \pre The elements are automatically added only if the map beckerjc@483: * given to the constructor was filled with -1's. Otherwise you beckerjc@483: * need to add all the elements by the \ref insert() method. alpar@810: * \bug It is not clear what the constructor parameter is used for. beckerjc@483: */ beckerjc@483: beckerjc@483: template beckerjc@483: class UnionFind { beckerjc@483: beckerjc@483: public: beckerjc@483: typedef T ElementType; beckerjc@483: typedef std::pair PairType; beckerjc@483: beckerjc@483: private: beckerjc@483: std::vector data; beckerjc@483: TIntMap& map; beckerjc@483: beckerjc@483: public: beckerjc@483: UnionFind(TIntMap& m) : map(m) {} beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Returns the index of the element's component. beckerjc@483: * beckerjc@483: * The method returns the index of the element's component. beckerjc@483: * This is an integer between zero and the number of inserted elements. beckerjc@483: */ beckerjc@483: beckerjc@483: int find(T a) beckerjc@483: { beckerjc@483: int comp0 = map[a]; beckerjc@483: if (comp0 < 0) { beckerjc@483: return insert(a); beckerjc@483: } beckerjc@483: int comp = comp0; beckerjc@483: int next; beckerjc@483: while ( (next = data[comp].first) != comp) { beckerjc@483: comp = next; beckerjc@483: } beckerjc@483: while ( (next = data[comp0].first) != comp) { beckerjc@483: data[comp0].first = comp; beckerjc@483: comp0 = next; beckerjc@483: } beckerjc@483: beckerjc@483: return comp; beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Insert a new element into the structure. beckerjc@483: * beckerjc@483: * This method inserts a new element into the data structure. beckerjc@483: * beckerjc@483: * It is not required to use this method: beckerjc@483: * if the map given to the constructor was filled beckerjc@483: * with -1's then it is called automatically beckerjc@483: * on the first \ref find or \ref join. beckerjc@483: * beckerjc@483: * The method returns the index of the new component. beckerjc@483: */ beckerjc@483: beckerjc@483: int insert(T a) beckerjc@483: { beckerjc@483: int n = data.size(); beckerjc@483: data.push_back(std::make_pair(n, 1)); beckerjc@483: map.set(a,n); beckerjc@483: return n; beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Joining the components of element \e a and element \e b. beckerjc@483: * beckerjc@483: * This is the \e union operation of the Union-Find structure. beckerjc@483: * Joins the component of elemenent \e a and component of beckerjc@483: * element \e b. If \e a and \e b are in the same component then beckerjc@483: * it returns false otherwise it returns true. beckerjc@483: */ beckerjc@483: beckerjc@483: bool join(T a, T b) beckerjc@483: { beckerjc@483: int ca = find(a); beckerjc@483: int cb = find(b); beckerjc@483: beckerjc@483: if ( ca == cb ) beckerjc@483: return false; beckerjc@483: beckerjc@483: if ( data[ca].second > data[cb].second ) { beckerjc@483: data[cb].first = ca; beckerjc@483: data[ca].second += data[cb].second; beckerjc@483: } beckerjc@483: else { beckerjc@483: data[ca].first = cb; beckerjc@483: data[cb].second += data[ca].second; beckerjc@483: } beckerjc@483: return true; beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Returns the size of the component of element \e a. beckerjc@483: * beckerjc@483: * Returns the size of the component of element \e a. beckerjc@483: */ beckerjc@483: beckerjc@483: int size(T a) beckerjc@483: { beckerjc@483: int ca = find(a); beckerjc@483: return data[ca].second; beckerjc@483: } beckerjc@483: beckerjc@483: }; beckerjc@483: beckerjc@483: beckerjc@483: beckerjc@483: beckerjc@483: /*******************************************************/ beckerjc@483: beckerjc@483: beckerjc@483: #ifdef DEVELOPMENT_DOCS beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief The auxiliary class for the \ref UnionFindEnum class. beckerjc@483: * beckerjc@483: * In the \ref UnionFindEnum class all components are represented as beckerjc@483: * a std::list. beckerjc@483: * Items of these lists are UnionFindEnumItem structures. beckerjc@483: * beckerjc@483: * The class has four fields: beckerjc@483: * - T me - the actual element beckerjc@483: * - IIter parent - the parent of the element in the union-find structure beckerjc@483: * - int size - the size of the component of the element. beckerjc@483: * Only valid if the element beckerjc@483: * is the leader of the component. beckerjc@483: * - CIter my_class - pointer into the list of components beckerjc@483: * pointing to the component of the element. beckerjc@483: * Only valid if the element is the leader of the component. beckerjc@483: */ beckerjc@483: beckerjc@483: #endif beckerjc@483: beckerjc@483: template beckerjc@483: struct UnionFindEnumItem { beckerjc@483: beckerjc@483: typedef std::list ItemList; beckerjc@483: typedef std::list ClassList; beckerjc@483: typedef typename ItemList::iterator IIter; beckerjc@483: typedef typename ClassList::iterator CIter; beckerjc@483: beckerjc@483: T me; beckerjc@483: IIter parent; beckerjc@483: int size; beckerjc@483: CIter my_class; beckerjc@483: beckerjc@483: UnionFindEnumItem() {} beckerjc@483: UnionFindEnumItem(const T &_me, CIter _my_class): beckerjc@483: me(_me), size(1), my_class(_my_class) {} beckerjc@483: }; beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief A \e Union-Find data structure implementation which beckerjc@483: * is able to enumerate the components. beckerjc@483: * athos@649: * The class implements a \e Union-Find data structure beckerjc@483: * which is able to enumerate the components and the items in beckerjc@483: * a component. If you don't need this feature then perhaps it's beckerjc@483: * better to use the \ref UnionFind class which is more efficient. beckerjc@483: * beckerjc@483: * The union operation uses rank heuristic, while athos@649: * the find operation uses path compression. beckerjc@483: * beckerjc@483: * \pre You beckerjc@483: * need to add all the elements by the \ref insert() method. beckerjc@483: */ beckerjc@483: beckerjc@483: beckerjc@483: template class Map> beckerjc@483: class UnionFindEnum { beckerjc@483: beckerjc@483: typedef std::list > ItemList; beckerjc@483: typedef std::list ClassList; beckerjc@483: typedef typename ItemList::iterator IIter; beckerjc@483: typedef typename ItemList::const_iterator IcIter; beckerjc@483: typedef typename ClassList::iterator CIter; beckerjc@483: typedef typename ClassList::const_iterator CcIter; beckerjc@483: beckerjc@483: public: beckerjc@483: typedef T ElementType; beckerjc@483: typedef UnionFindEnumItem ItemType; beckerjc@483: typedef Map< IIter > MapType; beckerjc@483: beckerjc@483: private: beckerjc@483: MapType& m; beckerjc@483: ClassList classes; beckerjc@483: beckerjc@483: IIter _find(IIter a) const { beckerjc@483: IIter comp = a; beckerjc@483: IIter next; beckerjc@483: while( (next = comp->parent) != comp ) { beckerjc@483: comp = next; beckerjc@483: } beckerjc@483: beckerjc@483: IIter comp1 = a; beckerjc@483: while( (next = comp1->parent) != comp ) { beckerjc@483: comp1->parent = comp->parent; beckerjc@483: comp1 = next; beckerjc@483: } beckerjc@483: return comp; beckerjc@483: } beckerjc@483: beckerjc@483: public: beckerjc@483: UnionFindEnum(MapType& _m) : m(_m) {} beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Insert the given element into a new component. beckerjc@483: * beckerjc@483: * This method creates a new component consisting only of the beckerjc@483: * given element. beckerjc@483: */ beckerjc@483: beckerjc@483: void insert(const T &a) beckerjc@483: { beckerjc@483: beckerjc@483: beckerjc@483: classes.push_back(ItemList()); beckerjc@483: CIter aclass = classes.end(); beckerjc@483: --aclass; beckerjc@483: beckerjc@483: ItemList &alist = *aclass; beckerjc@483: alist.push_back(ItemType(a, aclass)); beckerjc@483: IIter ai = alist.begin(); beckerjc@483: beckerjc@483: ai->parent = ai; beckerjc@483: m.set(a, ai); beckerjc@483: beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Insert the given element into the component of the others. beckerjc@483: * beckerjc@483: * This methods insert the element \e a into the component of the beckerjc@483: * element \e comp. beckerjc@483: */ beckerjc@483: beckerjc@483: void insert(const T &a, const T &comp) { beckerjc@483: beckerjc@483: IIter clit = _find(m[comp]); beckerjc@483: ItemList &c = *clit->my_class; beckerjc@483: c.push_back(ItemType(a,0)); beckerjc@483: IIter ai = c.end(); beckerjc@483: --ai; beckerjc@483: ai->parent = clit; beckerjc@483: m.set(a, ai); beckerjc@483: ++clit->size; beckerjc@483: } beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Find the leader of the component of the given element. beckerjc@483: * beckerjc@483: * The method returns the leader of the component of the given element. beckerjc@483: */ beckerjc@483: beckerjc@483: T find(const T &a) const { beckerjc@483: return _find(m[a])->me; beckerjc@483: } beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Joining the component of element \e a and element \e b. beckerjc@483: * beckerjc@483: * This is the \e union operation of the Union-Find structure. beckerjc@483: * Joins the component of elemenent \e a and component of beckerjc@483: * element \e b. If \e a and \e b are in the same component then beckerjc@483: * returns false else returns true. beckerjc@483: */ beckerjc@483: beckerjc@483: bool join(T a, T b) { beckerjc@483: beckerjc@483: IIter ca = _find(m[a]); beckerjc@483: IIter cb = _find(m[b]); beckerjc@483: beckerjc@483: if ( ca == cb ) { beckerjc@483: return false; beckerjc@483: } beckerjc@483: beckerjc@483: if ( ca->size > cb->size ) { beckerjc@483: beckerjc@483: cb->parent = ca->parent; beckerjc@483: ca->size += cb->size; beckerjc@483: beckerjc@483: ItemList &alist = *ca->my_class; beckerjc@483: alist.splice(alist.end(),*cb->my_class); beckerjc@483: beckerjc@483: classes.erase(cb->my_class); beckerjc@483: cb->my_class = 0; beckerjc@483: } beckerjc@483: else { beckerjc@483: beckerjc@483: ca->parent = cb->parent; beckerjc@483: cb->size += ca->size; beckerjc@483: beckerjc@483: ItemList &blist = *cb->my_class; beckerjc@483: blist.splice(blist.end(),*ca->my_class); beckerjc@483: beckerjc@483: classes.erase(ca->my_class); beckerjc@483: ca->my_class = 0; beckerjc@483: } beckerjc@483: beckerjc@483: return true; beckerjc@483: } beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Returns the size of the component of element \e a. beckerjc@483: * beckerjc@483: * Returns the size of the component of element \e a. beckerjc@483: */ beckerjc@483: beckerjc@483: int size(const T &a) const { beckerjc@483: return _find(m[a])->size; beckerjc@483: } beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Split up the component of the element. beckerjc@483: * beckerjc@483: * Splitting the component of the element into sigleton beckerjc@483: * components (component of size one). beckerjc@483: */ beckerjc@483: beckerjc@483: void split(const T &a) { beckerjc@483: beckerjc@483: IIter ca = _find(m[a]); beckerjc@483: beckerjc@483: if ( ca->size == 1 ) beckerjc@483: return; beckerjc@483: beckerjc@483: CIter aclass = ca->my_class; beckerjc@483: beckerjc@483: for(IIter curr = ca; ++curr != aclass->end(); curr=ca) { beckerjc@483: classes.push_back(ItemList()); beckerjc@483: CIter nl = --classes.end(); beckerjc@483: nl->splice(nl->end(), *aclass, curr); beckerjc@483: beckerjc@483: curr->size=1; beckerjc@483: curr->parent=curr; beckerjc@483: curr->my_class = nl; beckerjc@483: } beckerjc@483: beckerjc@483: ca->size=1; beckerjc@483: return; beckerjc@483: } beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Set the given element to the leader element of its component. beckerjc@483: * beckerjc@483: * Set the given element to the leader element of its component. beckerjc@483: */ beckerjc@483: beckerjc@483: void makeRep(const T &a) { beckerjc@483: beckerjc@483: IIter ia = m[a]; beckerjc@483: IIter la = _find(ia); beckerjc@483: if (la == ia) return; beckerjc@483: beckerjc@483: ia->my_class = la->my_class; beckerjc@483: la->my_class = 0; beckerjc@483: beckerjc@483: ia->size = la->size; beckerjc@483: beckerjc@483: CIter l = ia->my_class; beckerjc@483: l->splice(l->begin(),*l,ia); beckerjc@483: beckerjc@483: ia->parent = ia; beckerjc@483: la->parent = ia; beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Move the given element to an other component. beckerjc@483: * beckerjc@483: * This method moves the element \e a from its component beckerjc@483: * to the component of \e comp. beckerjc@483: * If \e a and \e comp are in the same component then beckerjc@483: * it returns false otherwise it returns true. beckerjc@483: */ beckerjc@483: beckerjc@483: bool move(const T &a, const T &comp) { beckerjc@483: beckerjc@483: IIter ai = m[a]; beckerjc@483: IIter lai = _find(ai); beckerjc@483: IIter clit = _find(m[comp]); beckerjc@483: beckerjc@483: if (lai == clit) beckerjc@483: return false; beckerjc@483: klao@914: ItemList &cl = *clit->my_class, klao@914: &al = *lai->my_class; beckerjc@483: beckerjc@483: bool is_leader = (lai == ai); beckerjc@483: bool singleton = false; beckerjc@483: beckerjc@483: if (is_leader) { beckerjc@483: ++lai; beckerjc@483: } beckerjc@483: klao@914: cl.splice(cl.end(), al, ai); beckerjc@483: beckerjc@483: if (is_leader) { beckerjc@483: if (ai->size == 1) { beckerjc@483: classes.erase(ai->my_class); beckerjc@483: singleton = true; beckerjc@483: } beckerjc@483: else { beckerjc@483: lai->size = ai->size; beckerjc@483: lai->my_class = ai->my_class; beckerjc@483: } beckerjc@483: } beckerjc@483: if (!singleton) { klao@914: for (IIter i = lai; i != al.end(); ++i) beckerjc@483: i->parent = lai; beckerjc@483: --lai->size; beckerjc@483: } beckerjc@483: beckerjc@483: ai->parent = clit; beckerjc@483: ai->my_class = 0; beckerjc@483: ++clit->size; beckerjc@483: beckerjc@483: return true; beckerjc@483: } beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Remove the given element from the structure. beckerjc@483: * beckerjc@483: * Remove the given element from the structure. beckerjc@483: * beckerjc@483: * Removes the element from its component and if the component becomes beckerjc@483: * empty then removes that component from the component list. beckerjc@483: */ beckerjc@483: void erase(const T &a) { beckerjc@483: beckerjc@483: IIter ma = m[a]; beckerjc@483: if (ma == 0) return; beckerjc@483: beckerjc@483: IIter la = _find(ma); beckerjc@483: if (la == ma) { beckerjc@483: if (ma -> size == 1){ beckerjc@483: classes.erase(ma->my_class); beckerjc@483: m.set(a,0); beckerjc@483: return; beckerjc@483: } beckerjc@483: ++la; beckerjc@483: la->size = ma->size; beckerjc@483: la->my_class = ma->my_class; beckerjc@483: } beckerjc@483: beckerjc@483: for (IIter i = la; i != la->my_class->end(); ++i) { beckerjc@483: i->parent = la; beckerjc@483: } beckerjc@483: beckerjc@483: la->size--; beckerjc@483: la->my_class->erase(ma); beckerjc@483: m.set(a,0); beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Removes the component of the given element from the structure. beckerjc@483: * beckerjc@483: * Removes the component of the given element from the structure. beckerjc@483: */ beckerjc@483: beckerjc@483: void eraseClass(const T &a) { beckerjc@483: IIter ma = m[a]; beckerjc@483: if (ma == 0) return; beckerjc@483: # ifdef DEBUG beckerjc@483: CIter c = _find(ma)->my_class; beckerjc@483: for (IIter i=c->begin(); i!=c->end(); ++i) beckerjc@483: m.set(i->me, 0); beckerjc@483: # endif beckerjc@483: classes.erase(_find(ma)->my_class); beckerjc@483: } beckerjc@483: beckerjc@483: beckerjc@483: class ClassIt { beckerjc@483: friend class UnionFindEnum; beckerjc@483: beckerjc@483: CcIter i; beckerjc@483: public: beckerjc@483: ClassIt(Invalid): i(0) {} beckerjc@483: ClassIt() {} beckerjc@483: beckerjc@483: operator const T& () const { beckerjc@483: ItemList const &ll = *i; beckerjc@483: return (ll.begin())->me; } beckerjc@483: bool operator == (ClassIt it) const { beckerjc@483: return (i == it.i); beckerjc@483: } beckerjc@483: bool operator != (ClassIt it) const { beckerjc@483: return (i != it.i); beckerjc@483: } beckerjc@483: bool operator < (ClassIt it) const { beckerjc@483: return (i < it.i); beckerjc@483: } beckerjc@483: beckerjc@483: bool valid() const { return i != 0; } beckerjc@483: private: beckerjc@483: void first(const ClassList &l) { i = l.begin(); validate(l); } beckerjc@483: void next(const ClassList &l) { beckerjc@483: ++i; beckerjc@483: validate(l); beckerjc@483: } beckerjc@483: void validate(const ClassList &l) { beckerjc@483: if ( i == l.end() ) beckerjc@483: i = 0; beckerjc@483: } beckerjc@483: }; beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Sets the iterator to point to the first component. beckerjc@483: * beckerjc@483: * Sets the iterator to point to the first component. beckerjc@483: * beckerjc@483: * With the \ref first, \ref valid and \ref next methods you can beckerjc@483: * iterate through the components. For example: beckerjc@483: * \code beckerjc@483: * UnionFindEnum::MapType map(G); beckerjc@483: * UnionFindEnum U(map); beckerjc@483: * UnionFindEnum::ClassIt iter; beckerjc@483: * for (U.first(iter); U.valid(iter); U.next(iter)) { beckerjc@483: * // iter is convertible to Graph::Node beckerjc@483: * cout << iter << endl; beckerjc@483: * } beckerjc@483: * \endcode beckerjc@483: */ beckerjc@483: beckerjc@483: ClassIt& first(ClassIt& it) const { beckerjc@483: it.first(classes); beckerjc@483: return it; beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Returns whether the iterator is valid. beckerjc@483: * beckerjc@483: * Returns whether the iterator is valid. beckerjc@483: * beckerjc@483: * With the \ref first, \ref valid and \ref next methods you can beckerjc@483: * iterate through the components. See the example here: \ref first. beckerjc@483: */ beckerjc@483: beckerjc@483: bool valid(ClassIt const &it) const { beckerjc@483: return it.valid(); beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Steps the iterator to the next component. beckerjc@483: * beckerjc@483: * Steps the iterator to the next component. beckerjc@483: * beckerjc@483: * With the \ref first, \ref valid and \ref next methods you can beckerjc@483: * iterate through the components. See the example here: \ref first. beckerjc@483: */ beckerjc@483: beckerjc@483: ClassIt& next(ClassIt& it) const { beckerjc@483: it.next(classes); beckerjc@483: return it; beckerjc@483: } beckerjc@483: beckerjc@483: beckerjc@483: class ItemIt { beckerjc@483: friend class UnionFindEnum; beckerjc@483: beckerjc@483: IcIter i; beckerjc@483: const ItemList *l; beckerjc@483: public: beckerjc@483: ItemIt(Invalid): i(0) {} beckerjc@483: ItemIt() {} beckerjc@483: beckerjc@483: operator const T& () const { return i->me; } beckerjc@483: bool operator == (ItemIt it) const { beckerjc@483: return (i == it.i); beckerjc@483: } beckerjc@483: bool operator != (ItemIt it) const { beckerjc@483: return (i != it.i); beckerjc@483: } beckerjc@483: bool operator < (ItemIt it) const { beckerjc@483: return (i < it.i); beckerjc@483: } beckerjc@483: beckerjc@483: bool valid() const { return i != 0; } beckerjc@483: private: beckerjc@483: void first(const ItemList &il) { l=&il; i = l->begin(); validate(); } beckerjc@483: void next() { beckerjc@483: ++i; beckerjc@483: validate(); beckerjc@483: } beckerjc@483: void validate() { beckerjc@483: if ( i == l->end() ) beckerjc@483: i = 0; beckerjc@483: } beckerjc@483: }; beckerjc@483: beckerjc@483: beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Sets the iterator to point to the first element of the component. beckerjc@483: * beckerjc@483: * \anchor first2 beckerjc@483: * Sets the iterator to point to the first element of the component. beckerjc@483: * beckerjc@483: * With the \ref first2 "first", \ref valid2 "valid" beckerjc@483: * and \ref next2 "next" methods you can beckerjc@483: * iterate through the elements of a component. For example beckerjc@483: * (iterating through the component of the node \e node): beckerjc@483: * \code beckerjc@483: * Graph::Node node = ...; beckerjc@483: * UnionFindEnum::MapType map(G); beckerjc@483: * UnionFindEnum U(map); beckerjc@483: * UnionFindEnum::ItemIt iiter; beckerjc@483: * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) { beckerjc@483: * // iiter is convertible to Graph::Node beckerjc@483: * cout << iiter << endl; beckerjc@483: * } beckerjc@483: * \endcode beckerjc@483: */ beckerjc@483: beckerjc@483: ItemIt& first(ItemIt& it, const T& a) const { beckerjc@483: it.first( * _find(m[a])->my_class ); beckerjc@483: return it; beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Returns whether the iterator is valid. beckerjc@483: * beckerjc@483: * \anchor valid2 beckerjc@483: * Returns whether the iterator is valid. beckerjc@483: * beckerjc@483: * With the \ref first2 "first", \ref valid2 "valid" beckerjc@483: * and \ref next2 "next" methods you can beckerjc@483: * iterate through the elements of a component. beckerjc@483: * See the example here: \ref first2 "first". beckerjc@483: */ beckerjc@483: beckerjc@483: bool valid(ItemIt const &it) const { beckerjc@483: return it.valid(); beckerjc@483: } beckerjc@483: beckerjc@483: /** beckerjc@483: * \brief Steps the iterator to the next component. beckerjc@483: * beckerjc@483: * \anchor next2 beckerjc@483: * Steps the iterator to the next component. beckerjc@483: * beckerjc@483: * With the \ref first2 "first", \ref valid2 "valid" beckerjc@483: * and \ref next2 "next" methods you can beckerjc@483: * iterate through the elements of a component. beckerjc@483: * See the example here: \ref first2 "first". beckerjc@483: */ beckerjc@483: beckerjc@483: ItemIt& next(ItemIt& it) const { beckerjc@483: it.next(); beckerjc@483: return it; beckerjc@483: } beckerjc@483: beckerjc@483: }; beckerjc@483: beckerjc@483: beckerjc@483: //! @} beckerjc@483: alpar@921: } //namespace lemon beckerjc@483: alpar@921: #endif //LEMON_UNION_FIND_H