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