COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/unionfind.h @ 774:4297098d9677

Last change on this file since 774:4297098d9677 was 774:4297098d9677, checked in by Alpar Juttner, 16 years ago

Merge back the whole branches/hugo++ to trunk.

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