2 * lemon/unionfind.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
17 #ifndef LEMON_UNION_FIND_H
18 #define LEMON_UNION_FIND_H
22 //!\brief Union-Find data structures.
24 //!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
25 //!fails to run (Segmentation fault).
33 #include <lemon/invalid.h>
37 //! \addtogroup auxdat
41 * \brief A \e Union-Find data structure implementation
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.
50 * It is primarily used in Kruskal algorithm for finding minimal
51 * cost spanning tree in a graph.
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.
60 template <typename T, typename TIntMap>
64 typedef T ElementType;
65 typedef std::pair<int,int> PairType;
68 std::vector<PairType> data;
72 UnionFind(TIntMap& m) : map(m) {}
75 * \brief Returns the index of the element's component.
77 * The method returns the index of the element's component.
78 * This is an integer between zero and the number of inserted elements.
89 while ( (next = data[comp].first) != comp) {
92 while ( (next = data[comp0].first) != comp) {
93 data[comp0].first = comp;
101 * \brief Inserts a new element into the structure.
103 * This method inserts a new element into the data structure.
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.
110 * The method returns the index of the new component.
116 data.push_back(std::make_pair(n, 1));
122 * \brief Joining the components of element \e a and element \e b.
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.
138 if ( data[ca].second > data[cb].second ) {
140 data[ca].second += data[cb].second;
144 data[cb].second += data[ca].second;
150 * \brief Returns the size of the component of element \e a.
152 * Returns the size of the component of element \e a.
158 return data[ca].second;
166 /*******************************************************/
169 #ifdef DEVELOPMENT_DOCS
172 * \brief The auxiliary class for the \ref UnionFindEnum class.
174 * In the \ref UnionFindEnum class all components are represented as
176 * Items of these lists are UnionFindEnumItem structures.
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.
191 template <typename T>
192 struct UnionFindEnumItem {
194 typedef std::list<UnionFindEnumItem> ItemList;
195 typedef std::list<ItemList> ClassList;
196 typedef typename ItemList::iterator IIter;
197 typedef typename ClassList::iterator CIter;
204 UnionFindEnumItem() {}
205 UnionFindEnumItem(const T &_me, CIter _my_class):
206 me(_me), size(1), my_class(_my_class) {}
211 * \brief A \e Union-Find data structure implementation which
212 * is able to enumerate the components.
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.
219 * The union operation uses rank heuristic, while
220 * the find operation uses path compression.
223 * need to add all the elements by the \ref insert() method.
227 template <typename T, template <typename Item> class Map>
228 class UnionFindEnum {
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;
238 typedef T ElementType;
239 typedef UnionFindEnumItem<T> ItemType;
240 typedef Map< IIter > MapType;
246 IIter _find(IIter a) const {
249 while( (next = comp->parent) != comp ) {
254 while( (next = comp1->parent) != comp ) {
255 comp1->parent = comp->parent;
262 UnionFindEnum(MapType& _m) : m(_m) {}
266 * \brief Inserts the given element into a new component.
268 * This method creates a new component consisting only of the
272 void insert(const T &a)
276 classes.push_back(ItemList());
277 CIter aclass = classes.end();
280 ItemList &alist = *aclass;
281 alist.push_back(ItemType(a, aclass));
282 IIter ai = alist.begin();
290 * \brief Inserts the given element into the component of the others.
292 * This methods inserts the element \e a into the component of the
296 void insert(const T &a, const T &comp) {
298 IIter clit = _find(m[comp]);
299 ItemList &c = *clit->my_class;
300 c.push_back(ItemType(a,0));
310 * \brief Finds the leader of the component of the given element.
312 * The method returns the leader of the component of the given element.
315 T find(const T &a) const {
316 return _find(m[a])->me;
321 * \brief Joining the component of element \e a and element \e b.
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.
329 bool join(T a, T b) {
331 IIter ca = _find(m[a]);
332 IIter cb = _find(m[b]);
338 if ( ca->size > cb->size ) {
340 cb->parent = ca->parent;
341 ca->size += cb->size;
343 ItemList &alist = *ca->my_class;
344 alist.splice(alist.end(),*cb->my_class);
346 classes.erase(cb->my_class);
351 ca->parent = cb->parent;
352 cb->size += ca->size;
354 ItemList &blist = *cb->my_class;
355 blist.splice(blist.end(),*ca->my_class);
357 classes.erase(ca->my_class);
366 * \brief Returns the size of the component of element \e a.
368 * Returns the size of the component of element \e a.
371 int size(const T &a) const {
372 return _find(m[a])->size;
377 * \brief Splits up the component of the element.
379 * Splitting the component of the element into sigleton
380 * components (component of size one).
383 void split(const T &a) {
385 IIter ca = _find(m[a]);
390 CIter aclass = ca->my_class;
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);
408 * \brief Sets the given element to the leader element of its component.
410 * Sets the given element to the leader element of its component.
413 void makeRep(const T &a) {
416 IIter la = _find(ia);
417 if (la == ia) return;
419 ia->my_class = la->my_class;
424 CIter l = ia->my_class;
425 l->splice(l->begin(),*l,ia);
432 * \brief Moves the given element to an other component.
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.
440 bool move(const T &a, const T &comp) {
443 IIter lai = _find(ai);
444 IIter clit = _find(m[comp]);
449 ItemList &cl = *clit->my_class,
450 &al = *lai->my_class;
452 bool is_leader = (lai == ai);
453 bool singleton = false;
459 cl.splice(cl.end(), al, ai);
463 classes.erase(ai->my_class);
467 lai->size = ai->size;
468 lai->my_class = ai->my_class;
472 for (IIter i = lai; i != al.end(); ++i)
486 * \brief Removes the given element from the structure.
488 * Removes the given element from the structure.
490 * Removes the element from its component and if the component becomes
491 * empty then removes that component from the component list.
493 void erase(const T &a) {
498 IIter la = _find(ma);
500 if (ma -> size == 1){
501 classes.erase(ma->my_class);
507 la->my_class = ma->my_class;
510 for (IIter i = la; i != la->my_class->end(); ++i) {
515 la->my_class->erase(ma);
520 * \brief Removes the component of the given element from the structure.
522 * Removes the component of the given element from the structure.
525 void eraseClass(const T &a) {
529 CIter c = _find(ma)->my_class;
530 for (IIter i=c->begin(); i!=c->end(); ++i)
533 classes.erase(_find(ma)->my_class);
538 friend class UnionFindEnum;
542 ClassIt(Invalid): i(0) {}
545 operator const T& () const {
546 ItemList const &ll = *i;
547 return (ll.begin())->me; }
548 bool operator == (ClassIt it) const {
551 bool operator != (ClassIt it) const {
554 bool operator < (ClassIt it) const {
558 bool valid() const { return i != 0; }
560 void first(const ClassList &l) { i = l.begin(); validate(l); }
561 void next(const ClassList &l) {
565 void validate(const ClassList &l) {
572 * \brief Sets the iterator to point to the first component.
574 * Sets the iterator to point to the first component.
576 * With the \ref first, \ref valid and \ref next methods you can
577 * iterate through the components. For example:
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;
589 ClassIt& first(ClassIt& it) const {
595 * \brief Returns whether the iterator is valid.
597 * Returns whether the iterator is valid.
599 * With the \ref first, \ref valid and \ref next methods you can
600 * iterate through the components. See the example here: \ref first.
603 bool valid(ClassIt const &it) const {
608 * \brief Steps the iterator to the next component.
610 * Steps the iterator to the next component.
612 * With the \ref first, \ref valid and \ref next methods you can
613 * iterate through the components. See the example here: \ref first.
616 ClassIt& next(ClassIt& it) const {
623 friend class UnionFindEnum;
628 ItemIt(Invalid): i(0) {}
631 operator const T& () const { return i->me; }
632 bool operator == (ItemIt it) const {
635 bool operator != (ItemIt it) const {
638 bool operator < (ItemIt it) const {
642 bool valid() const { return i != 0; }
644 void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
658 * \brief Sets the iterator to point to the first element of the component.
661 * Sets the iterator to point to the first element of the component.
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):
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;
679 ItemIt& first(ItemIt& it, const T& a) const {
680 it.first( * _find(m[a])->my_class );
685 * \brief Returns whether the iterator is valid.
688 * Returns whether the iterator is valid.
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".
696 bool valid(ItemIt const &it) const {
701 * \brief Steps the iterator to the next component.
704 * Steps the iterator to the next component.
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".
712 ItemIt& next(ItemIt& it) const {
724 #endif //LEMON_UNION_FIND_H