COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 2003:cf012a7c7f69

Last change on this file since 2003:cf012a7c7f69 was 2003:cf012a7c7f69, checked in by Mihaly Barasz, 14 years ago

UnionFindEnum? revision:

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