COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/unionfind.h @ 810:e9fbc747ca47

Last change on this file since 810:e9fbc747ca47 was 810:e9fbc747ca47, checked in by Alpar Juttner, 16 years ago

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