COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 1463:e8d27c74bd3b

Last change on this file since 1463:e8d27c74bd3b was 1435:8e85e6bbefdf, checked in by Akos Ladanyi, 19 years ago

trunk/src/* move to trunk/

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