COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 1865:dcefd1d1377f

Last change on this file since 1865:dcefd1d1377f was 1779:f6cafba4dbf2, checked in by Alpar Juttner, 14 years ago

Obsolete bug removed

File size: 16.7 KB
Line 
1/* -*- C++ -*-
2 * lemon/unionfind.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_UNION_FIND_H
18#define LEMON_UNION_FIND_H
19
20//!\ingroup auxdat
21//!\file
22//!\brief Union-Find data structures.
23//!
24
25#include <vector>
26#include <list>
27#include <utility>
28#include <algorithm>
29
30#include <lemon/invalid.h>
31
32namespace lemon {
33
34  //! \addtogroup auxdat
35  //! @{
36
37  /**
38   * \brief A \e Union-Find data structure implementation
39   *
40   * The class implements the \e Union-Find data structure.
41   * The union operation uses rank heuristic, while
42   * the find operation uses path compression.
43   * This is a very simple but efficient implementation, providing
44   * only four methods: join (union), find, insert and size.
45   * For more features see the \ref UnionFindEnum class.
46   *
47   * It is primarily used in Kruskal algorithm for finding minimal
48   * cost spanning tree in a graph.
49   * \sa kruskal()
50   *
51   * \pre The elements are automatically added only if the map
52   * given to the constructor was filled with -1's. Otherwise you
53   * need to add all the elements by the \ref insert() method.
54   * \bug It is not clear what the constructor parameter is used for.
55   */
56
57  template <typename T, typename TIntMap>
58  class UnionFind {
59   
60  public:
61    typedef T ElementType;
62    typedef std::pair<int,int> PairType;
63
64  private:
65    std::vector<PairType> data;
66    TIntMap& map;
67
68  public:
69    UnionFind(TIntMap& m) : map(m) {}
70
71    /**
72     * \brief Returns the index of the element's component.
73     *
74     * The method returns the index of the element's component.
75     * This is an integer between zero and the number of inserted elements.
76     */
77
78    int find(T a)
79    {
80      int comp0 = map[a];
81      if (comp0 < 0) {
82        return insert(a);
83      }
84      int comp = comp0;
85      int next;
86      while ( (next = data[comp].first) != comp) {
87        comp = next;
88      }
89      while ( (next = data[comp0].first) != comp) {
90        data[comp0].first = comp;
91        comp0 = next;
92      }
93
94      return comp;
95    }
96
97    /**
98     * \brief Inserts a new element into the structure.
99     *
100     * This method inserts a new element into the data structure.
101     *
102     * It is not required to use this method:
103     * if the map given to the constructor was filled
104     * with -1's then it is called automatically
105     * on the first \ref find or \ref join.
106     *
107     * The method returns the index of the new component.
108     */
109
110    int insert(T a)
111    {
112      int n = data.size();
113      data.push_back(std::make_pair(n, 1));
114      map.set(a,n);
115      return n;
116    }
117
118    /**
119     * \brief Joining the components of element \e a and element \e b.
120     *
121     * This is the \e union operation of the Union-Find structure.
122     * Joins the component of element \e a and component of
123     * element \e b. If \e a and \e b are in the same component then
124     * it returns false otherwise it returns true.
125     */
126
127    bool join(T a, T b)
128    {
129      int ca = find(a);
130      int cb = find(b);
131
132      if ( ca == cb )
133        return false;
134
135      if ( data[ca].second > data[cb].second ) {
136        data[cb].first = ca;
137        data[ca].second += data[cb].second;
138      }
139      else {
140        data[ca].first = cb;
141        data[cb].second += data[ca].second;
142      }
143      return true;
144    }
145
146    /**
147     * \brief Returns the size of the component of element \e a.
148     *
149     * Returns the size of the component of element \e a.
150     */
151
152    int size(T a)
153    {
154      int ca = find(a);
155      return data[ca].second;
156    }
157
158  };
159
160
161
162
163  /*******************************************************/
164
165
166#ifdef DEVELOPMENT_DOCS
167
168  /**
169   * \brief The auxiliary class for the \ref UnionFindEnum class.
170   *
171   * In the \ref UnionFindEnum class all components are represented as
172   * a std::list.
173   * Items of these lists are UnionFindEnumItem structures.
174   *
175   * The class has four fields:
176   *  - T me - the actual element
177   *  - IIter parent - the parent of the element in the union-find structure
178   *  - int size - the size of the component of the element.
179   *            Only valid if the element
180   *            is the leader of the component.
181   *  - CIter my_class - pointer into the list of components
182   *            pointing to the component of the element.
183   *            Only valid if the element is the leader of the component.
184   */
185
186#endif
187
188  template <typename T>
189  struct UnionFindEnumItem {
190
191    typedef std::list<UnionFindEnumItem> ItemList;
192    typedef std::list<ItemList> ClassList;
193    typedef typename ItemList::iterator IIter;
194    typedef typename ClassList::iterator CIter;
195
196    T me;
197    IIter parent;
198    int size;
199    CIter my_class;
200
201    UnionFindEnumItem() {}
202    UnionFindEnumItem(const T &_me, CIter _my_class):
203      me(_me), size(1), my_class(_my_class) {}
204  };
205
206
207  /**
208   * \brief A \e Union-Find data structure implementation which
209   * is able to enumerate the components.
210   *
211   * The class implements a \e Union-Find data structure
212   * which is able to enumerate the components and the items in
213   * a component. If you don't need this feature then perhaps it's
214   * better to use the \ref UnionFind class which is more efficient.
215   *
216   * The union operation uses rank heuristic, while
217   * the find operation uses path compression.
218   *
219   * \pre You
220   * need to add all the elements by the \ref insert() method.
221   */
222
223
224  template <typename T, template <typename Item> class Map>
225  class UnionFindEnum {
226
227    typedef std::list<UnionFindEnumItem<T> > ItemList;
228    typedef std::list<ItemList> ClassList;
229    typedef typename ItemList::iterator IIter;
230    typedef typename ItemList::const_iterator IcIter;
231    typedef typename ClassList::iterator CIter;
232    typedef typename ClassList::const_iterator CcIter;
233
234  public:
235    typedef T ElementType;
236    typedef UnionFindEnumItem<T> ItemType;
237    typedef Map< IIter > MapType;
238
239  private:
240    MapType& m;
241    ClassList classes;
242
243    IIter _find(IIter a) const {
244      IIter comp = a;
245      IIter next;
246      while( (next = comp->parent) != comp ) {
247        comp = next;
248      }
249
250      IIter comp1 = a;
251      while( (next = comp1->parent) != comp ) {
252        comp1->parent = comp->parent;
253        comp1 = next;
254      }
255      return comp;
256    }
257
258  public:
259    UnionFindEnum(MapType& _m) : m(_m) {}
260
261
262    /**
263     * \brief Inserts the given element into a new component.
264     *
265     * This method creates a new component consisting only of the
266     * given element.
267     */
268
269    void insert(const T &a)
270    {
271
272
273      classes.push_back(ItemList());
274      CIter aclass = classes.end();
275      --aclass;
276
277      ItemList &alist = *aclass;
278      alist.push_back(ItemType(a, aclass));
279      IIter ai = alist.begin();
280
281      ai->parent = ai;
282      m.set(a, ai);
283
284    }
285
286    /**
287     * \brief Inserts the given element into the component of the others.
288     *
289     * This methods inserts the element \e a into the component of the
290     * element \e comp.
291     */
292
293    void insert(const T &a, const T &comp) {
294     
295      IIter clit = _find(m[comp]);
296      ItemList &c = *clit->my_class;
297      c.push_back(ItemType(a,0));
298      IIter ai = c.end();
299      --ai;
300      ai->parent = clit;
301      m.set(a, ai);
302      ++clit->size;
303    }
304
305
306    /**
307     * \brief Finds the leader of the component of the given element.
308     *
309     * The method returns the leader of the component of the given element.
310     */
311
312    T find(const T &a) const {
313      return _find(m[a])->me;
314    }
315
316
317    /**
318     * \brief Joining the component of element \e a and element \e b.
319     *
320     * This is the \e union operation of the Union-Find structure.
321     * Joins the component of element \e a and component of
322     * element \e b. If \e a and \e b are in the same component then
323     * returns false else returns true.
324     */
325
326    bool join(T a, T b) {
327
328      IIter ca = _find(m[a]);
329      IIter cb = _find(m[b]);
330
331      if ( ca == cb ) {
332        return false;
333      }
334
335      if ( ca->size > cb->size ) {
336
337        cb->parent = ca->parent;
338        ca->size += cb->size;
339       
340        ItemList &alist = *ca->my_class;
341        alist.splice(alist.end(),*cb->my_class);
342
343        classes.erase(cb->my_class);
344        cb->my_class = 0;
345      }
346      else {
347
348        ca->parent = cb->parent;
349        cb->size += ca->size;
350       
351        ItemList &blist = *cb->my_class;
352        blist.splice(blist.end(),*ca->my_class);
353
354        classes.erase(ca->my_class);
355        ca->my_class = 0;
356      }
357
358      return true;
359    }
360
361
362    /**
363     * \brief Returns the size of the component of element \e a.
364     *
365     * Returns the size of the component of element \e a.
366     */
367
368    int size(const T &a) const {
369      return _find(m[a])->size;
370    }
371
372
373    /**
374     * \brief Splits up the component of the element.
375     *
376     * Splitting the component of the element into sigleton
377     * components (component of size one).
378     */
379
380    void split(const T &a) {
381
382      IIter ca = _find(m[a]);
383 
384      if ( ca->size == 1 )
385        return;
386     
387      CIter aclass = ca->my_class;
388
389      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
390        classes.push_back(ItemList());
391        CIter nl = --classes.end();
392        nl->splice(nl->end(), *aclass, curr);
393
394        curr->size=1;
395        curr->parent=curr;
396        curr->my_class = nl;
397      }
398
399      ca->size=1;
400      return;
401    }
402
403
404    /**
405     * \brief Sets the given element to the leader element of its component.
406     *
407     * Sets the given element to the leader element of its component.
408     */
409
410    void makeRep(const T &a) {
411
412      IIter ia = m[a];
413      IIter la = _find(ia);
414      if (la == ia) return;
415
416      ia->my_class = la->my_class;
417      la->my_class = 0;
418
419      ia->size = la->size;
420
421      CIter l = ia->my_class;
422      l->splice(l->begin(),*l,ia);
423
424      ia->parent = ia;
425      la->parent = ia;
426    }
427
428    /**
429     * \brief Moves the given element to an other component.
430     *
431     * This method moves the element \e a from its component
432     * to the component of \e comp.
433     * If \e a and \e comp are in the same component then
434     * it returns false otherwise it returns true.
435     */
436
437    bool move(const T &a, const T &comp) {
438
439      IIter ai = m[a];
440      IIter lai = _find(ai);
441      IIter clit = _find(m[comp]);
442
443      if (lai == clit)
444        return false;
445
446      ItemList &cl = *clit->my_class,
447        &al = *lai->my_class;
448
449      bool is_leader = (lai == ai);
450      bool singleton = false;
451
452      if (is_leader) {
453        ++lai;
454      }
455
456      cl.splice(cl.end(), al, ai);
457
458      if (is_leader) {
459        if (ai->size == 1) {
460          classes.erase(ai->my_class);
461          singleton = true;
462        }
463        else {
464          lai->size = ai->size;
465          lai->my_class = ai->my_class;
466        }
467      }
468      if (!singleton) {
469        for (IIter i = lai; i != al.end(); ++i)
470          i->parent = lai;
471        --lai->size;
472      }
473
474      ai->parent = clit;
475      ai->my_class = 0;
476      ++clit->size;
477
478      return true;
479    }
480
481
482    /**
483     * \brief Removes the given element from the structure.
484     *
485     * Removes the given element from the structure.
486     *
487     * Removes the element from its component and if the component becomes
488     * empty then removes that component from the component list.
489     */
490    void erase(const T &a) {
491
492      IIter ma = m[a];
493      if (ma == 0) return;
494
495      IIter la = _find(ma);
496      if (la == ma) {
497        if (ma -> size == 1){
498          classes.erase(ma->my_class);
499          m.set(a,0);
500          return;
501        }
502        ++la;
503        la->size = ma->size;
504        la->my_class = ma->my_class;   
505      }
506
507      for (IIter i = la; i != la->my_class->end(); ++i) {
508        i->parent = la;
509      }
510
511      la->size--;
512      la->my_class->erase(ma);
513      m.set(a,0);
514    }
515
516    /**
517     * \brief Removes the component of the given element from the structure.
518     *
519     * Removes the component of the given element from the structure.
520     */
521
522    void eraseClass(const T &a) {
523      IIter ma = m[a];
524      if (ma == 0) return;
525#     ifdef DEBUG
526      CIter c = _find(ma)->my_class;
527      for (IIter i=c->begin(); i!=c->end(); ++i)
528        m.set(i->me, 0);
529#     endif
530      classes.erase(_find(ma)->my_class);
531    }
532
533
534    class ClassIt {
535      friend class UnionFindEnum;
536
537      CcIter i;
538    public:
539      ClassIt(Invalid): i(0) {}
540      ClassIt() {}
541     
542      operator const T& () const {
543        ItemList const &ll = *i;
544        return (ll.begin())->me; }
545      bool operator == (ClassIt it) const {
546        return (i == it.i);
547      }
548      bool operator != (ClassIt it) const {
549        return (i != it.i);
550      }
551      bool operator < (ClassIt it) const {
552        return (i < it.i);
553      }
554
555      bool valid() const { return i != 0; }
556    private:
557      void first(const ClassList &l) { i = l.begin(); validate(l); }
558      void next(const ClassList &l) {
559        ++i;
560        validate(l);
561      }
562      void validate(const ClassList &l) {
563        if ( i == l.end() )
564          i = 0;
565      }
566    };
567
568    /**
569     * \brief Sets the iterator to point to the first component.
570     *
571     * Sets the iterator to point to the first component.
572     *
573     * With the \ref first, \ref valid and \ref next methods you can
574     * iterate through the components. For example:
575     * \code
576     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
577     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
578     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
579     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
580     *    // iter is convertible to Graph::Node
581     *    cout << iter << endl;
582     *  }
583     * \endcode
584     */
585
586    ClassIt& first(ClassIt& it) const {
587      it.first(classes);
588      return it;
589    }
590
591    /**
592     * \brief Returns whether the iterator is valid.
593     *
594     * Returns whether the iterator is valid.
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    bool valid(ClassIt const &it) const {
601      return it.valid();
602    }
603
604    /**
605     * \brief Steps the iterator to the next component.
606     *
607     * Steps the iterator to the next component.
608     *
609     * With the \ref first, \ref valid and \ref next methods you can
610     * iterate through the components. See the example here: \ref first.
611     */
612
613    ClassIt& next(ClassIt& it) const {
614      it.next(classes);
615      return it;
616    }
617
618
619    class ItemIt {
620      friend class UnionFindEnum;
621
622      IcIter i;
623      const ItemList *l;
624    public:
625      ItemIt(Invalid): i(0) {}
626      ItemIt() {}
627     
628      operator const T& () const { return i->me; }
629      bool operator == (ItemIt it) const {
630        return (i == it.i);
631      }
632      bool operator != (ItemIt it) const {
633        return (i != it.i);
634      }
635      bool operator < (ItemIt it) const {
636        return (i < it.i);
637      }
638
639      bool valid() const { return i != 0; }
640    private:
641      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
642      void next() {
643        ++i;
644        validate();
645      }
646      void validate() {
647        if ( i == l->end() )
648          i = 0;
649      }
650    };
651
652
653
654    /**
655     * \brief Sets the iterator to point to the first element of the component.
656     *
657     * \anchor first2
658     * Sets the iterator to point to the first element of the component.
659     *
660     * With the \ref first2 "first", \ref valid2 "valid"
661     * and \ref next2 "next" methods you can
662     * iterate through the elements of a component. For example
663     * (iterating through the component of the node \e node):
664     * \code
665     * Graph::Node node = ...;
666     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
667     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
668     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
669     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
670     *     // iiter is convertible to Graph::Node
671     *     cout << iiter << endl;
672     *   }
673     * \endcode
674     */
675   
676    ItemIt& first(ItemIt& it, const T& a) const {
677      it.first( * _find(m[a])->my_class );
678      return it;
679    }
680
681    /**
682     * \brief Returns whether the iterator is valid.
683     *
684     * \anchor valid2
685     * Returns whether the iterator is valid.
686     *
687     * With the \ref first2 "first", \ref valid2 "valid"
688     * and \ref next2 "next" methods you can
689     * iterate through the elements of a component.
690     * See the example here: \ref first2 "first".
691     */
692
693    bool valid(ItemIt const &it) const {
694      return it.valid();
695    }
696
697    /**
698     * \brief Steps the iterator to the next component.
699     *
700     * \anchor next2
701     * Steps the iterator to the next component.
702     *
703     * With the \ref first2 "first", \ref valid2 "valid"
704     * and \ref next2 "next" methods you can
705     * iterate through the elements of a component.
706     * See the example here: \ref first2 "first".
707     */
708
709    ItemIt& next(ItemIt& it) const {
710      it.next();
711      return it;
712    }
713   
714  };
715
716
717  //! @}
718
719} //namespace lemon
720
721#endif //LEMON_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.