lemon/unionfind.h
author deba
Fri, 04 Nov 2005 16:10:23 +0000
changeset 1769 a67ec111236c
parent 1359 1581f961cfaa
child 1779 f6cafba4dbf2
permissions -rw-r--r--
Removed todo
Moved to topology module
     1 /* -*- C++ -*-
     2  * lemon/unionfind.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_UNION_FIND_H
    18 #define LEMON_UNION_FIND_H
    19 
    20 //!\ingroup auxdat
    21 //!\file
    22 //!\brief Union-Find data structures.
    23 //!
    24 //!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
    25 //!fails to run (Segmentation fault).
    26 
    27 
    28 #include <vector>
    29 #include <list>
    30 #include <utility>
    31 #include <algorithm>
    32 
    33 #include <lemon/invalid.h>
    34 
    35 namespace lemon {
    36 
    37   //! \addtogroup auxdat
    38   //! @{
    39 
    40   /**
    41    * \brief A \e Union-Find data structure implementation
    42    *
    43    * The class implements the \e Union-Find data structure. 
    44    * The union operation uses rank heuristic, while
    45    * the find operation uses path compression.
    46    * This is a very simple but efficient implementation, providing 
    47    * only four methods: join (union), find, insert and size.
    48    * For more features see the \ref UnionFindEnum class.
    49    *
    50    * It is primarily used in Kruskal algorithm for finding minimal
    51    * cost spanning tree in a graph.
    52    * \sa kruskal()
    53    *
    54    * \pre The elements are automatically added only if the map 
    55    * given to the constructor was filled with -1's. Otherwise you
    56    * need to add all the elements by the \ref insert() method.
    57    * \bug It is not clear what the constructor parameter is used for.
    58    */
    59 
    60   template <typename T, typename TIntMap>
    61   class UnionFind {
    62     
    63   public:
    64     typedef T ElementType;
    65     typedef std::pair<int,int> PairType;
    66 
    67   private:
    68     std::vector<PairType> data;
    69     TIntMap& map;
    70 
    71   public:
    72     UnionFind(TIntMap& m) : map(m) {}
    73 
    74     /**
    75      * \brief Returns the index of the element's component.
    76      *
    77      * The method returns the index of the element's component.
    78      * This is an integer between zero and the number of inserted elements.
    79      */
    80 
    81     int find(T a)
    82     {
    83       int comp0 = map[a];
    84       if (comp0 < 0) {
    85 	return insert(a);
    86       }
    87       int comp = comp0;
    88       int next;
    89       while ( (next = data[comp].first) != comp) {
    90 	comp = next;
    91       }
    92       while ( (next = data[comp0].first) != comp) {
    93 	data[comp0].first = comp;
    94 	comp0 = next;
    95       }
    96 
    97       return comp;
    98     }
    99 
   100     /**
   101      * \brief Inserts a new element into the structure.
   102      *
   103      * This method inserts a new element into the data structure. 
   104      *
   105      * It is not required to use this method:
   106      * if the map given to the constructor was filled 
   107      * with -1's then it is called automatically
   108      * on the first \ref find or \ref join.
   109      *
   110      * The method returns the index of the new component.
   111      */
   112 
   113     int insert(T a)
   114     {
   115       int n = data.size();
   116       data.push_back(std::make_pair(n, 1));
   117       map.set(a,n);
   118       return n;
   119     }
   120 
   121     /**
   122      * \brief Joining the components of element \e a and element \e b.
   123      *
   124      * This is the \e union operation of the Union-Find structure. 
   125      * Joins the component of element \e a and component of
   126      * element \e b. If \e a and \e b are in the same component then
   127      * it returns false otherwise it returns true.
   128      */
   129 
   130     bool join(T a, T b)
   131     {
   132       int ca = find(a);
   133       int cb = find(b);
   134 
   135       if ( ca == cb ) 
   136 	return false;
   137 
   138       if ( data[ca].second > data[cb].second ) {
   139 	data[cb].first = ca;
   140 	data[ca].second += data[cb].second;
   141       }
   142       else {
   143 	data[ca].first = cb;
   144 	data[cb].second += data[ca].second;
   145       }
   146       return true;
   147     }
   148 
   149     /**
   150      * \brief Returns the size of the component of element \e a.
   151      *
   152      * Returns the size of the component of element \e a.
   153      */
   154 
   155     int size(T a)
   156     {
   157       int ca = find(a);
   158       return data[ca].second;
   159     }
   160 
   161   };
   162 
   163 
   164 
   165 
   166   /*******************************************************/
   167 
   168 
   169 #ifdef DEVELOPMENT_DOCS
   170 
   171   /**
   172    * \brief The auxiliary class for the \ref UnionFindEnum class.
   173    *
   174    * In the \ref UnionFindEnum class all components are represented as
   175    * a std::list. 
   176    * Items of these lists are UnionFindEnumItem structures.
   177    *
   178    * The class has four fields:
   179    *  - T me - the actual element 
   180    *  - IIter parent - the parent of the element in the union-find structure
   181    *  - int size - the size of the component of the element. 
   182    *            Only valid if the element
   183    *            is the leader of the component.
   184    *  - CIter my_class - pointer into the list of components 
   185    *            pointing to the component of the element.
   186    *            Only valid if the element is the leader of the component.
   187    */
   188 
   189 #endif
   190 
   191   template <typename T>
   192   struct UnionFindEnumItem {
   193 
   194     typedef std::list<UnionFindEnumItem> ItemList;
   195     typedef std::list<ItemList> ClassList;
   196     typedef typename ItemList::iterator IIter;
   197     typedef typename ClassList::iterator CIter;
   198 
   199     T me;
   200     IIter parent;
   201     int size;
   202     CIter my_class;
   203 
   204     UnionFindEnumItem() {}
   205     UnionFindEnumItem(const T &_me, CIter _my_class): 
   206       me(_me), size(1), my_class(_my_class) {}
   207   };
   208 
   209 
   210   /**
   211    * \brief A \e Union-Find data structure implementation which
   212    * is able to enumerate the components.
   213    *
   214    * The class implements a \e Union-Find data structure
   215    * which is able to enumerate the components and the items in
   216    * a component. If you don't need this feature then perhaps it's
   217    * better to use the \ref UnionFind class which is more efficient.
   218    *
   219    * The union operation uses rank heuristic, while
   220    * the find operation uses path compression.
   221    *
   222    * \pre You
   223    * need to add all the elements by the \ref insert() method.
   224    */
   225 
   226 
   227   template <typename T, template <typename Item> class Map>
   228   class UnionFindEnum {
   229 
   230     typedef std::list<UnionFindEnumItem<T> > ItemList;
   231     typedef std::list<ItemList> ClassList;
   232     typedef typename ItemList::iterator IIter;
   233     typedef typename ItemList::const_iterator IcIter;
   234     typedef typename ClassList::iterator CIter;
   235     typedef typename ClassList::const_iterator CcIter;
   236 
   237   public:
   238     typedef T ElementType;
   239     typedef UnionFindEnumItem<T> ItemType;
   240     typedef Map< IIter > MapType;
   241 
   242   private:
   243     MapType& m;
   244     ClassList classes;
   245 
   246     IIter _find(IIter a) const {
   247       IIter comp = a;
   248       IIter next;
   249       while( (next = comp->parent) != comp ) {
   250 	comp = next;
   251       }
   252 
   253       IIter comp1 = a;
   254       while( (next = comp1->parent) != comp ) {
   255 	comp1->parent = comp->parent;
   256 	comp1 = next;
   257       }
   258       return comp;
   259     }
   260 
   261   public:
   262     UnionFindEnum(MapType& _m) : m(_m) {}
   263 
   264 
   265     /**
   266      * \brief Inserts the given element into a new component.
   267      *
   268      * This method creates a new component consisting only of the
   269      * given element.
   270      */
   271 
   272     void insert(const T &a)
   273     {
   274 
   275 
   276       classes.push_back(ItemList());
   277       CIter aclass = classes.end();
   278       --aclass;
   279 
   280       ItemList &alist = *aclass;
   281       alist.push_back(ItemType(a, aclass));
   282       IIter ai = alist.begin();
   283 
   284       ai->parent = ai;
   285       m.set(a, ai);
   286 
   287     }
   288 
   289     /**
   290      * \brief Inserts the given element into the component of the others.
   291      *
   292      * This methods inserts the element \e a into the component of the
   293      * element \e comp. 
   294      */
   295 
   296     void insert(const T &a, const T &comp) {
   297       
   298       IIter clit = _find(m[comp]);
   299       ItemList &c = *clit->my_class;
   300       c.push_back(ItemType(a,0));
   301       IIter ai = c.end();
   302       --ai;
   303       ai->parent = clit;
   304       m.set(a, ai);
   305       ++clit->size;
   306     }
   307 
   308 
   309     /**
   310      * \brief Finds the leader of the component of the given element.
   311      *
   312      * The method returns the leader of the component of the given element.
   313      */
   314 
   315     T find(const T &a) const {
   316       return _find(m[a])->me;
   317     }
   318 
   319 
   320     /**
   321      * \brief Joining the component of element \e a and element \e b.
   322      *
   323      * This is the \e union operation of the Union-Find structure. 
   324      * Joins the component of element \e a and component of
   325      * element \e b. If \e a and \e b are in the same component then
   326      * returns false else returns true.
   327      */
   328 
   329     bool join(T a, T b) {
   330 
   331       IIter ca = _find(m[a]);
   332       IIter cb = _find(m[b]);
   333 
   334       if ( ca == cb ) {
   335 	return false;
   336       }
   337 
   338       if ( ca->size > cb->size ) {
   339 
   340 	cb->parent = ca->parent;
   341 	ca->size += cb->size;
   342 	
   343 	ItemList &alist = *ca->my_class;
   344 	alist.splice(alist.end(),*cb->my_class);
   345 
   346 	classes.erase(cb->my_class);
   347 	cb->my_class = 0;
   348       }
   349       else {
   350 
   351 	ca->parent = cb->parent;
   352 	cb->size += ca->size;
   353 	
   354 	ItemList &blist = *cb->my_class;
   355 	blist.splice(blist.end(),*ca->my_class);
   356 
   357 	classes.erase(ca->my_class);
   358 	ca->my_class = 0;
   359       }
   360 
   361       return true;
   362     }
   363 
   364 
   365     /**
   366      * \brief Returns the size of the component of element \e a.
   367      *
   368      * Returns the size of the component of element \e a.
   369      */
   370 
   371     int size(const T &a) const {
   372       return _find(m[a])->size;
   373     }
   374 
   375 
   376     /**
   377      * \brief Splits up the component of the element. 
   378      *
   379      * Splitting the component of the element into sigleton
   380      * components (component of size one).
   381      */
   382 
   383     void split(const T &a) {
   384 
   385       IIter ca = _find(m[a]);
   386  
   387       if ( ca->size == 1 )
   388 	return;
   389       
   390       CIter aclass = ca->my_class;
   391 
   392       for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
   393 	classes.push_back(ItemList());
   394 	CIter nl = --classes.end();
   395 	nl->splice(nl->end(), *aclass, curr);
   396 
   397 	curr->size=1;
   398 	curr->parent=curr;
   399 	curr->my_class = nl;
   400       }
   401 
   402       ca->size=1;
   403       return;
   404     }
   405 
   406 
   407     /**
   408      * \brief Sets the given element to the leader element of its component.
   409      *
   410      * Sets the given element to the leader element of its component.
   411      */
   412 
   413     void makeRep(const T &a) {
   414 
   415       IIter ia = m[a];
   416       IIter la = _find(ia);
   417       if (la == ia) return;
   418 
   419       ia->my_class = la->my_class;
   420       la->my_class = 0;
   421 
   422       ia->size = la->size;
   423 
   424       CIter l = ia->my_class;
   425       l->splice(l->begin(),*l,ia);
   426 
   427       ia->parent = ia;
   428       la->parent = ia;
   429     }
   430 
   431     /**
   432      * \brief Moves the given element to an other component.
   433      *
   434      * This method moves the element \e a from its component
   435      * to the component of \e comp.
   436      * If \e a and \e comp are in the same component then
   437      * it returns false otherwise it returns true.
   438      */
   439 
   440     bool move(const T &a, const T &comp) {
   441 
   442       IIter ai = m[a];
   443       IIter lai = _find(ai);
   444       IIter clit = _find(m[comp]);
   445 
   446       if (lai == clit)
   447 	return false;
   448 
   449       ItemList &cl = *clit->my_class,
   450 	&al = *lai->my_class;
   451 
   452       bool is_leader = (lai == ai);
   453       bool singleton = false;
   454 
   455       if (is_leader) {
   456 	++lai;
   457       }
   458 
   459       cl.splice(cl.end(), al, ai);
   460 
   461       if (is_leader) {
   462 	if (ai->size == 1) {
   463 	  classes.erase(ai->my_class);
   464 	  singleton = true;
   465 	}
   466 	else {
   467 	  lai->size = ai->size; 
   468 	  lai->my_class = ai->my_class;	
   469 	}
   470       }
   471       if (!singleton) {
   472 	for (IIter i = lai; i != al.end(); ++i)
   473 	  i->parent = lai;
   474 	--lai->size;
   475       }
   476 
   477       ai->parent = clit;
   478       ai->my_class = 0;
   479       ++clit->size;
   480 
   481       return true;
   482     }
   483 
   484 
   485     /**
   486      * \brief Removes the given element from the structure.
   487      *
   488      * Removes the given element from the structure.
   489      *
   490      * Removes the element from its component and if the component becomes
   491      * empty then removes that component from the component list.
   492      */
   493     void erase(const T &a) {
   494 
   495       IIter ma = m[a];
   496       if (ma == 0) return;
   497 
   498       IIter la = _find(ma);
   499       if (la == ma) {
   500 	if (ma -> size == 1){
   501 	  classes.erase(ma->my_class);
   502 	  m.set(a,0);
   503 	  return;
   504 	}
   505 	++la;
   506 	la->size = ma->size; 
   507 	la->my_class = ma->my_class;	
   508       }
   509 
   510       for (IIter i = la; i != la->my_class->end(); ++i) {
   511 	i->parent = la;
   512       }
   513 
   514       la->size--;
   515       la->my_class->erase(ma);
   516       m.set(a,0);
   517     }
   518 
   519     /**
   520      * \brief Removes the component of the given element from the structure.
   521      *
   522      * Removes the component of the given element from the structure.
   523      */
   524 
   525     void eraseClass(const T &a) {
   526       IIter ma = m[a];
   527       if (ma == 0) return;
   528 #     ifdef DEBUG
   529       CIter c = _find(ma)->my_class;
   530       for (IIter i=c->begin(); i!=c->end(); ++i)
   531 	m.set(i->me, 0);
   532 #     endif
   533       classes.erase(_find(ma)->my_class);
   534     }
   535 
   536 
   537     class ClassIt {
   538       friend class UnionFindEnum;
   539 
   540       CcIter i;
   541     public:
   542       ClassIt(Invalid): i(0) {}
   543       ClassIt() {}
   544       
   545       operator const T& () const { 
   546 	ItemList const &ll = *i;
   547 	return (ll.begin())->me; }
   548       bool operator == (ClassIt it) const {
   549 	return (i == it.i);
   550       }
   551       bool operator != (ClassIt it) const {
   552 	return (i != it.i);
   553       }
   554       bool operator < (ClassIt it) const {
   555 	return (i < it.i);
   556       }
   557 
   558       bool valid() const { return i != 0; }
   559     private:
   560       void first(const ClassList &l) { i = l.begin(); validate(l); }
   561       void next(const ClassList &l) {
   562 	++i; 
   563 	validate(l);
   564       }
   565       void validate(const ClassList &l) {
   566 	if ( i == l.end() ) 
   567 	  i = 0;
   568       }
   569     };
   570 
   571     /**
   572      * \brief Sets the iterator to point to the first component.
   573      * 
   574      * Sets the iterator to point to the first component.
   575      *
   576      * With the \ref first, \ref valid and \ref next methods you can
   577      * iterate through the components. For example:
   578      * \code
   579      * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
   580      * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
   581      * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
   582      *  for (U.first(iter); U.valid(iter); U.next(iter)) {
   583      *    // iter is convertible to Graph::Node
   584      *    cout << iter << endl;
   585      *  }
   586      * \endcode
   587      */
   588 
   589     ClassIt& first(ClassIt& it) const {
   590       it.first(classes);
   591       return it;
   592     }
   593 
   594     /**
   595      * \brief Returns whether the iterator is valid.
   596      *
   597      * Returns whether the iterator is valid.
   598      *
   599      * With the \ref first, \ref valid and \ref next methods you can
   600      * iterate through the components. See the example here: \ref first.
   601      */
   602 
   603     bool valid(ClassIt const &it) const {
   604       return it.valid(); 
   605     }
   606 
   607     /**
   608      * \brief Steps the iterator to the next component. 
   609      *
   610      * Steps the iterator to the next component.
   611      *
   612      * With the \ref first, \ref valid and \ref next methods you can
   613      * iterate through the components. See the example here: \ref first.
   614      */
   615 
   616     ClassIt& next(ClassIt& it) const {
   617       it.next(classes);
   618       return it;
   619     }
   620 
   621 
   622     class ItemIt {
   623       friend class UnionFindEnum;
   624 
   625       IcIter i;
   626       const ItemList *l;
   627     public:
   628       ItemIt(Invalid): i(0) {}
   629       ItemIt() {}
   630       
   631       operator const T& () const { return i->me; }
   632       bool operator == (ItemIt it) const {
   633 	return (i == it.i);
   634       }
   635       bool operator != (ItemIt it) const {
   636 	return (i != it.i);
   637       }
   638       bool operator < (ItemIt it) const {
   639 	return (i < it.i);
   640       }
   641 
   642       bool valid() const { return i != 0; }
   643     private:
   644       void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
   645       void next() {
   646 	++i; 
   647 	validate();
   648       }
   649       void validate() {
   650 	if ( i == l->end() ) 
   651 	  i = 0;
   652       }
   653     };
   654 
   655 
   656 
   657     /**
   658      * \brief Sets the iterator to point to the first element of the component.
   659      * 
   660      * \anchor first2 
   661      * Sets the iterator to point to the first element of the component.
   662      *
   663      * With the \ref first2 "first", \ref valid2 "valid" 
   664      * and \ref next2 "next" methods you can
   665      * iterate through the elements of a component. For example
   666      * (iterating through the component of the node \e node):
   667      * \code
   668      * Graph::Node node = ...;
   669      * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
   670      * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
   671      * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
   672      *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
   673      *     // iiter is convertible to Graph::Node
   674      *     cout << iiter << endl;
   675      *   }
   676      * \endcode
   677      */
   678     
   679     ItemIt& first(ItemIt& it, const T& a) const {
   680       it.first( * _find(m[a])->my_class );
   681       return it;
   682     }
   683 
   684     /**
   685      * \brief Returns whether the iterator is valid.
   686      *
   687      * \anchor valid2
   688      * Returns whether the iterator is valid.
   689      *
   690      * With the \ref first2 "first", \ref valid2 "valid" 
   691      * and \ref next2 "next" methods you can
   692      * iterate through the elements of a component.
   693      * See the example here: \ref first2 "first".
   694      */
   695 
   696     bool valid(ItemIt const &it) const {
   697       return it.valid(); 
   698     }
   699 
   700     /**
   701      * \brief Steps the iterator to the next component. 
   702      *
   703      * \anchor next2
   704      * Steps the iterator to the next component.
   705      *
   706      * With the \ref first2 "first", \ref valid2 "valid" 
   707      * and \ref next2 "next" methods you can
   708      * iterate through the elements of a component.
   709      * See the example here: \ref first2 "first".
   710      */
   711 
   712     ItemIt& next(ItemIt& it) const {
   713       it.next();
   714       return it;
   715     }
   716     
   717   };
   718 
   719 
   720   //! @}
   721 
   722 } //namespace lemon
   723 
   724 #endif //LEMON_UNION_FIND_H