unionfind.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_UNION_FIND_H
00020 #define LEMON_UNION_FIND_H
00021 
00026 
00027 #include <vector>
00028 #include <list>
00029 #include <utility>
00030 #include <algorithm>
00031 
00032 #include <lemon/invalid.h>
00033 
00034 namespace lemon {
00035 
00038 
00059   template <typename T, typename TIntMap>
00060   class UnionFind {
00061     
00062   public:
00063     typedef T ElementType;
00064     typedef std::pair<int,int> PairType;
00065 
00066   private:
00067     std::vector<PairType> data;
00068     TIntMap& map;
00069 
00070   public:
00071     UnionFind(TIntMap& m) : map(m) {}
00072 
00080     int find(T a)
00081     {
00082       int comp0 = map[a];
00083       if (comp0 < 0) {
00084         return insert(a);
00085       }
00086       int comp = comp0;
00087       int next;
00088       while ( (next = data[comp].first) != comp) {
00089         comp = next;
00090       }
00091       while ( (next = data[comp0].first) != comp) {
00092         data[comp0].first = comp;
00093         comp0 = next;
00094       }
00095 
00096       return comp;
00097     }
00098 
00112     int insert(T a)
00113     {
00114       int n = data.size();
00115       data.push_back(std::make_pair(n, 1));
00116       map.set(a,n);
00117       return n;
00118     }
00119 
00129     bool join(T a, T b)
00130     {
00131       int ca = find(a);
00132       int cb = find(b);
00133 
00134       if ( ca == cb ) 
00135         return false;
00136 
00137       if ( data[ca].second > data[cb].second ) {
00138         data[cb].first = ca;
00139         data[ca].second += data[cb].second;
00140       }
00141       else {
00142         data[ca].first = cb;
00143         data[cb].second += data[ca].second;
00144       }
00145       return true;
00146     }
00147 
00154     int size(T a)
00155     {
00156       int ca = find(a);
00157       return data[ca].second;
00158     }
00159 
00160   };
00161 
00162 
00163 
00164 
00165   /*******************************************************/
00166 
00167 
00168 #ifdef DEVELOPMENT_DOCS
00169 
00188 #endif
00189 
00190   template <typename T>
00191   struct UnionFindEnumItem {
00192 
00193     typedef std::list<UnionFindEnumItem> ItemList;
00194     typedef std::list<ItemList> ClassList;
00195     typedef typename ItemList::iterator IIter;
00196     typedef typename ClassList::iterator CIter;
00197 
00198     T me;
00199     IIter parent;
00200     int size;
00201     CIter my_class;
00202 
00203     UnionFindEnumItem() {}
00204     UnionFindEnumItem(const T &_me, CIter _my_class): 
00205       me(_me), size(1), my_class(_my_class) {}
00206   };
00207 
00208 
00226   template <typename T, template <typename Item> class Map>
00227   class UnionFindEnum {
00228 
00229     typedef std::list<UnionFindEnumItem<T> > ItemList;
00230     typedef std::list<ItemList> ClassList;
00231     typedef typename ItemList::iterator IIter;
00232     typedef typename ItemList::const_iterator IcIter;
00233     typedef typename ClassList::iterator CIter;
00234     typedef typename ClassList::const_iterator CcIter;
00235 
00236   public:
00237     typedef T ElementType;
00238     typedef UnionFindEnumItem<T> ItemType;
00239     typedef Map< IIter > MapType;
00240 
00241   private:
00242     MapType& m;
00243     ClassList classes;
00244 
00245     IIter _find(IIter a) const {
00246       IIter comp = a;
00247       IIter next;
00248       while( (next = comp->parent) != comp ) {
00249         comp = next;
00250       }
00251 
00252       IIter comp1 = a;
00253       while( (next = comp1->parent) != comp ) {
00254         comp1->parent = comp->parent;
00255         comp1 = next;
00256       }
00257       return comp;
00258     }
00259 
00260   public:
00261     UnionFindEnum(MapType& _m) : m(_m) {}
00262 
00263 
00271     void insert(const T &a)
00272     {
00273 
00274 
00275       classes.push_back(ItemList());
00276       CIter aclass = classes.end();
00277       --aclass;
00278 
00279       ItemList &alist = *aclass;
00280       alist.push_back(ItemType(a, aclass));
00281       IIter ai = alist.begin();
00282 
00283       ai->parent = ai;
00284       m.set(a, ai);
00285 
00286     }
00287 
00295     void insert(const T &a, const T &comp) {
00296       
00297       IIter clit = _find(m[comp]);
00298       ItemList &c = *clit->my_class;
00299       c.push_back(ItemType(a,0));
00300       IIter ai = c.end();
00301       --ai;
00302       ai->parent = clit;
00303       m.set(a, ai);
00304       ++clit->size;
00305     }
00306 
00307 
00314     T find(const T &a) const {
00315       return _find(m[a])->me;
00316     }
00317 
00318 
00328     bool join(T a, T b) {
00329 
00330       IIter ca = _find(m[a]);
00331       IIter cb = _find(m[b]);
00332 
00333       if ( ca == cb ) {
00334         return false;
00335       }
00336 
00337       if ( ca->size > cb->size ) {
00338 
00339         cb->parent = ca->parent;
00340         ca->size += cb->size;
00341         
00342         ItemList &alist = *ca->my_class;
00343         alist.splice(alist.end(),*cb->my_class);
00344 
00345         classes.erase(cb->my_class);
00346         cb->my_class = 0;
00347       }
00348       else {
00349 
00350         ca->parent = cb->parent;
00351         cb->size += ca->size;
00352         
00353         ItemList &blist = *cb->my_class;
00354         blist.splice(blist.end(),*ca->my_class);
00355 
00356         classes.erase(ca->my_class);
00357         ca->my_class = 0;
00358       }
00359 
00360       return true;
00361     }
00362 
00363 
00370     int size(const T &a) const {
00371       return _find(m[a])->size;
00372     }
00373 
00374 
00382     void split(const T &a) {
00383 
00384       IIter ca = _find(m[a]);
00385  
00386       if ( ca->size == 1 )
00387         return;
00388       
00389       CIter aclass = ca->my_class;
00390 
00391       for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
00392         classes.push_back(ItemList());
00393         CIter nl = --classes.end();
00394         nl->splice(nl->end(), *aclass, curr);
00395 
00396         curr->size=1;
00397         curr->parent=curr;
00398         curr->my_class = nl;
00399       }
00400 
00401       ca->size=1;
00402       return;
00403     }
00404 
00405 
00412     void makeRep(const T &a) {
00413 
00414       IIter ia = m[a];
00415       IIter la = _find(ia);
00416       if (la == ia) return;
00417 
00418       ia->my_class = la->my_class;
00419       la->my_class = 0;
00420 
00421       ia->size = la->size;
00422 
00423       CIter l = ia->my_class;
00424       l->splice(l->begin(),*l,ia);
00425 
00426       ia->parent = ia;
00427       la->parent = ia;
00428     }
00429 
00439     bool move(const T &a, const T &comp) {
00440 
00441       IIter ai = m[a];
00442       IIter lai = _find(ai);
00443       IIter clit = _find(m[comp]);
00444 
00445       if (lai == clit)
00446         return false;
00447 
00448       ItemList &cl = *clit->my_class,
00449         &al = *lai->my_class;
00450 
00451       bool is_leader = (lai == ai);
00452       bool singleton = false;
00453 
00454       if (is_leader) {
00455         ++lai;
00456       }
00457 
00458       cl.splice(cl.end(), al, ai);
00459 
00460       if (is_leader) {
00461         if (ai->size == 1) {
00462           classes.erase(ai->my_class);
00463           singleton = true;
00464         }
00465         else {
00466           lai->size = ai->size; 
00467           lai->my_class = ai->my_class; 
00468         }
00469       }
00470       if (!singleton) {
00471         for (IIter i = lai; i != al.end(); ++i)
00472           i->parent = lai;
00473         --lai->size;
00474       }
00475 
00476       ai->parent = clit;
00477       ai->my_class = 0;
00478       ++clit->size;
00479 
00480       return true;
00481     }
00482 
00483 
00492     void erase(const T &a) {
00493 
00494       IIter ma = m[a];
00495       if (ma == 0) return;
00496 
00497       IIter la = _find(ma);
00498       if (la == ma) {
00499         if (ma -> size == 1){
00500           classes.erase(ma->my_class);
00501           m.set(a,0);
00502           return;
00503         }
00504         ++la;
00505         la->size = ma->size; 
00506         la->my_class = ma->my_class;    
00507       }
00508 
00509       for (IIter i = la; i != la->my_class->end(); ++i) {
00510         i->parent = la;
00511       }
00512 
00513       la->size--;
00514       la->my_class->erase(ma);
00515       m.set(a,0);
00516     }
00517 
00524     void eraseClass(const T &a) {
00525       IIter ma = m[a];
00526       if (ma == 0) return;
00527 #     ifdef DEBUG
00528       CIter c = _find(ma)->my_class;
00529       for (IIter i=c->begin(); i!=c->end(); ++i)
00530         m.set(i->me, 0);
00531 #     endif
00532       classes.erase(_find(ma)->my_class);
00533     }
00534 
00535 
00536     class ClassIt {
00537       friend class UnionFindEnum;
00538 
00539       CcIter i;
00540     public:
00541       ClassIt(Invalid): i(0) {}
00542       ClassIt() {}
00543       
00544       operator const T& () const { 
00545         ItemList const &ll = *i;
00546         return (ll.begin())->me; }
00547       bool operator == (ClassIt it) const {
00548         return (i == it.i);
00549       }
00550       bool operator != (ClassIt it) const {
00551         return (i != it.i);
00552       }
00553       bool operator < (ClassIt it) const {
00554         return (i < it.i);
00555       }
00556 
00557       bool valid() const { return i != 0; }
00558     private:
00559       void first(const ClassList &l) { i = l.begin(); validate(l); }
00560       void next(const ClassList &l) {
00561         ++i; 
00562         validate(l);
00563       }
00564       void validate(const ClassList &l) {
00565         if ( i == l.end() ) 
00566           i = 0;
00567       }
00568     };
00569 
00588     ClassIt& first(ClassIt& it) const {
00589       it.first(classes);
00590       return it;
00591     }
00592 
00602     bool valid(ClassIt const &it) const {
00603       return it.valid(); 
00604     }
00605 
00615     ClassIt& next(ClassIt& it) const {
00616       it.next(classes);
00617       return it;
00618     }
00619 
00620 
00621     class ItemIt {
00622       friend class UnionFindEnum;
00623 
00624       IcIter i;
00625       const ItemList *l;
00626     public:
00627       ItemIt(Invalid): i(0) {}
00628       ItemIt() {}
00629       
00630       operator const T& () const { return i->me; }
00631       bool operator == (ItemIt it) const {
00632         return (i == it.i);
00633       }
00634       bool operator != (ItemIt it) const {
00635         return (i != it.i);
00636       }
00637       bool operator < (ItemIt it) const {
00638         return (i < it.i);
00639       }
00640 
00641       bool valid() const { return i != 0; }
00642     private:
00643       void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
00644       void next() {
00645         ++i; 
00646         validate();
00647       }
00648       void validate() {
00649         if ( i == l->end() ) 
00650           i = 0;
00651       }
00652     };
00653 
00654 
00655 
00678     ItemIt& first(ItemIt& it, const T& a) const {
00679       it.first( * _find(m[a])->my_class );
00680       return it;
00681     }
00682 
00695     bool valid(ItemIt const &it) const {
00696       return it.valid(); 
00697     }
00698 
00711     ItemIt& next(ItemIt& it) const {
00712       it.next();
00713       return it;
00714     }
00715     
00716   };
00717 
00718 
00720 
00721 } //namespace lemon
00722 
00723 #endif //LEMON_UNION_FIND_H

Generated on Fri Feb 3 18:39:51 2006 for LEMON by  doxygen 1.4.6