Lemon Graph Format uses label instead of id named map.
2 * lemon/unionfind.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 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.
30 #include <lemon/invalid.h>
34 //! \addtogroup auxdat
38 * \brief A \e Union-Find data structure implementation
40 * The class implements the \e Union-Find data structure.
41 * The union operation uses rank heuristic, while
42 * the find operation uses path compression.
43 * This is a very simple but efficient implementation, providing
44 * only four methods: join (union), find, insert and size.
45 * For more features see the \ref UnionFindEnum class.
47 * It is primarily used in Kruskal algorithm for finding minimal
48 * cost spanning tree in a graph.
51 * \pre The elements are automatically added only if the map
52 * given to the constructor was filled with -1's. Otherwise you
53 * need to add all the elements by the \ref insert() method.
54 * \bug It is not clear what the constructor parameter is used for.
57 template <typename T, typename TIntMap>
61 typedef T ElementType;
62 typedef std::pair<int,int> PairType;
65 std::vector<PairType> data;
69 UnionFind(TIntMap& m) : map(m) {}
72 * \brief Returns the index of the element's component.
74 * The method returns the index of the element's component.
75 * This is an integer between zero and the number of inserted elements.
86 while ( (next = data[comp].first) != comp) {
89 while ( (next = data[comp0].first) != comp) {
90 data[comp0].first = comp;
98 * \brief Inserts a new element into the structure.
100 * This method inserts a new element into the data structure.
102 * It is not required to use this method:
103 * if the map given to the constructor was filled
104 * with -1's then it is called automatically
105 * on the first \ref find or \ref join.
107 * The method returns the index of the new component.
113 data.push_back(std::make_pair(n, 1));
119 * \brief Joining the components of element \e a and element \e b.
121 * This is the \e union operation of the Union-Find structure.
122 * Joins the component of element \e a and component of
123 * element \e b. If \e a and \e b are in the same component then
124 * it returns false otherwise it returns true.
135 if ( data[ca].second > data[cb].second ) {
137 data[ca].second += data[cb].second;
141 data[cb].second += data[ca].second;
147 * \brief Returns the size of the component of element \e a.
149 * Returns the size of the component of element \e a.
155 return data[ca].second;
163 /*******************************************************/
166 #ifdef DEVELOPMENT_DOCS
169 * \brief The auxiliary class for the \ref UnionFindEnum class.
171 * In the \ref UnionFindEnum class all components are represented as
173 * Items of these lists are UnionFindEnumItem structures.
175 * The class has four fields:
176 * - T me - the actual element
177 * - IIter parent - the parent of the element in the union-find structure
178 * - int size - the size of the component of the element.
179 * Only valid if the element
180 * is the leader of the component.
181 * - CIter my_class - pointer into the list of components
182 * pointing to the component of the element.
183 * Only valid if the element is the leader of the component.
188 template <typename T>
189 struct UnionFindEnumItem {
191 typedef std::list<UnionFindEnumItem> ItemList;
192 typedef std::list<ItemList> ClassList;
193 typedef typename ItemList::iterator IIter;
194 typedef typename ClassList::iterator CIter;
201 UnionFindEnumItem() {}
202 UnionFindEnumItem(const T &_me, CIter _my_class):
203 me(_me), size(1), my_class(_my_class) {}
208 * \brief A \e Union-Find data structure implementation which
209 * is able to enumerate the components.
211 * The class implements a \e Union-Find data structure
212 * which is able to enumerate the components and the items in
213 * a component. If you don't need this feature then perhaps it's
214 * better to use the \ref UnionFind class which is more efficient.
216 * The union operation uses rank heuristic, while
217 * the find operation uses path compression.
220 * need to add all the elements by the \ref insert() method.
224 template <typename T, template <typename Item> class Map>
225 class UnionFindEnum {
227 typedef std::list<UnionFindEnumItem<T> > ItemList;
228 typedef std::list<ItemList> ClassList;
229 typedef typename ItemList::iterator IIter;
230 typedef typename ItemList::const_iterator IcIter;
231 typedef typename ClassList::iterator CIter;
232 typedef typename ClassList::const_iterator CcIter;
235 typedef T ElementType;
236 typedef UnionFindEnumItem<T> ItemType;
237 typedef Map< IIter > MapType;
243 IIter _find(IIter a) const {
246 while( (next = comp->parent) != comp ) {
251 while( (next = comp1->parent) != comp ) {
252 comp1->parent = comp->parent;
259 UnionFindEnum(MapType& _m) : m(_m) {}
263 * \brief Inserts the given element into a new component.
265 * This method creates a new component consisting only of the
269 void insert(const T &a)
273 classes.push_back(ItemList());
274 CIter aclass = classes.end();
277 ItemList &alist = *aclass;
278 alist.push_back(ItemType(a, aclass));
279 IIter ai = alist.begin();
287 * \brief Inserts the given element into the component of the others.
289 * This methods inserts the element \e a into the component of the
293 void insert(const T &a, const T &comp) {
295 IIter clit = _find(m[comp]);
296 ItemList &c = *clit->my_class;
297 c.push_back(ItemType(a,0));
307 * \brief Finds the leader of the component of the given element.
309 * The method returns the leader of the component of the given element.
312 T find(const T &a) const {
313 return _find(m[a])->me;
318 * \brief Joining the component of element \e a and element \e b.
320 * This is the \e union operation of the Union-Find structure.
321 * Joins the component of element \e a and component of
322 * element \e b. If \e a and \e b are in the same component then
323 * returns false else returns true.
326 bool join(T a, T b) {
328 IIter ca = _find(m[a]);
329 IIter cb = _find(m[b]);
335 if ( ca->size > cb->size ) {
337 cb->parent = ca->parent;
338 ca->size += cb->size;
340 ItemList &alist = *ca->my_class;
341 alist.splice(alist.end(),*cb->my_class);
343 classes.erase(cb->my_class);
348 ca->parent = cb->parent;
349 cb->size += ca->size;
351 ItemList &blist = *cb->my_class;
352 blist.splice(blist.end(),*ca->my_class);
354 classes.erase(ca->my_class);
363 * \brief Returns the size of the component of element \e a.
365 * Returns the size of the component of element \e a.
368 int size(const T &a) const {
369 return _find(m[a])->size;
374 * \brief Splits up the component of the element.
376 * Splitting the component of the element into sigleton
377 * components (component of size one).
380 void split(const T &a) {
382 IIter ca = _find(m[a]);
387 CIter aclass = ca->my_class;
389 for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
390 classes.push_back(ItemList());
391 CIter nl = --classes.end();
392 nl->splice(nl->end(), *aclass, curr);
405 * \brief Sets the given element to the leader element of its component.
407 * Sets the given element to the leader element of its component.
410 void makeRep(const T &a) {
413 IIter la = _find(ia);
414 if (la == ia) return;
416 ia->my_class = la->my_class;
421 CIter l = ia->my_class;
422 l->splice(l->begin(),*l,ia);
429 * \brief Moves the given element to an other component.
431 * This method moves the element \e a from its component
432 * to the component of \e comp.
433 * If \e a and \e comp are in the same component then
434 * it returns false otherwise it returns true.
437 bool move(const T &a, const T &comp) {
440 IIter lai = _find(ai);
441 IIter clit = _find(m[comp]);
446 ItemList &cl = *clit->my_class,
447 &al = *lai->my_class;
449 bool is_leader = (lai == ai);
450 bool singleton = false;
456 cl.splice(cl.end(), al, ai);
460 classes.erase(ai->my_class);
464 lai->size = ai->size;
465 lai->my_class = ai->my_class;
469 for (IIter i = lai; i != al.end(); ++i)
483 * \brief Removes the given element from the structure.
485 * 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 void erase(const T &a) {
495 IIter la = _find(ma);
497 if (ma -> size == 1){
498 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);
517 * \brief Removes the component of the given element from the structure.
519 * Removes the component of the given element from the structure.
522 void eraseClass(const T &a) {
526 CIter c = _find(ma)->my_class;
527 for (IIter i=c->begin(); i!=c->end(); ++i)
530 classes.erase(_find(ma)->my_class);
535 friend class UnionFindEnum;
539 ClassIt(Invalid): i(0) {}
542 operator const T& () const {
543 ItemList const &ll = *i;
544 return (ll.begin())->me; }
545 bool operator == (ClassIt it) const {
548 bool operator != (ClassIt it) const {
551 bool operator < (ClassIt it) const {
555 bool valid() const { return i != 0; }
557 void first(const ClassList &l) { i = l.begin(); validate(l); }
558 void next(const ClassList &l) {
562 void validate(const ClassList &l) {
569 * \brief Sets the iterator to point to the first component.
571 * Sets the iterator to point to the first component.
573 * With the \ref first, \ref valid and \ref next methods you can
574 * iterate through the components. For example:
576 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
577 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
578 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
579 * for (U.first(iter); U.valid(iter); U.next(iter)) {
580 * // iter is convertible to Graph::Node
581 * cout << iter << endl;
586 ClassIt& first(ClassIt& it) const {
592 * \brief Returns whether the iterator is valid.
594 * Returns whether the iterator is valid.
596 * With the \ref first, \ref valid and \ref next methods you can
597 * iterate through the components. See the example here: \ref first.
600 bool valid(ClassIt const &it) const {
605 * \brief Steps the iterator to the next component.
607 * Steps the iterator to the next component.
609 * With the \ref first, \ref valid and \ref next methods you can
610 * iterate through the components. See the example here: \ref first.
613 ClassIt& next(ClassIt& it) const {
620 friend class UnionFindEnum;
625 ItemIt(Invalid): i(0) {}
628 operator const T& () const { return i->me; }
629 bool operator == (ItemIt it) const {
632 bool operator != (ItemIt it) const {
635 bool operator < (ItemIt it) const {
639 bool valid() const { return i != 0; }
641 void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
655 * \brief Sets the iterator to point to the first element of the component.
658 * Sets the iterator to point to the first element of the component.
660 * With the \ref first2 "first", \ref valid2 "valid"
661 * and \ref next2 "next" methods you can
662 * iterate through the elements of a component. For example
663 * (iterating through the component of the node \e node):
665 * Graph::Node node = ...;
666 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
667 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
668 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
669 * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
670 * // iiter is convertible to Graph::Node
671 * cout << iiter << endl;
676 ItemIt& first(ItemIt& it, const T& a) const {
677 it.first( * _find(m[a])->my_class );
682 * \brief Returns whether the iterator is valid.
685 * Returns whether the iterator is valid.
687 * With the \ref first2 "first", \ref valid2 "valid"
688 * and \ref next2 "next" methods you can
689 * iterate through the elements of a component.
690 * See the example here: \ref first2 "first".
693 bool valid(ItemIt const &it) const {
698 * \brief Steps the iterator to the next component.
701 * Steps the iterator to the next component.
703 * With the \ref first2 "first", \ref valid2 "valid"
704 * and \ref next2 "next" methods you can
705 * iterate through the elements of a component.
706 * See the example here: \ref first2 "first".
709 ItemIt& next(ItemIt& it) const {
721 #endif //LEMON_UNION_FIND_H