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 <vector>
beckerjc@483: #include <list>
beckerjc@483: #include <utility>
beckerjc@483: #include <algorithm>
beckerjc@483: 
alpar@921: #include <lemon/invalid.h>
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 <typename T, typename TIntMap>
beckerjc@483:   class UnionFind {
beckerjc@483:     
beckerjc@483:   public:
beckerjc@483:     typedef T ElementType;
beckerjc@483:     typedef std::pair<int,int> PairType;
beckerjc@483: 
beckerjc@483:   private:
beckerjc@483:     std::vector<PairType> 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 <typename T>
beckerjc@483:   struct UnionFindEnumItem {
beckerjc@483: 
beckerjc@483:     typedef std::list<UnionFindEnumItem> ItemList;
beckerjc@483:     typedef std::list<ItemList> 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 <typename T, template <typename Item> class Map>
beckerjc@483:   class UnionFindEnum {
beckerjc@483: 
beckerjc@483:     typedef std::list<UnionFindEnumItem<T> > ItemList;
beckerjc@483:     typedef std::list<ItemList> 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<T> 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<Graph::Node, Graph::NodeMap>::MapType map(G);
beckerjc@483:      * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
beckerjc@483:      * UnionFindEnum<Graph::Node, Graph::NodeMap>::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<Graph::Node, Graph::NodeMap>::MapType map(G);
beckerjc@483:      * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
beckerjc@483:      * UnionFindEnum<Graph::Node, Graph::NodeMap>::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