Kruskal alg. (src/hugo/kruskal.h, src/test/kruskal_test.cc) is (almost) done.
- Some input adaptor is still missing.
- The class and function names should be revised.
- Docs still needs some improvement.
2 #ifndef HUGO_UNION_FIND_H
3 #define HUGO_UNION_FIND_H
7 //!\brief Union-Find data structures.
9 //!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
10 //!fails to run (Segmentation fault).
18 #include <hugo/invalid.h>
22 //! \addtogroup auxdat
26 * \brief A \e Union-Find data structure implementation
28 * The class implements the \e Union-Find data structure.
29 * The union operation uses rank heuristic, while
30 * the find operation uses path compression.
31 * This is a very simple but efficient implementation, providing
32 * only four methods: join (union), find, insert and size.
33 * For more features see the \ref UnionFindEnum class.
35 * It is primarily used in Kruskal algorithm for finding minimal
36 * cost spanning tree in a graph.
39 * \pre The elements are automatically added only if the map
40 * given to the constructor was filled with -1's. Otherwise you
41 * need to add all the elements by the \ref insert() method.
42 * \bug It is not clear what the constructor parameter is used for.
45 template <typename T, typename TIntMap>
49 typedef T ElementType;
50 typedef std::pair<int,int> PairType;
53 std::vector<PairType> data;
57 UnionFind(TIntMap& m) : map(m) {}
60 * \brief Returns the index of the element's component.
62 * The method returns the index of the element's component.
63 * This is an integer between zero and the number of inserted elements.
74 while ( (next = data[comp].first) != comp) {
77 while ( (next = data[comp0].first) != comp) {
78 data[comp0].first = comp;
86 * \brief Insert a new element into the structure.
88 * This method inserts a new element into the data structure.
90 * It is not required to use this method:
91 * if the map given to the constructor was filled
92 * with -1's then it is called automatically
93 * on the first \ref find or \ref join.
95 * The method returns the index of the new component.
101 data.push_back(std::make_pair(n, 1));
107 * \brief Joining the components of element \e a and element \e b.
109 * This is the \e union operation of the Union-Find structure.
110 * Joins the component of elemenent \e a and component of
111 * element \e b. If \e a and \e b are in the same component then
112 * it returns false otherwise it returns true.
123 if ( data[ca].second > data[cb].second ) {
125 data[ca].second += data[cb].second;
129 data[cb].second += data[ca].second;
135 * \brief Returns the size of the component of element \e a.
137 * Returns the size of the component of element \e a.
143 return data[ca].second;
151 /*******************************************************/
154 #ifdef DEVELOPMENT_DOCS
157 * \brief The auxiliary class for the \ref UnionFindEnum class.
159 * In the \ref UnionFindEnum class all components are represented as
161 * Items of these lists are UnionFindEnumItem structures.
163 * The class has four fields:
164 * - T me - the actual element
165 * - IIter parent - the parent of the element in the union-find structure
166 * - int size - the size of the component of the element.
167 * Only valid if the element
168 * is the leader of the component.
169 * - CIter my_class - pointer into the list of components
170 * pointing to the component of the element.
171 * Only valid if the element is the leader of the component.
176 template <typename T>
177 struct UnionFindEnumItem {
179 typedef std::list<UnionFindEnumItem> ItemList;
180 typedef std::list<ItemList> ClassList;
181 typedef typename ItemList::iterator IIter;
182 typedef typename ClassList::iterator CIter;
189 UnionFindEnumItem() {}
190 UnionFindEnumItem(const T &_me, CIter _my_class):
191 me(_me), size(1), my_class(_my_class) {}
196 * \brief A \e Union-Find data structure implementation which
197 * is able to enumerate the components.
199 * The class implements a \e Union-Find data structure
200 * which is able to enumerate the components and the items in
201 * a component. If you don't need this feature then perhaps it's
202 * better to use the \ref UnionFind class which is more efficient.
204 * The union operation uses rank heuristic, while
205 * the find operation uses path compression.
208 * need to add all the elements by the \ref insert() method.
212 template <typename T, template <typename Item> class Map>
213 class UnionFindEnum {
215 typedef std::list<UnionFindEnumItem<T> > ItemList;
216 typedef std::list<ItemList> ClassList;
217 typedef typename ItemList::iterator IIter;
218 typedef typename ItemList::const_iterator IcIter;
219 typedef typename ClassList::iterator CIter;
220 typedef typename ClassList::const_iterator CcIter;
223 typedef T ElementType;
224 typedef UnionFindEnumItem<T> ItemType;
225 typedef Map< IIter > MapType;
231 IIter _find(IIter a) const {
234 while( (next = comp->parent) != comp ) {
239 while( (next = comp1->parent) != comp ) {
240 comp1->parent = comp->parent;
247 UnionFindEnum(MapType& _m) : m(_m) {}
251 * \brief Insert the given element into a new component.
253 * This method creates a new component consisting only of the
257 void insert(const T &a)
261 classes.push_back(ItemList());
262 CIter aclass = classes.end();
265 ItemList &alist = *aclass;
266 alist.push_back(ItemType(a, aclass));
267 IIter ai = alist.begin();
275 * \brief Insert the given element into the component of the others.
277 * This methods insert the element \e a into the component of the
281 void insert(const T &a, const T &comp) {
283 IIter clit = _find(m[comp]);
284 ItemList &c = *clit->my_class;
285 c.push_back(ItemType(a,0));
295 * \brief Find the leader of the component of the given element.
297 * The method returns the leader of the component of the given element.
300 T find(const T &a) const {
301 return _find(m[a])->me;
306 * \brief Joining the component of element \e a and element \e b.
308 * This is the \e union operation of the Union-Find structure.
309 * Joins the component of elemenent \e a and component of
310 * element \e b. If \e a and \e b are in the same component then
311 * returns false else returns true.
314 bool join(T a, T b) {
316 IIter ca = _find(m[a]);
317 IIter cb = _find(m[b]);
323 if ( ca->size > cb->size ) {
325 cb->parent = ca->parent;
326 ca->size += cb->size;
328 ItemList &alist = *ca->my_class;
329 alist.splice(alist.end(),*cb->my_class);
331 classes.erase(cb->my_class);
336 ca->parent = cb->parent;
337 cb->size += ca->size;
339 ItemList &blist = *cb->my_class;
340 blist.splice(blist.end(),*ca->my_class);
342 classes.erase(ca->my_class);
351 * \brief Returns the size of the component of element \e a.
353 * Returns the size of the component of element \e a.
356 int size(const T &a) const {
357 return _find(m[a])->size;
362 * \brief Split up the component of the element.
364 * Splitting the component of the element into sigleton
365 * components (component of size one).
368 void split(const T &a) {
370 IIter ca = _find(m[a]);
375 CIter aclass = ca->my_class;
377 for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
378 classes.push_back(ItemList());
379 CIter nl = --classes.end();
380 nl->splice(nl->end(), *aclass, curr);
393 * \brief Set the given element to the leader element of its component.
395 * Set the given element to the leader element of its component.
398 void makeRep(const T &a) {
401 IIter la = _find(ia);
402 if (la == ia) return;
404 ia->my_class = la->my_class;
409 CIter l = ia->my_class;
410 l->splice(l->begin(),*l,ia);
417 * \brief Move the given element to an other component.
419 * This method moves the element \e a from its component
420 * to the component of \e comp.
421 * If \e a and \e comp are in the same component then
422 * it returns false otherwise it returns true.
425 bool move(const T &a, const T &comp) {
428 IIter lai = _find(ai);
429 IIter clit = _find(m[comp]);
434 ItemList &c = *clit->my_class;
436 bool is_leader = (lai == ai);
437 bool singleton = false;
443 c.splice(c.end(), *lai->my_class, ai);
447 classes.erase(ai->my_class);
451 lai->size = ai->size;
452 lai->my_class = ai->my_class;
456 for (IIter i = lai; i != lai->my_class->end(); ++i)
470 * \brief Remove the given element from the structure.
472 * Remove the given element from the structure.
474 * Removes the element from its component and if the component becomes
475 * empty then removes that component from the component list.
477 void erase(const T &a) {
482 IIter la = _find(ma);
484 if (ma -> size == 1){
485 classes.erase(ma->my_class);
491 la->my_class = ma->my_class;
494 for (IIter i = la; i != la->my_class->end(); ++i) {
499 la->my_class->erase(ma);
504 * \brief Removes the component of the given element from the structure.
506 * Removes the component of the given element from the structure.
509 void eraseClass(const T &a) {
513 CIter c = _find(ma)->my_class;
514 for (IIter i=c->begin(); i!=c->end(); ++i)
517 classes.erase(_find(ma)->my_class);
522 friend class UnionFindEnum;
526 ClassIt(Invalid): i(0) {}
529 operator const T& () const {
530 ItemList const &ll = *i;
531 return (ll.begin())->me; }
532 bool operator == (ClassIt it) const {
535 bool operator != (ClassIt it) const {
538 bool operator < (ClassIt it) const {
542 bool valid() const { return i != 0; }
544 void first(const ClassList &l) { i = l.begin(); validate(l); }
545 void next(const ClassList &l) {
549 void validate(const ClassList &l) {
556 * \brief Sets the iterator to point to the first component.
558 * Sets the iterator to point to the first component.
560 * With the \ref first, \ref valid and \ref next methods you can
561 * iterate through the components. For example:
563 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
564 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
565 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
566 * for (U.first(iter); U.valid(iter); U.next(iter)) {
567 * // iter is convertible to Graph::Node
568 * cout << iter << endl;
573 ClassIt& first(ClassIt& it) const {
579 * \brief Returns whether the iterator is valid.
581 * Returns whether the iterator is valid.
583 * With the \ref first, \ref valid and \ref next methods you can
584 * iterate through the components. See the example here: \ref first.
587 bool valid(ClassIt const &it) const {
592 * \brief Steps the iterator to the next component.
594 * Steps the iterator to the next component.
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 ClassIt& next(ClassIt& it) const {
607 friend class UnionFindEnum;
612 ItemIt(Invalid): i(0) {}
615 operator const T& () const { return i->me; }
616 bool operator == (ItemIt it) const {
619 bool operator != (ItemIt it) const {
622 bool operator < (ItemIt it) const {
626 bool valid() const { return i != 0; }
628 void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
642 * \brief Sets the iterator to point to the first element of the component.
645 * Sets the iterator to point to the first element of the component.
647 * With the \ref first2 "first", \ref valid2 "valid"
648 * and \ref next2 "next" methods you can
649 * iterate through the elements of a component. For example
650 * (iterating through the component of the node \e node):
652 * Graph::Node node = ...;
653 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
654 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
655 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
656 * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
657 * // iiter is convertible to Graph::Node
658 * cout << iiter << endl;
663 ItemIt& first(ItemIt& it, const T& a) const {
664 it.first( * _find(m[a])->my_class );
669 * \brief Returns whether the iterator is valid.
672 * Returns whether the iterator is valid.
674 * With the \ref first2 "first", \ref valid2 "valid"
675 * and \ref next2 "next" methods you can
676 * iterate through the elements of a component.
677 * See the example here: \ref first2 "first".
680 bool valid(ItemIt const &it) const {
685 * \brief Steps the iterator to the next component.
688 * Steps the iterator to the next component.
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".
696 ItemIt& next(ItemIt& it) const {
708 #endif //HUGO_UNION_FIND_H