NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
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.
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