COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/unionfind.h @ 462:0ab31578af67

Last change on this file since 462:0ab31578af67 was 462:0ab31578af67, checked in by beckerjc, 17 years ago

Doc for the union-find structures.

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