Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

unionfind.h

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

Generated on Sat Mar 19 10:58:41 2005 for LEMON by  doxygen 1.4.1