00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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 }
00722
00723 #endif //LEMON_UNION_FIND_H