COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 2193:8057a4245685

Last change on this file since 2193:8057a4245685 was 2006:00d59f733817, checked in by Alpar Juttner, 18 years ago

Spellcheck

File size: 17.3 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,CIter()));
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      }
351      else {
352
353        ca->parent = cb->parent;
354        cb->size += ca->size;
355       
356        ItemList &blist = *cb->my_class;
357        blist.splice(blist.end(),*ca->my_class);
358
359        classes.erase(ca->my_class);
360      }
361
362      return true;
363    }
364
365
366    /**
367     * \brief Returns the size of the component of element \e a.
368     *
369     * Returns the size of the component of element \e a.
370     */
371
372    int size(const T &a) const {
373      return _find(m[a])->size;
374    }
375
376
377    /**
378     * \brief Splits up the component of the element.
379     *
380     * Splitting the component of the element into sigleton
381     * components (component of size one).
382     */
383
384    void split(const T &a) {
385
386      IIter ca = _find(m[a]);
387 
388      if ( ca->size == 1 )
389        return;
390     
391      CIter aclass = ca->my_class;
392
393      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
394        classes.push_back(ItemList());
395        CIter nl = --classes.end();
396        nl->splice(nl->end(), *aclass, curr);
397
398        curr->size=1;
399        curr->parent=curr;
400        curr->my_class = nl;
401      }
402
403      ca->size=1;
404      return;
405    }
406
407
408    /**
409     * \brief Sets the given element to the leader element of its component.
410     *
411     * Sets the given element to the leader element of its component.
412     */
413
414    void makeRep(const T &a) {
415
416      IIter ia = m[a];
417      IIter la = _find(ia);
418      if (la == ia) return;
419
420      ia->my_class = la->my_class;
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 another 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      ++clit->size;
479
480      return true;
481    }
482
483
484    /**
485     * \brief 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     * It is an error to remove an element which is not in the structure.
491     */
492    void erase(const T &a) {
493
494      IIter ma = m[a];
495
496      IIter la = _find(ma);
497      if (la == ma) {
498        if (ma -> size == 1){
499          classes.erase(ma->my_class);
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    }
514
515    /**
516     * \brief Removes the component of the given element from the structure.
517     *
518     * Removes the component of the given element from the structure.
519     *
520     * It is an error to give an element which is not in the structure.
521     */
522
523    void eraseClass(const T &a) {
524      IIter ma = m[a];
525      classes.erase(_find(ma)->my_class);
526    }
527
528
529    class ClassIt {
530      friend class UnionFindEnum;
531
532      CcIter i;
533      const ClassList *l;
534
535    public:
536      ClassIt(Invalid): l(0) {}
537      ClassIt() {}
538      ClassIt(UnionFindEnum const &ufe) {
539        l = &ufe.classes;
540        i = l->begin();
541      }
542     
543      operator const T& () const {
544        ItemList const &ll = *i;
545        return (ll.begin())->me;
546      }
547      bool operator == (ClassIt const &it) const {
548        return (l==it.l && i==it.i) || (!valid() && !it.valid());
549      }
550      bool operator != (ClassIt const &it) const {
551        return !(*this == it);
552      }
553      bool operator < (ClassIt const &it) const {
554        return (i < it.i);
555      }
556
557      bool operator==(Invalid) const {
558        return !valid();
559      }
560      bool operator!=(Invalid) const {
561        return valid();
562      }
563
564      ClassIt& operator++() {
565        ++i;
566        return *this;
567      }
568
569      // obsoleted:
570      bool valid() const { return l!=0 && i!=l->end(); }
571    };
572
573    /**
574     * \brief Sets the iterator to point to the first component.
575     *
576     * Sets the iterator to point to the first component.
577     *
578     * With the \ref first, \ref valid and \ref next methods you can
579     * iterate through the components. For example:
580     * \code
581     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
582     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
583     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
584     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
585     *    // iter is convertible to Graph::Node
586     *    cout << iter << endl;
587     *  }
588     * \endcode
589     *
590     * \bug obsoleted, use the new LEMON iterator interface instead
591     */
592
593    ClassIt& first(ClassIt& it) const {
594      it = ClassIt(*this);
595      return it;
596    }
597
598    /**
599     * \brief Returns whether the iterator is valid.
600     *
601     * Returns whether the iterator is valid.
602     *
603     * With the \ref first, \ref valid and \ref next methods you can
604     * iterate through the components. See the example here: \ref first.
605     *
606     * \bug obsoleted, use the new LEMON iterator interface instead
607     */
608
609    bool valid(ClassIt const &it) const {
610      return it.valid();
611    }
612
613    /**
614     * \brief Steps the iterator to the next component.
615     *
616     * Steps the iterator to the next component.
617     *
618     * With the \ref first, \ref valid and \ref next methods you can
619     * iterate through the components. See the example here: \ref first.
620     */
621
622    ClassIt& next(ClassIt& it) const {
623      return ++it;
624    }
625
626
627    class ItemIt {
628      friend class UnionFindEnum;
629
630      IcIter i;
631      const ItemList *l;
632    public:
633      ItemIt(Invalid): l(0) {}
634      ItemIt() {}
635      ItemIt(UnionFindEnum const &ufe, const T& a) {
636        l = &ufe.classOf(a);
637        i = l->begin();
638      }
639     
640      operator const T& () const { return i->me; }
641      bool operator == (ItemIt const &it) const {
642        return (l==it.l && i==it.i) || (!valid() && !it.valid());
643      }
644      bool operator != (ItemIt const &it) const {
645        return !(*this == it);
646      }
647      bool operator < (ItemIt const &it) const {
648        return (i < it.i);
649      }
650
651      bool operator==(Invalid) const {
652        return !valid();
653      }
654      bool operator!=(Invalid) const {
655        return valid();
656      }
657
658      ItemIt& operator++() {
659        ++i;
660        return *this;
661      }
662
663      // obsoleted:
664      bool valid() const { return l!=0 && i!=l->end(); }
665    };
666
667
668
669    /**
670     * \brief Sets the iterator to point to the first element of the component.
671     *
672     * \anchor first2
673     * Sets the iterator to point to the first element of the component.
674     *
675     * With the \ref first2 "first", \ref valid2 "valid"
676     * and \ref next2 "next" methods you can
677     * iterate through the elements of a component. For example
678     * (iterating through the component of the node \e node):
679     * \code
680     * Graph::Node node = ...;
681     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
682     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
683     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
684     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
685     *     // iiter is convertible to Graph::Node
686     *     cout << iiter << endl;
687     *   }
688     * \endcode
689     *
690     * \bug obsoleted, use the new LEMON iterator interface instead
691     */
692   
693    ItemIt& first(ItemIt& it, const T& a) const {
694      it = ItemIt(*this, a);
695      return it;
696    }
697
698    /**
699     * \brief Returns whether the iterator is valid.
700     *
701     * \anchor valid2
702     * Returns whether the iterator is valid.
703     *
704     * With the \ref first2 "first", \ref valid2 "valid"
705     * and \ref next2 "next" methods you can
706     * iterate through the elements of a component.
707     * See the example here: \ref first2 "first".
708     *
709     * \bug obsoleted, use the new LEMON iterator interface instead
710     */
711
712    bool valid(ItemIt const &it) const {
713      return it.valid();
714    }
715
716    /**
717     * \brief Steps the iterator to the next component.
718     *
719     * \anchor next2
720     * Steps the iterator to the next component.
721     *
722     * With the \ref first2 "first", \ref valid2 "valid"
723     * and \ref next2 "next" methods you can
724     * iterate through the elements of a component.
725     * See the example here: \ref first2 "first".
726     *
727     * \bug obsoleted, use the new LEMON iterator interface instead
728     */
729
730    ItemIt& next(ItemIt& it) const {
731      return ++it;
732    }
733   
734  };
735
736
737  //! @}
738
739} //namespace lemon
740
741#endif //LEMON_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.