COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 1996:5dc13b93f8b4

Last change on this file since 1996:5dc13b93f8b4 was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

File size: 16.7 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  public:
261    UnionFindEnum(MapType& _m) : m(_m) {}
262
263
264    /**
265     * \brief Inserts the given element into a new component.
266     *
267     * This method creates a new component consisting only of the
268     * given element.
269     */
270
271    void insert(const T &a)
272    {
273
274
275      classes.push_back(ItemList());
276      CIter aclass = classes.end();
277      --aclass;
278
279      ItemList &alist = *aclass;
280      alist.push_back(ItemType(a, aclass));
281      IIter ai = alist.begin();
282
283      ai->parent = ai;
284      m.set(a, ai);
285
286    }
287
288    /**
289     * \brief Inserts the given element into the component of the others.
290     *
291     * This methods inserts the element \e a into the component of the
292     * element \e comp.
293     */
294
295    void insert(const T &a, const T &comp) {
296     
297      IIter clit = _find(m[comp]);
298      ItemList &c = *clit->my_class;
299      c.push_back(ItemType(a,0));
300      IIter ai = c.end();
301      --ai;
302      ai->parent = clit;
303      m.set(a, ai);
304      ++clit->size;
305    }
306
307
308    /**
309     * \brief Finds the leader of the component of the given element.
310     *
311     * The method returns the leader of the component of the given element.
312     */
313
314    T find(const T &a) const {
315      return _find(m[a])->me;
316    }
317
318
319    /**
320     * \brief Joining the component of element \e a and element \e b.
321     *
322     * This is the \e union operation of the Union-Find structure.
323     * Joins the component of element \e a and component of
324     * element \e b. If \e a and \e b are in the same component then
325     * returns false else returns true.
326     */
327
328    bool join(T a, T b) {
329
330      IIter ca = _find(m[a]);
331      IIter cb = _find(m[b]);
332
333      if ( ca == cb ) {
334        return false;
335      }
336
337      if ( ca->size > cb->size ) {
338
339        cb->parent = ca->parent;
340        ca->size += cb->size;
341       
342        ItemList &alist = *ca->my_class;
343        alist.splice(alist.end(),*cb->my_class);
344
345        classes.erase(cb->my_class);
346        cb->my_class = 0;
347      }
348      else {
349
350        ca->parent = cb->parent;
351        cb->size += ca->size;
352       
353        ItemList &blist = *cb->my_class;
354        blist.splice(blist.end(),*ca->my_class);
355
356        classes.erase(ca->my_class);
357        ca->my_class = 0;
358      }
359
360      return true;
361    }
362
363
364    /**
365     * \brief Returns the size of the component of element \e a.
366     *
367     * Returns the size of the component of element \e a.
368     */
369
370    int size(const T &a) const {
371      return _find(m[a])->size;
372    }
373
374
375    /**
376     * \brief Splits up the component of the element.
377     *
378     * Splitting the component of the element into sigleton
379     * components (component of size one).
380     */
381
382    void split(const T &a) {
383
384      IIter ca = _find(m[a]);
385 
386      if ( ca->size == 1 )
387        return;
388     
389      CIter aclass = ca->my_class;
390
391      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
392        classes.push_back(ItemList());
393        CIter nl = --classes.end();
394        nl->splice(nl->end(), *aclass, curr);
395
396        curr->size=1;
397        curr->parent=curr;
398        curr->my_class = nl;
399      }
400
401      ca->size=1;
402      return;
403    }
404
405
406    /**
407     * \brief Sets the given element to the leader element of its component.
408     *
409     * Sets the given element to the leader element of its component.
410     */
411
412    void makeRep(const T &a) {
413
414      IIter ia = m[a];
415      IIter la = _find(ia);
416      if (la == ia) return;
417
418      ia->my_class = la->my_class;
419      la->my_class = 0;
420
421      ia->size = la->size;
422
423      CIter l = ia->my_class;
424      l->splice(l->begin(),*l,ia);
425
426      ia->parent = ia;
427      la->parent = ia;
428    }
429
430    /**
431     * \brief Moves the given element to an other component.
432     *
433     * This method moves the element \e a from its component
434     * to the component of \e comp.
435     * If \e a and \e comp are in the same component then
436     * it returns false otherwise it returns true.
437     */
438
439    bool move(const T &a, const T &comp) {
440
441      IIter ai = m[a];
442      IIter lai = _find(ai);
443      IIter clit = _find(m[comp]);
444
445      if (lai == clit)
446        return false;
447
448      ItemList &cl = *clit->my_class,
449        &al = *lai->my_class;
450
451      bool is_leader = (lai == ai);
452      bool singleton = false;
453
454      if (is_leader) {
455        ++lai;
456      }
457
458      cl.splice(cl.end(), al, ai);
459
460      if (is_leader) {
461        if (ai->size == 1) {
462          classes.erase(ai->my_class);
463          singleton = true;
464        }
465        else {
466          lai->size = ai->size;
467          lai->my_class = ai->my_class;
468        }
469      }
470      if (!singleton) {
471        for (IIter i = lai; i != al.end(); ++i)
472          i->parent = lai;
473        --lai->size;
474      }
475
476      ai->parent = clit;
477      ai->my_class = 0;
478      ++clit->size;
479
480      return true;
481    }
482
483
484    /**
485     * \brief Removes the given element from the structure.
486     *
487     * Removes the given element from the structure.
488     *
489     * Removes the element from its component and if the component becomes
490     * empty then removes that component from the component list.
491     */
492    void erase(const T &a) {
493
494      IIter ma = m[a];
495      if (ma == 0) return;
496
497      IIter la = _find(ma);
498      if (la == ma) {
499        if (ma -> size == 1){
500          classes.erase(ma->my_class);
501          m.set(a,0);
502          return;
503        }
504        ++la;
505        la->size = ma->size;
506        la->my_class = ma->my_class;   
507      }
508
509      for (IIter i = la; i != la->my_class->end(); ++i) {
510        i->parent = la;
511      }
512
513      la->size--;
514      la->my_class->erase(ma);
515      m.set(a,0);
516    }
517
518    /**
519     * \brief Removes the component of the given element from the structure.
520     *
521     * Removes the component of the given element from the structure.
522     */
523
524    void eraseClass(const T &a) {
525      IIter ma = m[a];
526      if (ma == 0) return;
527#     ifdef DEBUG
528      CIter c = _find(ma)->my_class;
529      for (IIter i=c->begin(); i!=c->end(); ++i)
530        m.set(i->me, 0);
531#     endif
532      classes.erase(_find(ma)->my_class);
533    }
534
535
536    class ClassIt {
537      friend class UnionFindEnum;
538
539      CcIter i;
540    public:
541      ClassIt(Invalid): i(0) {}
542      ClassIt() {}
543     
544      operator const T& () const {
545        ItemList const &ll = *i;
546        return (ll.begin())->me; }
547      bool operator == (ClassIt it) const {
548        return (i == it.i);
549      }
550      bool operator != (ClassIt it) const {
551        return (i != it.i);
552      }
553      bool operator < (ClassIt it) const {
554        return (i < it.i);
555      }
556
557      bool valid() const { return i != 0; }
558    private:
559      void first(const ClassList &l) { i = l.begin(); validate(l); }
560      void next(const ClassList &l) {
561        ++i;
562        validate(l);
563      }
564      void validate(const ClassList &l) {
565        if ( i == l.end() )
566          i = 0;
567      }
568    };
569
570    /**
571     * \brief Sets the iterator to point to the first component.
572     *
573     * Sets the iterator to point to the first component.
574     *
575     * With the \ref first, \ref valid and \ref next methods you can
576     * iterate through the components. For example:
577     * \code
578     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
579     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
580     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
581     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
582     *    // iter is convertible to Graph::Node
583     *    cout << iter << endl;
584     *  }
585     * \endcode
586     */
587
588    ClassIt& first(ClassIt& it) const {
589      it.first(classes);
590      return it;
591    }
592
593    /**
594     * \brief Returns whether the iterator is valid.
595     *
596     * Returns whether the iterator is valid.
597     *
598     * With the \ref first, \ref valid and \ref next methods you can
599     * iterate through the components. See the example here: \ref first.
600     */
601
602    bool valid(ClassIt const &it) const {
603      return it.valid();
604    }
605
606    /**
607     * \brief Steps the iterator to the next component.
608     *
609     * Steps the iterator to the next component.
610     *
611     * With the \ref first, \ref valid and \ref next methods you can
612     * iterate through the components. See the example here: \ref first.
613     */
614
615    ClassIt& next(ClassIt& it) const {
616      it.next(classes);
617      return it;
618    }
619
620
621    class ItemIt {
622      friend class UnionFindEnum;
623
624      IcIter i;
625      const ItemList *l;
626    public:
627      ItemIt(Invalid): i(0) {}
628      ItemIt() {}
629     
630      operator const T& () const { return i->me; }
631      bool operator == (ItemIt it) const {
632        return (i == it.i);
633      }
634      bool operator != (ItemIt it) const {
635        return (i != it.i);
636      }
637      bool operator < (ItemIt it) const {
638        return (i < it.i);
639      }
640
641      bool valid() const { return i != 0; }
642    private:
643      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
644      void next() {
645        ++i;
646        validate();
647      }
648      void validate() {
649        if ( i == l->end() )
650          i = 0;
651      }
652    };
653
654
655
656    /**
657     * \brief Sets the iterator to point to the first element of the component.
658     *
659     * \anchor first2
660     * Sets the iterator to point to the first element of the component.
661     *
662     * With the \ref first2 "first", \ref valid2 "valid"
663     * and \ref next2 "next" methods you can
664     * iterate through the elements of a component. For example
665     * (iterating through the component of the node \e node):
666     * \code
667     * Graph::Node node = ...;
668     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
669     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
670     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
671     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
672     *     // iiter is convertible to Graph::Node
673     *     cout << iiter << endl;
674     *   }
675     * \endcode
676     */
677   
678    ItemIt& first(ItemIt& it, const T& a) const {
679      it.first( * _find(m[a])->my_class );
680      return it;
681    }
682
683    /**
684     * \brief Returns whether the iterator is valid.
685     *
686     * \anchor valid2
687     * Returns whether the iterator is valid.
688     *
689     * With the \ref first2 "first", \ref valid2 "valid"
690     * and \ref next2 "next" methods you can
691     * iterate through the elements of a component.
692     * See the example here: \ref first2 "first".
693     */
694
695    bool valid(ItemIt const &it) const {
696      return it.valid();
697    }
698
699    /**
700     * \brief Steps the iterator to the next component.
701     *
702     * \anchor next2
703     * Steps the iterator to the next component.
704     *
705     * With the \ref first2 "first", \ref valid2 "valid"
706     * and \ref next2 "next" methods you can
707     * iterate through the elements of a component.
708     * See the example here: \ref first2 "first".
709     */
710
711    ItemIt& next(ItemIt& it) const {
712      it.next();
713      return it;
714    }
715   
716  };
717
718
719  //! @}
720
721} //namespace lemon
722
723#endif //LEMON_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.