Nicer and more documented graph_wrapper.h file.
These are only the first steps for making this file more beautiful.
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 * \pre The elements are automatically added only if the map
36 * given to the constructor was filled with -1's. Otherwise you
37 * need to add all the elements by the \ref insert() method.
40 template <typename T, typename TIntMap>
44 typedef T ElementType;
45 typedef std::pair<int,int> PairType;
48 std::vector<PairType> data;
52 UnionFind(TIntMap& m) : map(m) {}
55 * \brief Returns the index of the element's component.
57 * The method returns the index of the element's component.
58 * This is an integer between zero and the number of inserted elements.
69 while ( (next = data[comp].first) != comp) {
72 while ( (next = data[comp0].first) != comp) {
73 data[comp0].first = comp;
81 * \brief Insert a new element into the structure.
83 * This method inserts a new element into the data structure.
85 * It is not required to use this method:
86 * if the map given to the constructor was filled
87 * with -1's then it is called automatically
88 * on the first \ref find or \ref join.
90 * The method returns the index of the new component.
96 data.push_back(std::make_pair(n, 1));
102 * \brief Joining the components of element \e a and element \e b.
104 * This is the \e union operation of the Union-Find structure.
105 * Joins the component of elemenent \e a and component of
106 * element \e b. If \e a and \e b are in the same component then
107 * it returns false otherwise it returns true.
118 if ( data[ca].second > data[cb].second ) {
120 data[ca].second += data[cb].second;
124 data[cb].second += data[ca].second;
130 * \brief Returns the size of the component of element \e a.
132 * Returns the size of the component of element \e a.
138 return data[ca].second;
146 /*******************************************************/
149 #ifdef DEVELOPMENT_DOCS
152 * \brief The auxiliary class for the \ref UnionFindEnum class.
154 * In the \ref UnionFindEnum class all components are represented as
156 * Items of these lists are UnionFindEnumItem structures.
158 * The class has four fields:
159 * - T me - the actual element
160 * - IIter parent - the parent of the element in the union-find structure
161 * - int size - the size of the component of the element.
162 * Only valid if the element
163 * is the leader of the component.
164 * - CIter my_class - pointer into the list of components
165 * pointing to the component of the element.
166 * Only valid if the element is the leader of the component.
171 template <typename T>
172 struct UnionFindEnumItem {
174 typedef std::list<UnionFindEnumItem> ItemList;
175 typedef std::list<ItemList> ClassList;
176 typedef typename ItemList::iterator IIter;
177 typedef typename ClassList::iterator CIter;
184 UnionFindEnumItem() {}
185 UnionFindEnumItem(const T &_me, CIter _my_class):
186 me(_me), size(1), my_class(_my_class) {}
191 * \brief A \e Union-Find data structure implementation which
192 * is able to enumerate the components.
194 * The class implements a \e Union-Find data structure
195 * which is able to enumerate the components and the items in
196 * a component. If you don't need this feature then perhaps it's
197 * better to use the \ref UnionFind class which is more efficient.
199 * The union operation uses rank heuristic, while
200 * the find operation uses path compression.
203 * need to add all the elements by the \ref insert() method.
207 template <typename T, template <typename Item> class Map>
208 class UnionFindEnum {
210 typedef std::list<UnionFindEnumItem<T> > ItemList;
211 typedef std::list<ItemList> ClassList;
212 typedef typename ItemList::iterator IIter;
213 typedef typename ItemList::const_iterator IcIter;
214 typedef typename ClassList::iterator CIter;
215 typedef typename ClassList::const_iterator CcIter;
218 typedef T ElementType;
219 typedef UnionFindEnumItem<T> ItemType;
220 typedef Map< IIter > MapType;
226 IIter _find(IIter a) const {
229 while( (next = comp->parent) != comp ) {
234 while( (next = comp1->parent) != comp ) {
235 comp1->parent = comp->parent;
242 UnionFindEnum(MapType& _m) : m(_m) {}
246 * \brief Insert the given element into a new component.
248 * This method creates a new component consisting only of the
252 void insert(const T &a)
256 classes.push_back(ItemList());
257 CIter aclass = classes.end();
260 ItemList &alist = *aclass;
261 alist.push_back(ItemType(a, aclass));
262 IIter ai = alist.begin();
270 * \brief Insert the given element into the component of the others.
272 * This methods insert the element \e a into the component of the
276 void insert(const T &a, const T &comp) {
278 IIter clit = _find(m[comp]);
279 ItemList &c = *clit->my_class;
280 c.push_back(ItemType(a,0));
290 * \brief Find the leader of the component of the given element.
292 * The method returns the leader of the component of the given element.
295 T find(const T &a) const {
296 return _find(m[a])->me;
301 * \brief Joining the component of element \e a and element \e b.
303 * This is the \e union operation of the Union-Find structure.
304 * Joins the component of elemenent \e a and component of
305 * element \e b. If \e a and \e b are in the same component then
306 * returns false else returns true.
309 bool join(T a, T b) {
311 IIter ca = _find(m[a]);
312 IIter cb = _find(m[b]);
318 if ( ca->size > cb->size ) {
320 cb->parent = ca->parent;
321 ca->size += cb->size;
323 ItemList &alist = *ca->my_class;
324 alist.splice(alist.end(),*cb->my_class);
326 classes.erase(cb->my_class);
331 ca->parent = cb->parent;
332 cb->size += ca->size;
334 ItemList &blist = *cb->my_class;
335 blist.splice(blist.end(),*ca->my_class);
337 classes.erase(ca->my_class);
346 * \brief Returns the size of the component of element \e a.
348 * Returns the size of the component of element \e a.
351 int size(const T &a) const {
352 return _find(m[a])->size;
357 * \brief Split up the component of the element.
359 * Splitting the component of the element into sigleton
360 * components (component of size one).
363 void split(const T &a) {
365 IIter ca = _find(m[a]);
370 CIter aclass = ca->my_class;
372 for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
373 classes.push_back(ItemList());
374 CIter nl = --classes.end();
375 nl->splice(nl->end(), *aclass, curr);
388 * \brief Set the given element to the leader element of its component.
390 * Set the given element to the leader element of its component.
393 void makeRep(const T &a) {
396 IIter la = _find(ia);
397 if (la == ia) return;
399 ia->my_class = la->my_class;
404 CIter l = ia->my_class;
405 l->splice(l->begin(),*l,ia);
412 * \brief Move the given element to an other component.
414 * This method moves the element \e a from its component
415 * to the component of \e comp.
416 * If \e a and \e comp are in the same component then
417 * it returns false otherwise it returns true.
420 bool move(const T &a, const T &comp) {
423 IIter lai = _find(ai);
424 IIter clit = _find(m[comp]);
429 ItemList &c = *clit->my_class;
431 bool is_leader = (lai == ai);
432 bool singleton = false;
438 c.splice(c.end(), *lai->my_class, ai);
442 classes.erase(ai->my_class);
446 lai->size = ai->size;
447 lai->my_class = ai->my_class;
451 for (IIter i = lai; i != lai->my_class->end(); ++i)
465 * \brief Remove the given element from the structure.
467 * Remove the given element from the structure.
469 * Removes the element from its component and if the component becomes
470 * empty then removes that component from the component list.
472 void erase(const T &a) {
477 IIter la = _find(ma);
479 if (ma -> size == 1){
480 classes.erase(ma->my_class);
486 la->my_class = ma->my_class;
489 for (IIter i = la; i != la->my_class->end(); ++i) {
494 la->my_class->erase(ma);
499 * \brief Removes the component of the given element from the structure.
501 * Removes the component of the given element from the structure.
504 void eraseClass(const T &a) {
508 CIter c = _find(ma)->my_class;
509 for (IIter i=c->begin(); i!=c->end(); ++i)
512 classes.erase(_find(ma)->my_class);
517 friend class UnionFindEnum;
521 ClassIt(Invalid): i(0) {}
524 operator const T& () const {
525 ItemList const &ll = *i;
526 return (ll.begin())->me; }
527 bool operator == (ClassIt it) const {
530 bool operator != (ClassIt it) const {
533 bool operator < (ClassIt it) const {
537 bool valid() const { return i != 0; }
539 void first(const ClassList &l) { i = l.begin(); validate(l); }
540 void next(const ClassList &l) {
544 void validate(const ClassList &l) {
551 * \brief Sets the iterator to point to the first component.
553 * Sets the iterator to point to the first component.
555 * With the \ref first, \ref valid and \ref next methods you can
556 * iterate through the components. For example:
558 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
559 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
560 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
561 * for (U.first(iter); U.valid(iter); U.next(iter)) {
562 * // iter is convertible to Graph::Node
563 * cout << iter << endl;
568 ClassIt& first(ClassIt& it) const {
574 * \brief Returns whether the iterator is valid.
576 * Returns whether the iterator is valid.
578 * With the \ref first, \ref valid and \ref next methods you can
579 * iterate through the components. See the example here: \ref first.
582 bool valid(ClassIt const &it) const {
587 * \brief Steps the iterator to the next component.
589 * Steps the iterator to the next component.
591 * With the \ref first, \ref valid and \ref next methods you can
592 * iterate through the components. See the example here: \ref first.
595 ClassIt& next(ClassIt& it) const {
602 friend class UnionFindEnum;
607 ItemIt(Invalid): i(0) {}
610 operator const T& () const { return i->me; }
611 bool operator == (ItemIt it) const {
614 bool operator != (ItemIt it) const {
617 bool operator < (ItemIt it) const {
621 bool valid() const { return i != 0; }
623 void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
637 * \brief Sets the iterator to point to the first element of the component.
640 * Sets the iterator to point to the first element of the component.
642 * With the \ref first2 "first", \ref valid2 "valid"
643 * and \ref next2 "next" methods you can
644 * iterate through the elements of a component. For example
645 * (iterating through the component of the node \e node):
647 * Graph::Node node = ...;
648 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
649 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
650 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
651 * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
652 * // iiter is convertible to Graph::Node
653 * cout << iiter << endl;
658 ItemIt& first(ItemIt& it, const T& a) const {
659 it.first( * _find(m[a])->my_class );
664 * \brief Returns whether the iterator is valid.
667 * Returns whether the iterator is valid.
669 * With the \ref first2 "first", \ref valid2 "valid"
670 * and \ref next2 "next" methods you can
671 * iterate through the elements of a component.
672 * See the example here: \ref first2 "first".
675 bool valid(ItemIt const &it) const {
680 * \brief Steps the iterator to the next component.
683 * Steps the iterator to the next component.
685 * With the \ref first2 "first", \ref valid2 "valid"
686 * and \ref next2 "next" methods you can
687 * iterate through the elements of a component.
688 * See the example here: \ref first2 "first".
691 ItemIt& next(ItemIt& it) const {
703 #endif //HUGO_UNION_FIND_H