3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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>
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 You need to add all the elements by the \ref insert()
53 template <typename _ItemIntMap>
57 typedef _ItemIntMap ItemIntMap;
58 typedef typename ItemIntMap::Key Item;
61 // If the items vector stores negative value for an item then
62 // that item is root item and it has -items[it] component size.
63 // Else the items[it] contains the index of the parent.
64 std::vector<int> items;
67 bool rep(int idx) const {
68 return items[idx] < 0;
71 int repIndex(int idx) const {
77 int next = items[idx];
78 const_cast<int&>(items[idx]) = k;
86 /// \brief Constructor
88 /// Constructor of the UnionFind class. You should give an item to
89 /// integer map which will be used from the data structure. If you
90 /// modify directly this map that may cause segmentation fault,
91 /// invalid data structure, or infinite loop when you use again
93 UnionFind(ItemIntMap& m) : index(m) {}
95 /// \brief Returns the index of the element's component.
97 /// The method returns the index of the element's component.
98 /// This is an integer between zero and the number of inserted elements.
100 int find(const Item& a) {
101 return repIndex(index[a]);
104 /// \brief Clears the union-find data structure
106 /// Erase each item from the data structure.
111 /// \brief Inserts a new element into the structure.
113 /// This method inserts a new element into the data structure.
115 /// The method returns the index of the new component.
116 int insert(const Item& a) {
117 int n = items.size();
123 /// \brief Joining the components of element \e a and element \e b.
125 /// This is the \e union operation of the Union-Find structure.
126 /// Joins the component of element \e a and component of
127 /// element \e b. If \e a and \e b are in the same component then
128 /// it returns false otherwise it returns true.
129 bool join(const Item& a, const Item& b) {
130 int ka = repIndex(index[a]);
131 int kb = repIndex(index[b]);
136 if (items[ka] < items[kb]) {
137 items[ka] += items[kb];
140 items[kb] += items[ka];
146 /// \brief Returns the size of the component of element \e a.
148 /// Returns the size of the component of element \e a.
149 int size(const Item& a) {
150 int k = repIndex(index[a]);
158 /// \brief A \e Union-Find data structure implementation which
159 /// is able to enumerate the components.
161 /// The class implements a \e Union-Find data structure
162 /// which is able to enumerate the components and the items in
163 /// a component. If you don't need this feature then perhaps it's
164 /// better to use the \ref UnionFind class which is more efficient.
166 /// The union operation uses rank heuristic, while
167 /// the find operation uses path compression.
169 /// \pre You need to add all the elements by the \ref insert()
172 template <typename _ItemIntMap>
173 class UnionFindEnum {
176 typedef _ItemIntMap ItemIntMap;
177 typedef typename ItemIntMap::Key Item;
183 // If the parent stores negative value for an item then that item
184 // is root item and it has ~(items[it].parent) component id. Else
185 // the items[it].parent contains the index of the parent.
187 // The \c next and \c prev provides the double-linked
188 // cyclic list of one component's items.
196 std::vector<ItemT> items;
205 std::vector<ClassT> classes;
206 int firstClass, firstFreeClass;
209 if (firstFreeClass == -1) {
210 int cdx = classes.size();
211 classes.push_back(ClassT());
214 int cdx = firstFreeClass;
215 firstFreeClass = classes[firstFreeClass].next;
221 if (firstFreeItem == -1) {
222 int idx = items.size();
223 items.push_back(ItemT());
226 int idx = firstFreeItem;
227 firstFreeItem = items[firstFreeItem].next;
233 bool rep(int idx) const {
234 return items[idx].parent < 0;
237 int repIndex(int idx) const {
243 int next = items[idx].parent;
244 const_cast<int&>(items[idx].parent) = k;
250 int classIndex(int idx) const {
251 return ~(items[repIndex(idx)].parent);
254 void singletonItem(int idx) {
255 items[idx].next = idx;
256 items[idx].prev = idx;
259 void laceItem(int idx, int rdx) {
260 items[idx].prev = rdx;
261 items[idx].next = items[rdx].next;
262 items[items[rdx].next].prev = idx;
263 items[rdx].next = idx;
266 void unlaceItem(int idx) {
267 items[items[idx].prev].next = items[idx].next;
268 items[items[idx].next].prev = items[idx].prev;
270 items[idx].next = firstFreeItem;
274 void spliceItems(int ak, int bk) {
275 items[items[ak].prev].next = bk;
276 items[items[bk].prev].next = ak;
277 int tmp = items[ak].prev;
278 items[ak].prev = items[bk].prev;
279 items[bk].prev = tmp;
283 void laceClass(int cls) {
284 if (firstClass != -1) {
285 classes[firstClass].prev = cls;
287 classes[cls].next = firstClass;
288 classes[cls].prev = -1;
292 void unlaceClass(int cls) {
293 if (classes[cls].prev != -1) {
294 classes[classes[cls].prev].next = classes[cls].next;
296 firstClass = classes[cls].next;
298 if (classes[cls].next != -1) {
299 classes[classes[cls].next].prev = classes[cls].prev;
302 classes[cls].next = firstFreeClass;
303 firstFreeClass = cls;
308 UnionFindEnum(ItemIntMap& _index)
309 : index(_index), items(), firstFreeItem(-1),
310 firstClass(-1), firstFreeClass(-1) {}
312 /// \brief Inserts the given element into a new component.
314 /// This method creates a new component consisting only of the
317 int insert(const Item& item) {
320 index.set(item, idx);
323 items[idx].item = item;
325 int cdx = newClass();
327 items[idx].parent = ~cdx;
330 classes[cdx].size = 1;
331 classes[cdx].firstItem = idx;
338 /// \brief Inserts the given element into the component of the others.
340 /// This methods inserts the element \e a into the component of the
342 void insert(const Item& item, int cls) {
343 int rdx = classes[cls].firstItem;
346 index.set(item, idx);
350 items[idx].item = item;
351 items[idx].parent = rdx;
353 ++classes[~(items[rdx].parent)].size;
356 /// \brief Clears the union-find data structure
358 /// Erase each item from the data structure.
365 /// \brief Finds the component of the given element.
367 /// The method returns the component id of the given element.
368 int find(const Item &item) const {
369 return ~(items[repIndex(index[item])].parent);
372 /// \brief Joining the component of element \e a and element \e b.
374 /// This is the \e union operation of the Union-Find structure.
375 /// Joins the component of element \e a and component of
376 /// element \e b. If \e a and \e b are in the same component then
377 /// returns -1 else returns the remaining class.
378 int join(const Item& a, const Item& b) {
380 int ak = repIndex(index[a]);
381 int bk = repIndex(index[b]);
387 int acx = ~(items[ak].parent);
388 int bcx = ~(items[bk].parent);
392 if (classes[acx].size > classes[bcx].size) {
393 classes[acx].size += classes[bcx].size;
394 items[bk].parent = ak;
398 classes[bcx].size += classes[acx].size;
399 items[ak].parent = bk;
408 /// \brief Returns the size of the class.
410 /// Returns the size of the class.
411 int size(int cls) const {
412 return classes[cls].size;
415 /// \brief Splits up the component.
417 /// Splitting the component into singleton components (component
419 void split(int cls) {
420 int fdx = classes[cls].firstItem;
421 int idx = items[fdx].next;
423 int next = items[idx].next;
427 int cdx = newClass();
428 items[idx].parent = ~cdx;
431 classes[cdx].size = 1;
432 classes[cdx].firstItem = idx;
437 items[idx].prev = idx;
438 items[idx].next = idx;
440 classes[~(items[idx].parent)].size = 1;
444 /// \brief Removes the given element from the structure.
446 /// Removes the element from its component and if the component becomes
447 /// empty then removes that component from the component list.
449 /// \warning It is an error to remove an element which is not in
451 /// \warning This running time of this operation is proportional to the
452 /// number of the items in this class.
453 void erase(const Item& item) {
454 int idx = index[item];
455 int fdx = items[idx].next;
457 int cdx = classIndex(idx);
460 items[idx].next = firstFreeItem;
464 classes[cdx].firstItem = fdx;
466 items[fdx].parent = ~cdx;
469 idx = items[fdx].next;
471 items[idx].parent = fdx;
472 idx = items[idx].next;
479 /// \brief Removes the component of the given element from the structure.
481 /// Removes the component of the given element from the structure.
483 /// \warning It is an error to give an element which is not in the
485 void eraseClass(int cls) {
486 int fdx = classes[cls].firstItem;
488 items[items[fdx].prev].next = firstFreeItem;
492 /// \brief Lemon style iterator for the representant items.
494 /// ClassIt is a lemon style iterator for the components. It iterates
495 /// on the ids of the classes.
498 /// \brief Constructor of the iterator
500 /// Constructor of the iterator
501 ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
502 cdx = unionFind->firstClass;
505 /// \brief Constructor to get invalid iterator
507 /// Constructor to get invalid iterator
508 ClassIt(Invalid) : unionFind(0), cdx(-1) {}
510 /// \brief Increment operator
512 /// It steps to the next representant item.
513 ClassIt& operator++() {
514 cdx = unionFind->classes[cdx].next;
518 /// \brief Conversion operator
520 /// It converts the iterator to the current representant item.
521 operator int() const {
525 /// \brief Equality operator
527 /// Equality operator
528 bool operator==(const ClassIt& i) {
532 /// \brief Inequality operator
534 /// Inequality operator
535 bool operator!=(const ClassIt& i) {
540 const UnionFindEnum* unionFind;
544 /// \brief Lemon style iterator for the items of a component.
546 /// ClassIt is a lemon style iterator for the components. It iterates
547 /// on the items of a class. By example if you want to iterate on
548 /// each items of each classes then you may write the next code.
550 /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
551 /// std::cout << "Class: ";
552 /// for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
553 /// std::cout << toString(iit) << ' ' << std::endl;
555 /// std::cout << std::endl;
560 /// \brief Constructor of the iterator
562 /// Constructor of the iterator. The iterator iterates
563 /// on the class of the \c item.
564 ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
565 fdx = idx = unionFind->classes[cls].firstItem;
568 /// \brief Constructor to get invalid iterator
570 /// Constructor to get invalid iterator
571 ItemIt(Invalid) : unionFind(0), idx(-1) {}
573 /// \brief Increment operator
575 /// It steps to the next item in the class.
576 ItemIt& operator++() {
577 idx = unionFind->items[idx].next;
578 if (idx == fdx) idx = -1;
582 /// \brief Conversion operator
584 /// It converts the iterator to the current item.
585 operator const Item&() const {
586 return unionFind->items[idx].item;
589 /// \brief Equality operator
591 /// Equality operator
592 bool operator==(const ItemIt& i) {
596 /// \brief Inequality operator
598 /// Inequality operator
599 bool operator!=(const ItemIt& i) {
604 const UnionFindEnum* unionFind;
612 /// \brief A \e Extend-Find data structure implementation which
613 /// is able to enumerate the components.
615 /// The class implements an \e Extend-Find data structure which is
616 /// able to enumerate the components and the items in a
617 /// component. The data structure is a simplification of the
618 /// Union-Find structure, and it does not allow to merge two components.
620 /// \pre You need to add all the elements by the \ref insert()
622 template <typename _ItemIntMap>
623 class ExtendFindEnum {
626 typedef _ItemIntMap ItemIntMap;
627 typedef typename ItemIntMap::Key Item;
639 std::vector<ItemT> items;
647 std::vector<ClassT> classes;
649 int firstClass, firstFreeClass;
652 if (firstFreeClass != -1) {
653 int cdx = firstFreeClass;
654 firstFreeClass = classes[cdx].next;
657 classes.push_back(ClassT());
658 return classes.size() - 1;
663 if (firstFreeItem != -1) {
664 int idx = firstFreeItem;
665 firstFreeItem = items[idx].next;
668 items.push_back(ItemT());
669 return items.size() - 1;
675 /// \brief Constructor
676 ExtendFindEnum(ItemIntMap& _index)
677 : index(_index), items(), firstFreeItem(-1),
678 classes(), firstClass(-1), firstFreeClass(-1) {}
680 /// \brief Inserts the given element into a new component.
682 /// This method creates a new component consisting only of the
684 int insert(const Item& item) {
685 int cdx = newClass();
686 classes[cdx].prev = -1;
687 classes[cdx].next = firstClass;
691 items[idx].item = item;
692 items[idx].cls = cdx;
693 items[idx].prev = idx;
694 items[idx].next = idx;
696 classes[cdx].firstItem = idx;
698 index.set(item, idx);
703 /// \brief Inserts the given element into the given component.
705 /// This methods inserts the element \e item a into the \e cls class.
706 void insert(const Item& item, int cls) {
708 int rdx = classes[cls].firstItem;
709 items[idx].item = item;
710 items[idx].cls = cls;
712 items[idx].prev = rdx;
713 items[idx].next = items[rdx].next;
714 items[items[rdx].next].prev = idx;
715 items[rdx].next = idx;
717 index.set(item, idx);
720 /// \brief Clears the union-find data structure
722 /// Erase each item from the data structure.
726 firstClass = firstFreeClass = firstFreeItem = -1;
729 /// \brief Gives back the class of the \e item.
731 /// Gives back the class of the \e item.
732 int find(const Item &item) const {
733 return items[index[item]].cls;
736 /// \brief Removes the given element from the structure.
738 /// Removes the element from its component and if the component becomes
739 /// empty then removes that component from the component list.
741 /// \warning It is an error to remove an element which is not in
743 void erase(const Item &item) {
744 int idx = index[item];
745 int cdx = items[idx].cls;
747 if (idx == items[idx].next) {
748 if (classes[cdx].prev != -1) {
749 classes[classes[cdx].prev].next = classes[cdx].next;
751 firstClass = classes[cdx].next;
753 if (classes[cdx].next != -1) {
754 classes[classes[cdx].next].prev = classes[cdx].prev;
756 classes[cdx].next = firstFreeClass;
757 firstFreeClass = cdx;
759 classes[cdx].firstItem = items[idx].next;
760 items[items[idx].next].prev = items[idx].prev;
761 items[items[idx].prev].next = items[idx].next;
763 items[idx].next = firstFreeItem;
769 /// \brief Removes the component of the given element from the structure.
771 /// Removes the component of the given element from the structure.
773 /// \warning It is an error to give an element which is not in the
775 void eraseClass(int cdx) {
776 int idx = classes[cdx].firstItem;
777 items[items[idx].prev].next = firstFreeItem;
780 if (classes[cdx].prev != -1) {
781 classes[classes[cdx].prev].next = classes[cdx].next;
783 firstClass = classes[cdx].next;
785 if (classes[cdx].next != -1) {
786 classes[classes[cdx].next].prev = classes[cdx].prev;
788 classes[cdx].next = firstFreeClass;
789 firstFreeClass = cdx;
792 /// \brief Lemon style iterator for the classes.
794 /// ClassIt is a lemon style iterator for the components. It iterates
795 /// on the ids of classes.
798 /// \brief Constructor of the iterator
800 /// Constructor of the iterator
801 ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
802 cdx = extendFind->firstClass;
805 /// \brief Constructor to get invalid iterator
807 /// Constructor to get invalid iterator
808 ClassIt(Invalid) : extendFind(0), cdx(-1) {}
810 /// \brief Increment operator
812 /// It steps to the next representant item.
813 ClassIt& operator++() {
814 cdx = extendFind->classes[cdx].next;
818 /// \brief Conversion operator
820 /// It converts the iterator to the current class id.
821 operator int() const {
825 /// \brief Equality operator
827 /// Equality operator
828 bool operator==(const ClassIt& i) {
832 /// \brief Inequality operator
834 /// Inequality operator
835 bool operator!=(const ClassIt& i) {
840 const ExtendFindEnum* extendFind;
844 /// \brief Lemon style iterator for the items of a component.
846 /// ClassIt is a lemon style iterator for the components. It iterates
847 /// on the items of a class. By example if you want to iterate on
848 /// each items of each classes then you may write the next code.
850 /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
851 /// std::cout << "Class: ";
852 /// for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
853 /// std::cout << toString(iit) << ' ' << std::endl;
855 /// std::cout << std::endl;
860 /// \brief Constructor of the iterator
862 /// Constructor of the iterator. The iterator iterates
863 /// on the class of the \c item.
864 ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
865 fdx = idx = extendFind->classes[cls].firstItem;
868 /// \brief Constructor to get invalid iterator
870 /// Constructor to get invalid iterator
871 ItemIt(Invalid) : extendFind(0), idx(-1) {}
873 /// \brief Increment operator
875 /// It steps to the next item in the class.
876 ItemIt& operator++() {
877 idx = extendFind->items[idx].next;
878 if (fdx == idx) idx = -1;
882 /// \brief Conversion operator
884 /// It converts the iterator to the current item.
885 operator const Item&() const {
886 return extendFind->items[idx].item;
889 /// \brief Equality operator
891 /// Equality operator
892 bool operator==(const ItemIt& i) {
896 /// \brief Inequality operator
898 /// Inequality operator
899 bool operator!=(const ItemIt& i) {
904 const ExtendFindEnum* extendFind;
914 #endif //LEMON_UNION_FIND_H