Added a short tutorial on using graphs.
2 #ifndef HUGO_UNION_FIND_H
3 #define HUGO_UNION_FIND_H
7 //!\brief Union-Find data structures.
15 #include <hugo/invalid.h>
19 //! \addtogroup auxdat
23 * \brief A \e Union-Find data structure implementation
25 * The class implements the \e Union-Find data structure.
26 * The union operation uses rank heuristic, while
27 * the find operation uses path compression.
28 * This is a very simple but efficient implementation, providing
29 * only four methods: join (union), find, insert and size.
30 * For more features see the \ref UnionFindEnum class.
32 * \pre The elements are automatically added only if the map
33 * given to the constructor was filled with -1's. Otherwise you
34 * need to add all the elements by the \ref insert() method.
37 template <typename T, typename TIntMap>
41 typedef T ElementType;
42 typedef std::pair<int,int> PairType;
45 std::vector<PairType> data;
49 UnionFind(TIntMap& m) : map(m) {}
52 * \brief Returns the index of the element's component.
54 * The method returns the index of the element's component.
55 * This is an integer between zero and the number of inserted elements.
66 while ( (next = data[comp].first) != comp) {
69 while ( (next = data[comp0].first) != comp) {
70 data[comp0].first = comp;
78 * \brief Insert a new element into the structure.
80 * This method inserts a new element into the data structure.
82 * It is not required to use this method:
83 * if the map given to the constructor was filled
84 * with -1's then it is called automatically
85 * on the first \ref find or \ref join.
87 * The method returns the index of the new component.
93 data.push_back(std::make_pair(n, 1));
99 * \brief Joining the components of element \e a and element \e b.
101 * This is the \e union operation of the Union-Find structure.
102 * Joins the component of elemenent \e a and component of
103 * element \e b. If \e a and \e b are in the same component then
104 * it returns false otherwise it returns true.
115 if ( data[ca].second > data[cb].second ) {
117 data[ca].second += data[cb].second;
121 data[cb].second += data[ca].second;
127 * \brief Returns the size of the component of element \e a.
129 * Returns the size of the component of element \e a.
135 return data[ca].second;
143 /*******************************************************/
146 #ifdef DEVELOPMENT_DOCS
149 * \brief The auxiliary class for the \ref UnionFindEnum class.
151 * In the \ref UnionFindEnum class all components are represented as
153 * Items of these lists are UnionFindEnumItem structures.
155 * The class has four fields:
156 * - T me - the actual element
157 * - IIter parent - the parent of the element in the union-find structure
158 * - int size - the size of the component of the element.
159 * Only valid if the element
160 * is the leader of the component.
161 * - CIter my_class - pointer into the list of components
162 * pointing to the component of the element.
163 * Only valid if the element is the leader of the component.
168 template <typename T>
169 struct UnionFindEnumItem {
171 typedef std::list<UnionFindEnumItem> ItemList;
172 typedef std::list<ItemList> ClassList;
173 typedef typename ItemList::iterator IIter;
174 typedef typename ClassList::iterator CIter;
181 UnionFindEnumItem() {}
182 UnionFindEnumItem(const T &_me, CIter _my_class):
183 me(_me), size(1), my_class(_my_class) {}
188 * \brief A \e Union-Find data structure implementation which
189 * is able to enumerate the components.
191 * The class implements a \e Union-Find data structure
192 * which is able to enumerate the components and the items in
193 * a component. If you don't need this feature then perhaps it's
194 * better to use the \ref UnionFind class which is more efficient.
196 * The union operation uses rank heuristic, while
197 * the find operation uses path compression.
200 * need to add all the elements by the \ref insert() method.
204 template <typename T, template <typename Item> class Map>
205 class UnionFindEnum {
207 typedef std::list<UnionFindEnumItem<T> > ItemList;
208 typedef std::list<ItemList> ClassList;
209 typedef typename ItemList::iterator IIter;
210 typedef typename ItemList::const_iterator IcIter;
211 typedef typename ClassList::iterator CIter;
212 typedef typename ClassList::const_iterator CcIter;
215 typedef T ElementType;
216 typedef UnionFindEnumItem<T> ItemType;
217 typedef Map< IIter > MapType;
223 IIter _find(IIter a) const {
226 while( (next = comp->parent) != comp ) {
231 while( (next = comp1->parent) != comp ) {
232 comp1->parent = comp->parent;
239 UnionFindEnum(MapType& _m) : m(_m) {}
243 * \brief Insert the given element into a new component.
245 * This method creates a new component consisting only of the
249 void insert(const T &a)
253 classes.push_back(ItemList());
254 CIter aclass = classes.end();
257 ItemList &alist = *aclass;
258 alist.push_back(ItemType(a, aclass));
259 IIter ai = alist.begin();
267 * \brief Insert the given element into the component of the others.
269 * This methods insert the element \e a into the component of the
273 void insert(const T &a, const T &comp) {
275 IIter clit = _find(m[comp]);
276 ItemList &c = *clit->my_class;
277 c.push_back(ItemType(a,0));
287 * \brief Find the leader of the component of the given element.
289 * The method returns the leader of the component of the given element.
292 T find(const T &a) const {
293 return _find(m[a])->me;
298 * \brief Joining the component of element \e a and element \e b.
300 * This is the \e union operation of the Union-Find structure.
301 * Joins the component of elemenent \e a and component of
302 * element \e b. If \e a and \e b are in the same component then
303 * returns false else returns true.
306 bool join(T a, T b) {
308 IIter ca = _find(m[a]);
309 IIter cb = _find(m[b]);
315 if ( ca->size > cb->size ) {
317 cb->parent = ca->parent;
318 ca->size += cb->size;
320 ItemList &alist = *ca->my_class;
321 alist.splice(alist.end(),*cb->my_class);
323 classes.erase(cb->my_class);
328 ca->parent = cb->parent;
329 cb->size += ca->size;
331 ItemList &blist = *cb->my_class;
332 blist.splice(blist.end(),*ca->my_class);
334 classes.erase(ca->my_class);
343 * \brief Returns the size of the component of element \e a.
345 * Returns the size of the component of element \e a.
348 int size(const T &a) const {
349 return _find(m[a])->size;
354 * \brief Split up the component of the element.
356 * Splitting the component of the element into sigleton
357 * components (component of size one).
360 void split(const T &a) {
362 IIter ca = _find(m[a]);
367 CIter aclass = ca->my_class;
369 for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
370 classes.push_back(ItemList());
371 CIter nl = --classes.end();
372 nl->splice(nl->end(), *aclass, curr);
385 * \brief Set the given element to the leader element of its component.
387 * Set the given element to the leader element of its component.
390 void makeRep(const T &a) {
393 IIter la = _find(ia);
394 if (la == ia) return;
396 ia->my_class = la->my_class;
401 CIter l = ia->my_class;
402 l->splice(l->begin(),*l,ia);
409 * \brief Move the given element to an other component.
411 * This method moves the element \e a from its component
412 * to the component of \e comp.
413 * If \e a and \e comp are in the same component then
414 * it returns false otherwise it returns true.
417 bool move(const T &a, const T &comp) {
420 IIter lai = _find(ai);
421 IIter clit = _find(m[comp]);
426 ItemList &c = *clit->my_class;
428 bool is_leader = (lai == ai);
429 bool singleton = false;
435 c.splice(c.end(), *lai->my_class, ai);
439 classes.erase(ai->my_class);
443 lai->size = ai->size;
444 lai->my_class = ai->my_class;
448 for (IIter i = lai; i != lai->my_class->end(); ++i)
462 * \brief Remove the given element from the structure.
464 * Remove the given element from the structure.
466 * Removes the element from its component and if the component becomes
467 * empty then removes that component from the component list.
469 void erase(const T &a) {
474 IIter la = _find(ma);
476 if (ma -> size == 1){
477 classes.erase(ma->my_class);
483 la->my_class = ma->my_class;
486 for (IIter i = la; i != la->my_class->end(); ++i) {
491 la->my_class->erase(ma);
496 * \brief Removes the component of the given element from the structure.
498 * Removes the component of the given element from the structure.
501 void eraseClass(const T &a) {
505 CIter c = _find(ma)->my_class;
506 for (IIter i=c->begin(); i!=c->end(); ++i)
509 classes.erase(_find(ma)->my_class);
514 friend class UnionFindEnum;
518 ClassIt(Invalid): i(0) {}
521 operator const T& () const {
522 ItemList const &ll = *i;
523 return (ll.begin())->me; }
524 bool operator == (ClassIt it) const {
527 bool operator != (ClassIt it) const {
530 bool operator < (ClassIt it) const {
534 bool valid() const { return i != 0; }
536 void first(const ClassList &l) { i = l.begin(); validate(l); }
537 void next(const ClassList &l) {
541 void validate(const ClassList &l) {
548 * \brief Sets the iterator to point to the first component.
550 * Sets the iterator to point to the first component.
552 * With the \ref first, \ref valid and \ref next methods you can
553 * iterate through the components. For example:
555 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
556 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
557 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
558 * for (U.first(iter); U.valid(iter); U.next(iter)) {
559 * // iter is convertible to Graph::Node
560 * cout << iter << endl;
565 ClassIt& first(ClassIt& it) const {
571 * \brief Returns whether the iterator is valid.
573 * Returns whether the iterator is valid.
575 * With the \ref first, \ref valid and \ref next methods you can
576 * iterate through the components. See the example here: \ref first.
579 bool valid(ClassIt const &it) const {
584 * \brief Steps the iterator to the next component.
586 * Steps the iterator to the next component.
588 * With the \ref first, \ref valid and \ref next methods you can
589 * iterate through the components. See the example here: \ref first.
592 ClassIt& next(ClassIt& it) const {
599 friend class UnionFindEnum;
604 ItemIt(Invalid): i(0) {}
607 operator const T& () const { return i->me; }
608 bool operator == (ItemIt it) const {
611 bool operator != (ItemIt it) const {
614 bool operator < (ItemIt it) const {
618 bool valid() const { return i != 0; }
620 void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
634 * \brief Sets the iterator to point to the first element of the component.
637 * Sets the iterator to point to the first element of the component.
639 * With the \ref first2 "first", \ref valid2 "valid"
640 * and \ref next2 "next" methods you can
641 * iterate through the elements of a component. For example
642 * (iterating through the component of the node \e node):
644 * Graph::Node node = ...;
645 * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
646 * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
647 * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
648 * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
649 * // iiter is convertible to Graph::Node
650 * cout << iiter << endl;
655 ItemIt& first(ItemIt& it, const T& a) const {
656 it.first( * _find(m[a])->my_class );
661 * \brief Returns whether the iterator is valid.
664 * Returns whether the iterator is valid.
666 * With the \ref first2 "first", \ref valid2 "valid"
667 * and \ref next2 "next" methods you can
668 * iterate through the elements of a component.
669 * See the example here: \ref first2 "first".
672 bool valid(ItemIt const &it) const {
677 * \brief Steps the iterator to the next component.
680 * Steps the iterator to the next component.
682 * With the \ref first2 "first", \ref valid2 "valid"
683 * and \ref next2 "next" methods you can
684 * iterate through the elements of a component.
685 * See the example here: \ref first2 "first".
688 ItemIt& next(ItemIt& it) const {
700 #endif //HUGO_UNION_FIND_H