1 /* -*- C++ -*- |
|
2 * src/lemon/unionfind.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
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. |
|
10 * |
|
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 |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_UNION_FIND_H |
|
18 #define LEMON_UNION_FIND_H |
|
19 |
|
20 //!\ingroup auxdat |
|
21 //!\file |
|
22 //!\brief Union-Find data structures. |
|
23 //! |
|
24 //!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but |
|
25 //!fails to run (Segmentation fault). |
|
26 |
|
27 |
|
28 #include <vector> |
|
29 #include <list> |
|
30 #include <utility> |
|
31 #include <algorithm> |
|
32 |
|
33 #include <lemon/invalid.h> |
|
34 |
|
35 namespace lemon { |
|
36 |
|
37 //! \addtogroup auxdat |
|
38 //! @{ |
|
39 |
|
40 /** |
|
41 * \brief A \e Union-Find data structure implementation |
|
42 * |
|
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. |
|
49 * |
|
50 * It is primarily used in Kruskal algorithm for finding minimal |
|
51 * cost spanning tree in a graph. |
|
52 * \sa kruskal() |
|
53 * |
|
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. |
|
58 */ |
|
59 |
|
60 template <typename T, typename TIntMap> |
|
61 class UnionFind { |
|
62 |
|
63 public: |
|
64 typedef T ElementType; |
|
65 typedef std::pair<int,int> PairType; |
|
66 |
|
67 private: |
|
68 std::vector<PairType> data; |
|
69 TIntMap& map; |
|
70 |
|
71 public: |
|
72 UnionFind(TIntMap& m) : map(m) {} |
|
73 |
|
74 /** |
|
75 * \brief Returns the index of the element's component. |
|
76 * |
|
77 * The method returns the index of the element's component. |
|
78 * This is an integer between zero and the number of inserted elements. |
|
79 */ |
|
80 |
|
81 int find(T a) |
|
82 { |
|
83 int comp0 = map[a]; |
|
84 if (comp0 < 0) { |
|
85 return insert(a); |
|
86 } |
|
87 int comp = comp0; |
|
88 int next; |
|
89 while ( (next = data[comp].first) != comp) { |
|
90 comp = next; |
|
91 } |
|
92 while ( (next = data[comp0].first) != comp) { |
|
93 data[comp0].first = comp; |
|
94 comp0 = next; |
|
95 } |
|
96 |
|
97 return comp; |
|
98 } |
|
99 |
|
100 /** |
|
101 * \brief Inserts a new element into the structure. |
|
102 * |
|
103 * This method inserts a new element into the data structure. |
|
104 * |
|
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. |
|
109 * |
|
110 * The method returns the index of the new component. |
|
111 */ |
|
112 |
|
113 int insert(T a) |
|
114 { |
|
115 int n = data.size(); |
|
116 data.push_back(std::make_pair(n, 1)); |
|
117 map.set(a,n); |
|
118 return n; |
|
119 } |
|
120 |
|
121 /** |
|
122 * \brief Joining the components of element \e a and element \e b. |
|
123 * |
|
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. |
|
128 */ |
|
129 |
|
130 bool join(T a, T b) |
|
131 { |
|
132 int ca = find(a); |
|
133 int cb = find(b); |
|
134 |
|
135 if ( ca == cb ) |
|
136 return false; |
|
137 |
|
138 if ( data[ca].second > data[cb].second ) { |
|
139 data[cb].first = ca; |
|
140 data[ca].second += data[cb].second; |
|
141 } |
|
142 else { |
|
143 data[ca].first = cb; |
|
144 data[cb].second += data[ca].second; |
|
145 } |
|
146 return true; |
|
147 } |
|
148 |
|
149 /** |
|
150 * \brief Returns the size of the component of element \e a. |
|
151 * |
|
152 * Returns the size of the component of element \e a. |
|
153 */ |
|
154 |
|
155 int size(T a) |
|
156 { |
|
157 int ca = find(a); |
|
158 return data[ca].second; |
|
159 } |
|
160 |
|
161 }; |
|
162 |
|
163 |
|
164 |
|
165 |
|
166 /*******************************************************/ |
|
167 |
|
168 |
|
169 #ifdef DEVELOPMENT_DOCS |
|
170 |
|
171 /** |
|
172 * \brief The auxiliary class for the \ref UnionFindEnum class. |
|
173 * |
|
174 * In the \ref UnionFindEnum class all components are represented as |
|
175 * a std::list. |
|
176 * Items of these lists are UnionFindEnumItem structures. |
|
177 * |
|
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. |
|
187 */ |
|
188 |
|
189 #endif |
|
190 |
|
191 template <typename T> |
|
192 struct UnionFindEnumItem { |
|
193 |
|
194 typedef std::list<UnionFindEnumItem> ItemList; |
|
195 typedef std::list<ItemList> ClassList; |
|
196 typedef typename ItemList::iterator IIter; |
|
197 typedef typename ClassList::iterator CIter; |
|
198 |
|
199 T me; |
|
200 IIter parent; |
|
201 int size; |
|
202 CIter my_class; |
|
203 |
|
204 UnionFindEnumItem() {} |
|
205 UnionFindEnumItem(const T &_me, CIter _my_class): |
|
206 me(_me), size(1), my_class(_my_class) {} |
|
207 }; |
|
208 |
|
209 |
|
210 /** |
|
211 * \brief A \e Union-Find data structure implementation which |
|
212 * is able to enumerate the components. |
|
213 * |
|
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. |
|
218 * |
|
219 * The union operation uses rank heuristic, while |
|
220 * the find operation uses path compression. |
|
221 * |
|
222 * \pre You |
|
223 * need to add all the elements by the \ref insert() method. |
|
224 */ |
|
225 |
|
226 |
|
227 template <typename T, template <typename Item> class Map> |
|
228 class UnionFindEnum { |
|
229 |
|
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; |
|
236 |
|
237 public: |
|
238 typedef T ElementType; |
|
239 typedef UnionFindEnumItem<T> ItemType; |
|
240 typedef Map< IIter > MapType; |
|
241 |
|
242 private: |
|
243 MapType& m; |
|
244 ClassList classes; |
|
245 |
|
246 IIter _find(IIter a) const { |
|
247 IIter comp = a; |
|
248 IIter next; |
|
249 while( (next = comp->parent) != comp ) { |
|
250 comp = next; |
|
251 } |
|
252 |
|
253 IIter comp1 = a; |
|
254 while( (next = comp1->parent) != comp ) { |
|
255 comp1->parent = comp->parent; |
|
256 comp1 = next; |
|
257 } |
|
258 return comp; |
|
259 } |
|
260 |
|
261 public: |
|
262 UnionFindEnum(MapType& _m) : m(_m) {} |
|
263 |
|
264 |
|
265 /** |
|
266 * \brief Inserts the given element into a new component. |
|
267 * |
|
268 * This method creates a new component consisting only of the |
|
269 * given element. |
|
270 */ |
|
271 |
|
272 void insert(const T &a) |
|
273 { |
|
274 |
|
275 |
|
276 classes.push_back(ItemList()); |
|
277 CIter aclass = classes.end(); |
|
278 --aclass; |
|
279 |
|
280 ItemList &alist = *aclass; |
|
281 alist.push_back(ItemType(a, aclass)); |
|
282 IIter ai = alist.begin(); |
|
283 |
|
284 ai->parent = ai; |
|
285 m.set(a, ai); |
|
286 |
|
287 } |
|
288 |
|
289 /** |
|
290 * \brief Inserts the given element into the component of the others. |
|
291 * |
|
292 * This methods inserts the element \e a into the component of the |
|
293 * element \e comp. |
|
294 */ |
|
295 |
|
296 void insert(const T &a, const T &comp) { |
|
297 |
|
298 IIter clit = _find(m[comp]); |
|
299 ItemList &c = *clit->my_class; |
|
300 c.push_back(ItemType(a,0)); |
|
301 IIter ai = c.end(); |
|
302 --ai; |
|
303 ai->parent = clit; |
|
304 m.set(a, ai); |
|
305 ++clit->size; |
|
306 } |
|
307 |
|
308 |
|
309 /** |
|
310 * \brief Finds the leader of the component of the given element. |
|
311 * |
|
312 * The method returns the leader of the component of the given element. |
|
313 */ |
|
314 |
|
315 T find(const T &a) const { |
|
316 return _find(m[a])->me; |
|
317 } |
|
318 |
|
319 |
|
320 /** |
|
321 * \brief Joining the component of element \e a and element \e b. |
|
322 * |
|
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. |
|
327 */ |
|
328 |
|
329 bool join(T a, T b) { |
|
330 |
|
331 IIter ca = _find(m[a]); |
|
332 IIter cb = _find(m[b]); |
|
333 |
|
334 if ( ca == cb ) { |
|
335 return false; |
|
336 } |
|
337 |
|
338 if ( ca->size > cb->size ) { |
|
339 |
|
340 cb->parent = ca->parent; |
|
341 ca->size += cb->size; |
|
342 |
|
343 ItemList &alist = *ca->my_class; |
|
344 alist.splice(alist.end(),*cb->my_class); |
|
345 |
|
346 classes.erase(cb->my_class); |
|
347 cb->my_class = 0; |
|
348 } |
|
349 else { |
|
350 |
|
351 ca->parent = cb->parent; |
|
352 cb->size += ca->size; |
|
353 |
|
354 ItemList &blist = *cb->my_class; |
|
355 blist.splice(blist.end(),*ca->my_class); |
|
356 |
|
357 classes.erase(ca->my_class); |
|
358 ca->my_class = 0; |
|
359 } |
|
360 |
|
361 return true; |
|
362 } |
|
363 |
|
364 |
|
365 /** |
|
366 * \brief Returns the size of the component of element \e a. |
|
367 * |
|
368 * Returns the size of the component of element \e a. |
|
369 */ |
|
370 |
|
371 int size(const T &a) const { |
|
372 return _find(m[a])->size; |
|
373 } |
|
374 |
|
375 |
|
376 /** |
|
377 * \brief Splits up the component of the element. |
|
378 * |
|
379 * Splitting the component of the element into sigleton |
|
380 * components (component of size one). |
|
381 */ |
|
382 |
|
383 void split(const T &a) { |
|
384 |
|
385 IIter ca = _find(m[a]); |
|
386 |
|
387 if ( ca->size == 1 ) |
|
388 return; |
|
389 |
|
390 CIter aclass = ca->my_class; |
|
391 |
|
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); |
|
396 |
|
397 curr->size=1; |
|
398 curr->parent=curr; |
|
399 curr->my_class = nl; |
|
400 } |
|
401 |
|
402 ca->size=1; |
|
403 return; |
|
404 } |
|
405 |
|
406 |
|
407 /** |
|
408 * \brief Sets the given element to the leader element of its component. |
|
409 * |
|
410 * Sets the given element to the leader element of its component. |
|
411 */ |
|
412 |
|
413 void makeRep(const T &a) { |
|
414 |
|
415 IIter ia = m[a]; |
|
416 IIter la = _find(ia); |
|
417 if (la == ia) return; |
|
418 |
|
419 ia->my_class = la->my_class; |
|
420 la->my_class = 0; |
|
421 |
|
422 ia->size = la->size; |
|
423 |
|
424 CIter l = ia->my_class; |
|
425 l->splice(l->begin(),*l,ia); |
|
426 |
|
427 ia->parent = ia; |
|
428 la->parent = ia; |
|
429 } |
|
430 |
|
431 /** |
|
432 * \brief Moves the given element to an other component. |
|
433 * |
|
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. |
|
438 */ |
|
439 |
|
440 bool move(const T &a, const T &comp) { |
|
441 |
|
442 IIter ai = m[a]; |
|
443 IIter lai = _find(ai); |
|
444 IIter clit = _find(m[comp]); |
|
445 |
|
446 if (lai == clit) |
|
447 return false; |
|
448 |
|
449 ItemList &cl = *clit->my_class, |
|
450 &al = *lai->my_class; |
|
451 |
|
452 bool is_leader = (lai == ai); |
|
453 bool singleton = false; |
|
454 |
|
455 if (is_leader) { |
|
456 ++lai; |
|
457 } |
|
458 |
|
459 cl.splice(cl.end(), al, ai); |
|
460 |
|
461 if (is_leader) { |
|
462 if (ai->size == 1) { |
|
463 classes.erase(ai->my_class); |
|
464 singleton = true; |
|
465 } |
|
466 else { |
|
467 lai->size = ai->size; |
|
468 lai->my_class = ai->my_class; |
|
469 } |
|
470 } |
|
471 if (!singleton) { |
|
472 for (IIter i = lai; i != al.end(); ++i) |
|
473 i->parent = lai; |
|
474 --lai->size; |
|
475 } |
|
476 |
|
477 ai->parent = clit; |
|
478 ai->my_class = 0; |
|
479 ++clit->size; |
|
480 |
|
481 return true; |
|
482 } |
|
483 |
|
484 |
|
485 /** |
|
486 * \brief Removes the given element from the structure. |
|
487 * |
|
488 * Removes the given element from the structure. |
|
489 * |
|
490 * Removes the element from its component and if the component becomes |
|
491 * empty then removes that component from the component list. |
|
492 */ |
|
493 void erase(const T &a) { |
|
494 |
|
495 IIter ma = m[a]; |
|
496 if (ma == 0) return; |
|
497 |
|
498 IIter la = _find(ma); |
|
499 if (la == ma) { |
|
500 if (ma -> size == 1){ |
|
501 classes.erase(ma->my_class); |
|
502 m.set(a,0); |
|
503 return; |
|
504 } |
|
505 ++la; |
|
506 la->size = ma->size; |
|
507 la->my_class = ma->my_class; |
|
508 } |
|
509 |
|
510 for (IIter i = la; i != la->my_class->end(); ++i) { |
|
511 i->parent = la; |
|
512 } |
|
513 |
|
514 la->size--; |
|
515 la->my_class->erase(ma); |
|
516 m.set(a,0); |
|
517 } |
|
518 |
|
519 /** |
|
520 * \brief Removes the component of the given element from the structure. |
|
521 * |
|
522 * Removes the component of the given element from the structure. |
|
523 */ |
|
524 |
|
525 void eraseClass(const T &a) { |
|
526 IIter ma = m[a]; |
|
527 if (ma == 0) return; |
|
528 # ifdef DEBUG |
|
529 CIter c = _find(ma)->my_class; |
|
530 for (IIter i=c->begin(); i!=c->end(); ++i) |
|
531 m.set(i->me, 0); |
|
532 # endif |
|
533 classes.erase(_find(ma)->my_class); |
|
534 } |
|
535 |
|
536 |
|
537 class ClassIt { |
|
538 friend class UnionFindEnum; |
|
539 |
|
540 CcIter i; |
|
541 public: |
|
542 ClassIt(Invalid): i(0) {} |
|
543 ClassIt() {} |
|
544 |
|
545 operator const T& () const { |
|
546 ItemList const &ll = *i; |
|
547 return (ll.begin())->me; } |
|
548 bool operator == (ClassIt it) const { |
|
549 return (i == it.i); |
|
550 } |
|
551 bool operator != (ClassIt it) const { |
|
552 return (i != it.i); |
|
553 } |
|
554 bool operator < (ClassIt it) const { |
|
555 return (i < it.i); |
|
556 } |
|
557 |
|
558 bool valid() const { return i != 0; } |
|
559 private: |
|
560 void first(const ClassList &l) { i = l.begin(); validate(l); } |
|
561 void next(const ClassList &l) { |
|
562 ++i; |
|
563 validate(l); |
|
564 } |
|
565 void validate(const ClassList &l) { |
|
566 if ( i == l.end() ) |
|
567 i = 0; |
|
568 } |
|
569 }; |
|
570 |
|
571 /** |
|
572 * \brief Sets the iterator to point to the first component. |
|
573 * |
|
574 * Sets the iterator to point to the first component. |
|
575 * |
|
576 * With the \ref first, \ref valid and \ref next methods you can |
|
577 * iterate through the components. For example: |
|
578 * \code |
|
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; |
|
585 * } |
|
586 * \endcode |
|
587 */ |
|
588 |
|
589 ClassIt& first(ClassIt& it) const { |
|
590 it.first(classes); |
|
591 return it; |
|
592 } |
|
593 |
|
594 /** |
|
595 * \brief Returns whether the iterator is valid. |
|
596 * |
|
597 * Returns whether the iterator is valid. |
|
598 * |
|
599 * With the \ref first, \ref valid and \ref next methods you can |
|
600 * iterate through the components. See the example here: \ref first. |
|
601 */ |
|
602 |
|
603 bool valid(ClassIt const &it) const { |
|
604 return it.valid(); |
|
605 } |
|
606 |
|
607 /** |
|
608 * \brief Steps the iterator to the next component. |
|
609 * |
|
610 * Steps the iterator to the next component. |
|
611 * |
|
612 * With the \ref first, \ref valid and \ref next methods you can |
|
613 * iterate through the components. See the example here: \ref first. |
|
614 */ |
|
615 |
|
616 ClassIt& next(ClassIt& it) const { |
|
617 it.next(classes); |
|
618 return it; |
|
619 } |
|
620 |
|
621 |
|
622 class ItemIt { |
|
623 friend class UnionFindEnum; |
|
624 |
|
625 IcIter i; |
|
626 const ItemList *l; |
|
627 public: |
|
628 ItemIt(Invalid): i(0) {} |
|
629 ItemIt() {} |
|
630 |
|
631 operator const T& () const { return i->me; } |
|
632 bool operator == (ItemIt it) const { |
|
633 return (i == it.i); |
|
634 } |
|
635 bool operator != (ItemIt it) const { |
|
636 return (i != it.i); |
|
637 } |
|
638 bool operator < (ItemIt it) const { |
|
639 return (i < it.i); |
|
640 } |
|
641 |
|
642 bool valid() const { return i != 0; } |
|
643 private: |
|
644 void first(const ItemList &il) { l=&il; i = l->begin(); validate(); } |
|
645 void next() { |
|
646 ++i; |
|
647 validate(); |
|
648 } |
|
649 void validate() { |
|
650 if ( i == l->end() ) |
|
651 i = 0; |
|
652 } |
|
653 }; |
|
654 |
|
655 |
|
656 |
|
657 /** |
|
658 * \brief Sets the iterator to point to the first element of the component. |
|
659 * |
|
660 * \anchor first2 |
|
661 * Sets the iterator to point to the first element of the component. |
|
662 * |
|
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): |
|
667 * \code |
|
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; |
|
675 * } |
|
676 * \endcode |
|
677 */ |
|
678 |
|
679 ItemIt& first(ItemIt& it, const T& a) const { |
|
680 it.first( * _find(m[a])->my_class ); |
|
681 return it; |
|
682 } |
|
683 |
|
684 /** |
|
685 * \brief Returns whether the iterator is valid. |
|
686 * |
|
687 * \anchor valid2 |
|
688 * Returns whether the iterator is valid. |
|
689 * |
|
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". |
|
694 */ |
|
695 |
|
696 bool valid(ItemIt const &it) const { |
|
697 return it.valid(); |
|
698 } |
|
699 |
|
700 /** |
|
701 * \brief Steps the iterator to the next component. |
|
702 * |
|
703 * \anchor next2 |
|
704 * Steps the iterator to the next component. |
|
705 * |
|
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". |
|
710 */ |
|
711 |
|
712 ItemIt& next(ItemIt& it) const { |
|
713 it.next(); |
|
714 return it; |
|
715 } |
|
716 |
|
717 }; |
|
718 |
|
719 |
|
720 //! @} |
|
721 |
|
722 } //namespace lemon |
|
723 |
|
724 #endif //LEMON_UNION_FIND_H |
|