COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/unionfind.h @ 649:ce74706e924d

Last change on this file since 649:ce74706e924d was 649:ce74706e924d, checked in by athos, 16 years ago

Cooorected some eroorrs.

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