... and fix another one.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_UNION_FIND_H
20 #define LEMON_UNION_FIND_H
24 //!\brief Union-Find data structures.
32 #include <lemon/bits/invalid.h>
36 //! \addtogroup auxdat
40 * \brief A \e Union-Find data structure implementation
42 * The class implements the \e Union-Find data structure.
43 * The union operation uses rank heuristic, while
44 * the find operation uses path compression.
45 * This is a very simple but efficient implementation, providing
46 * only four methods: join (union), find, insert and size.
47 * For more features see the \ref UnionFindEnum class.
49 * It is primarily used in Kruskal algorithm for finding minimal
50 * cost spanning tree in a graph.
53 * \pre The elements are automatically added only if the map
54 * given to the constructor was filled with -1's. Otherwise you
55 * need to add all the elements by the \ref insert() method.
56 * \bug It is not clear what the constructor parameter is used for.
59 template <typename T, typename TIntMap>
63 typedef T ElementType;
64 typedef std::pair<int,int> PairType;
67 std::vector<PairType> data;
71 UnionFind(TIntMap& m) : map(m) {}
74 * \brief Returns the index of the element's component.
76 * The method returns the index of the element's component.
77 * This is an integer between zero and the number of inserted elements.
88 while ( (next = data[comp].first) != comp) {
91 while ( (next = data[comp0].first) != comp) {
92 data[comp0].first = comp;
100 * \brief Inserts a new element into the structure.
102 * This method inserts a new element into the data structure.
104 * It is not required to use this method:
105 * if the map given to the constructor was filled
106 * with -1's then it is called automatically
107 * on the first \ref find or \ref join.
109 * The method returns the index of the new component.
115 data.push_back(std::make_pair(n, 1));
121 * \brief Joining the components of element \e a and element \e b.
123 * This is the \e union operation of the Union-Find structure.
124 * Joins the component of element \e a and component of
125 * element \e b. If \e a and \e b are in the same component then
126 * it returns false otherwise it returns true.
137 if ( data[ca].second > data[cb].second ) {
139 data[ca].second += data[cb].second;
143 data[cb].second += data[ca].second;
149 * \brief Returns the size of the component of element \e a.
151 * Returns the size of the component of element \e a.
157 return data[ca].second;
165 /*******************************************************/
168 #ifdef DEVELOPMENT_DOCS
171 * \brief The auxiliary class for the \ref UnionFindEnum class.
173 * In the \ref UnionFindEnum class all components are represented as
175 * Items of these lists are UnionFindEnumItem structures.
177 * The class has four fields:
178 * - T me - the actual element
179 * - IIter parent - the parent of the element in the union-find structure
180 * - int size - the size of the component of the element.
181 * Only valid if the element
182 * is the leader of the component.
183 * - CIter my_class - pointer into the list of components
184 * pointing to the component of the element.
185 * Only valid if the element is the leader of the component.
190 template <typename T>
191 struct UnionFindEnumItem {
193 typedef std::list<UnionFindEnumItem> ItemList;
194 typedef std::list<ItemList> ClassList;
195 typedef typename ItemList::iterator IIter;
196 typedef typename ClassList::iterator CIter;
203 UnionFindEnumItem() {}
204 UnionFindEnumItem(const T &_me, CIter _my_class):
205 me(_me), size(1), my_class(_my_class) {}
210 * \brief A \e Union-Find data structure implementation which
211 * is able to enumerate the components.
213 * The class implements a \e Union-Find data structure
214 * which is able to enumerate the components and the items in
215 * a component. If you don't need this feature then perhaps it's
216 * better to use the \ref UnionFind class which is more efficient.
218 * The union operation uses rank heuristic, while
219 * the find operation uses path compression.
222 * need to add all the elements by the \ref insert() method.
226 template <typename T, template <typename Item> class Map>
227 class UnionFindEnum {
229 typedef std::list<UnionFindEnumItem<T> > ItemList;
230 typedef std::list<ItemList> ClassList;
231 typedef typename ItemList::iterator IIter;
232 typedef typename ItemList::const_iterator IcIter;
233 typedef typename ClassList::iterator CIter;
234 typedef typename ClassList::const_iterator CcIter;
237 typedef T ElementType;
238 typedef UnionFindEnumItem<T> ItemType;
239 typedef Map< IIter > MapType;
245 IIter _find(IIter a) const {
248 while( (next = comp->parent) != comp ) {
253 while( (next = comp1->parent) != comp ) {
254 comp1->parent = comp->parent;
260 const ItemList& classOf(const T &a) const {
261 return *_find(m[a])->my_class;
265 UnionFindEnum(MapType& _m) : m(_m) {}
269 * \brief Inserts the given element into a new component.
271 * This method creates a new component consisting only of the
275 void insert(const T &a)
279 classes.push_back(ItemList());
280 CIter aclass = classes.end();
283 ItemList &alist = *aclass;
284 alist.push_back(ItemType(a, aclass));
285 IIter ai = alist.begin();
293 * \brief Inserts the given element into the component of the others.
295 * This methods inserts the element \e a into the component of the
299 void insert(const T &a, const T &comp) {
301 IIter clit = _find(m[comp]);
302 ItemList &c = *clit->my_class;
303 c.push_back(ItemType(a,CIter()));
313 * \brief Finds the leader of the component of the given element.
315 * The method returns the leader of the component of the given element.
318 T find(const T &a) const {
319 return _find(m[a])->me;
324 * \brief Joining the component of element \e a and element \e b.
326 * This is the \e union operation of the Union-Find structure.
327 * Joins the component of element \e a and component of
328 * element \e b. If \e a and \e b are in the same component then
329 * returns false else returns true.
332 bool join(T a, T b) {
334 IIter ca = _find(m[a]);
335 IIter cb = _find(m[b]);
341 if ( ca->size > cb->size ) {
343 cb->parent = ca->parent;
344 ca->size += cb->size;
346 ItemList &alist = *ca->my_class;
347 alist.splice(alist.end(),*cb->my_class);
349 classes.erase(cb->my_class);
353 ca->parent = cb->parent;
354 cb->size += ca->size;
356 ItemList &blist = *cb->my_class;
357 blist.splice(blist.end(),*ca->my_class);
359 classes.erase(ca->my_class);
367 * \brief Returns the size of the component of element \e a.
369 * Returns the size of the component of element \e a.
372 int size(const T &a) const {
373 return _find(m[a])->size;
378 * \brief Splits up the component of the element.
380 * Splitting the component of the element into sigleton
381 * components (component of size one).
384 void split(const T &a) {
386 IIter ca = _find(m[a]);
391 CIter aclass = ca->my_class;
393 for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
394 classes.push_back(ItemList());
395 CIter nl = --classes.end();
396 nl->splice(nl->end(), *aclass, curr);
409 * \brief Sets the given element to the leader element of its component.
411 * Sets the given element to the leader element of its component.
414 void makeRep(const T &a) {
417 IIter la = _find(ia);
418 if (la == ia) return;
420 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 another 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)
485 * \brief Removes the given element from the structure.
487 * Removes the element from its component and if the component becomes
488 * empty then removes that component from the component list.
490 * It is an error to remove an element which is not in the structure.
492 void erase(const T &a) {
496 IIter la = _find(ma);
498 if (ma -> size == 1){
499 classes.erase(ma->my_class);
504 la->my_class = ma->my_class;
507 for (IIter i = la; i != la->my_class->end(); ++i) {
512 la->my_class->erase(ma);
516 * \brief Removes the component of the given element from the structure.
518 * Removes the component of the given element from the structure.
520 * It is an error to give an element which is not in the structure.
523 void eraseClass(const T &a) {
525 classes.erase(_find(ma)->my_class);
530 friend class UnionFindEnum;
536 ClassIt(Invalid): l(0) {}
538 ClassIt(UnionFindEnum const &ufe) {
543 operator const T& () const {
544 ItemList const &ll = *i;
545 return (ll.begin())->me;
547 bool operator == (ClassIt const &it) const {
548 return (l==it.l && i==it.i) || (!valid() && !it.valid());
550 bool operator != (ClassIt const &it) const {
551 return !(*this == it);
553 bool operator < (ClassIt const &it) const {
557 bool operator==(Invalid) const {
560 bool operator!=(Invalid) const {
564 ClassIt& operator++() {
570 bool valid() const { return l!=0 && i!=l->end(); }
574 * \brief Sets the iterator to point to the first component.
576 * Sets the iterator to point to the first component.
578 * With the \ref first, \ref valid and \ref next methods you can
579 * iterate through the components. For example:
581 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
582 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
583 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
584 * for (U.first(iter); U.valid(iter); U.next(iter)) {
585 * // iter is convertible to Graph::Node
586 * cout << iter << endl;
590 * \bug obsoleted, use the new LEMON iterator interface instead
593 ClassIt& first(ClassIt& it) const {
599 * \brief Returns whether the iterator is valid.
601 * Returns whether the iterator is valid.
603 * With the \ref first, \ref valid and \ref next methods you can
604 * iterate through the components. See the example here: \ref first.
606 * \bug obsoleted, use the new LEMON iterator interface instead
609 bool valid(ClassIt const &it) const {
614 * \brief Steps the iterator to the next component.
616 * Steps the iterator to the next component.
618 * With the \ref first, \ref valid and \ref next methods you can
619 * iterate through the components. See the example here: \ref first.
622 ClassIt& next(ClassIt& it) const {
628 friend class UnionFindEnum;
633 ItemIt(Invalid): l(0) {}
635 ItemIt(UnionFindEnum const &ufe, const T& a) {
640 operator const T& () const { return i->me; }
641 bool operator == (ItemIt const &it) const {
642 return (l==it.l && i==it.i) || (!valid() && !it.valid());
644 bool operator != (ItemIt const &it) const {
645 return !(*this == it);
647 bool operator < (ItemIt const &it) const {
651 bool operator==(Invalid) const {
654 bool operator!=(Invalid) const {
658 ItemIt& operator++() {
664 bool valid() const { return l!=0 && i!=l->end(); }
670 * \brief Sets the iterator to point to the first element of the component.
673 * Sets the iterator to point to the first element of the component.
675 * With the \ref first2 "first", \ref valid2 "valid"
676 * and \ref next2 "next" methods you can
677 * iterate through the elements of a component. For example
678 * (iterating through the component of the node \e node):
680 * Graph::Node node = ...;
681 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
682 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
683 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
684 * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
685 * // iiter is convertible to Graph::Node
686 * cout << iiter << endl;
690 * \bug obsoleted, use the new LEMON iterator interface instead
693 ItemIt& first(ItemIt& it, const T& a) const {
694 it = ItemIt(*this, a);
699 * \brief Returns whether the iterator is valid.
702 * Returns whether the iterator is valid.
704 * With the \ref first2 "first", \ref valid2 "valid"
705 * and \ref next2 "next" methods you can
706 * iterate through the elements of a component.
707 * See the example here: \ref first2 "first".
709 * \bug obsoleted, use the new LEMON iterator interface instead
712 bool valid(ItemIt const &it) const {
717 * \brief Steps the iterator to the next component.
720 * Steps the iterator to the next component.
722 * With the \ref first2 "first", \ref valid2 "valid"
723 * and \ref next2 "next" methods you can
724 * iterate through the elements of a component.
725 * See the example here: \ref first2 "first".
727 * \bug obsoleted, use the new LEMON iterator interface instead
730 ItemIt& next(ItemIt& it) const {
741 #endif //LEMON_UNION_FIND_H