COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/unionfind.h @ 906:17f31d280385

Last change on this file since 906:17f31d280385 was 906:17f31d280385, checked in by Alpar Juttner, 20 years ago

Copyright header added.

File size: 16.8 KB
Line 
1/* -*- C++ -*-
2 * src/hugo/unionfind.h - Part of HUGOlib, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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 HUGO_UNION_FIND_H
18#define HUGO_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 <hugo/invalid.h>
34
35namespace hugo {
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 Insert 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 elemenent \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 Insert 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 Insert the given element into the component of the others.
291     *
292     * This methods insert 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 Find 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 elemenent \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 Split 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 Set the given element to the leader element of its component.
409     *
410     * Set 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 Move 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 &c = *clit->my_class;
450
451      bool is_leader = (lai == ai);
452      bool singleton = false;
453
454      if (is_leader) {
455        ++lai;
456      }
457
458      c.splice(c.end(), *lai->my_class, 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 != lai->my_class->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 Remove the given element from the structure.
486     *
487     * Remove 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 hugo
722
723#endif //HUGO_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.