COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/unionfind.h @ 445:6fe0d7d70674

Last change on this file since 445:6fe0d7d70674 was 394:3a34c5626e52, checked in by beckerjc, 20 years ago

New union-find structure with enumerable classes.

File size: 6.9 KB
Line 
1// -*- c++ -*- //
2#ifndef HUGO_UNION_FIND_H
3#define HUGO_UNION_FIND_H
4
5#include <vector>
6#include <list>
7#include <utility>
8#include <algorithm>
9
10#include <invalid.h>
11
12namespace hugo {
13
14  template <typename T, typename TIntMap>
15  class UnionFind {
16   
17  public:
18    typedef T ElementType;
19    typedef std::pair<int,int> PairType;
20
21  private:
22    std::vector<PairType> data;
23    TIntMap& map;
24
25  public:
26    UnionFind(TIntMap& m) : map(m) {}
27
28
29    int find(T a)
30    {
31      int comp0 = map[a];
32      if (comp0 < 0) {
33        return insert(a);
34      }
35      int comp = comp0;
36      int next;
37      while ( (next = data[comp].first) != comp) {
38        comp = next;
39      }
40      while ( (next = data[comp0].first) != comp) {
41        data[comp0].first = comp;
42        comp0 = next;
43      }
44
45      return comp;
46    }
47
48    int insert(T a)
49    {
50      int n = data.size();
51      data.push_back(std::make_pair(n, 1));
52      map.set(a,n);
53      return n;
54    }
55
56    bool join(T a, T b)
57    {
58      int ca = find(a);
59      int cb = find(b);
60
61      if ( ca == cb )
62        return false;
63
64      if ( data[ca].second > data[cb].second ) {
65        data[cb].first = ca;
66        data[ca].second += data[cb].second;
67      }
68      else {
69        data[ca].first = cb;
70        data[cb].second += data[ca].second;
71      }
72      return true;
73    }
74
75    int size(T a)
76    {
77      int ca = find(a);
78      return data[ca].second;
79    }
80
81  };
82
83
84
85
86  /*******************************************************/
87
88
89
90  template <typename T>
91  struct UnionFindEnumItem {
92
93    typedef std::list<UnionFindEnumItem> ItemList;
94    typedef std::list<ItemList> ClassList;
95    typedef typename ItemList::iterator IIter;
96    typedef typename ClassList::iterator CIter;
97
98    T me;
99    IIter parent;
100    int size;
101    CIter my_class;
102
103    UnionFindEnumItem() {}
104    UnionFindEnumItem(const T &_me, CIter _my_class):
105      me(_me), size(1), my_class(_my_class) {}
106  };
107
108  template <typename T, template <typename Item> class Map>
109  class UnionFindEnum {
110
111    typedef std::list<UnionFindEnumItem<T> > ItemList;
112    typedef std::list<ItemList> ClassList;
113    typedef typename ItemList::iterator IIter;
114    typedef typename ItemList::const_iterator IcIter;
115    typedef typename ClassList::iterator CIter;
116    typedef typename ClassList::const_iterator CcIter;
117
118  public:
119    typedef T ElementType;
120    typedef UnionFindEnumItem<T> ItemType;
121    typedef Map< IIter > MapType;
122
123  private:
124    MapType& m;
125    ClassList classes;
126
127    //    IIter where(const T &a) { return m[a]; }
128    //    IIter parent(IIter a) { return a->parent; }
129    //    P sibling(P a) { return &m[a->sibling]; }
130
131    IIter _find(IIter a) const {
132      IIter comp = a;
133      IIter next;
134      while( (next = comp->parent) != comp ) {
135        comp = next;
136      }
137
138      IIter comp1 = a;
139      while( (next = comp1->parent) != comp ) {
140        comp1->parent = comp->parent;
141        comp1 = next;
142      }
143      return comp;
144    }
145
146  public:
147    UnionFindEnum(MapType& _m) : m(_m) {}
148
149    void insert(const T &a)
150    {
151
152
153      classes.push_back(ItemList());
154      CIter aclass = classes.end();
155      --aclass;
156
157      ItemList &alist = *aclass;
158      alist.push_back(ItemType(a, aclass));
159      IIter ai = alist.begin();
160
161      ai->parent = ai;
162      m.set(a, ai);
163
164    }
165
166    T find(const T &a) const {
167      return _find(m[a])->me;
168    }
169
170    bool join(T a, T b) {
171
172      IIter ca = _find(m[a]);
173      IIter cb = _find(m[b]);
174
175      if ( ca == cb ) {
176        return false;
177      }
178
179      if ( ca->size > cb->size ) {
180
181        cb->parent = ca->parent;
182        ca->size += cb->size;
183       
184        ItemList &alist = *ca->my_class;
185        alist.splice(alist.end(),*cb->my_class);
186
187        classes.erase(cb->my_class);
188        cb->my_class = 0;
189      }
190      else {
191
192        ca->parent = cb->parent;
193        cb->size += ca->size;
194       
195        ItemList &blist = *cb->my_class;
196        blist.splice(blist.end(),*ca->my_class);
197
198        classes.erase(ca->my_class);
199        ca->my_class = 0;
200      }
201
202      return true;
203    }
204
205    int size(const T &a) const {
206      return _find(m[a])->size;
207    }
208
209   
210    void split(const T &a) {
211
212      IIter ca = _find(m[a]);
213 
214      if ( ca->size == 1 )
215        return;
216     
217      CIter aclass = ca->my_class;
218
219      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
220        classes.push_back(ItemList());
221        CIter nl = --classes.end();
222        nl->splice(nl->end(), *aclass, curr);
223
224        curr->size=1;
225        curr->parent=curr;
226        curr->my_class = nl;
227      }
228
229      ca->size=1;
230      return;
231    }
232
233    void erase(const T &a) {
234
235      IIter ma = m[a];
236      if (ma == 0) return;
237
238      IIter la = _find(ma);
239      if (la == ma) {
240        if (ma -> size == 1){
241          classes.erase(ma->my_class);
242          m.set(a,0);
243          return;
244        }
245        ++la;
246        la->size = ma->size - 1;
247        la->my_class = ma->my_class;   
248      }
249
250      for (IIter i = la; i != la->my_class->end(); ++i) {
251        i->parent = la;
252      }
253
254      la->my_class->erase(ma);
255      m.set(a,0);
256    }
257
258    void eraseClass(const T &a) {
259      IIter ma = m[a];
260      if (ma == 0) return;
261#     ifdef DEBUG
262      CIter c = _find(ma)->my_class;
263      for (IIter i=c->begin(); i!=c->end(); ++i)
264        m.set(i->me, 0);
265#     endif
266      classes.erase(_find(ma)->my_class);
267    }
268
269
270    class ClassIt {
271      friend class UnionFindEnum;
272
273      CcIter i;
274    public:
275      ClassIt(Invalid): i(0) {}
276      ClassIt() {}
277     
278      operator const T& () const {
279        ItemList const &ll = *i;
280        return (ll.begin())->me; }
281      bool operator == (ClassIt it) const {
282        return (i == it.i);
283      }
284      bool operator != (ClassIt it) const {
285        return (i != it.i);
286      }
287      bool operator < (ClassIt it) const {
288        return (i < it.i);
289      }
290
291      bool valid() const { return i != 0; }
292    private:
293      void first(const ClassList &l) { i = l.begin(); validate(l); }
294      void next(const ClassList &l) {
295        ++i;
296        validate(l);
297      }
298      void validate(const ClassList &l) {
299        if ( i == l.end() )
300          i = 0;
301      }
302    };
303
304
305    ClassIt& first(ClassIt& it) const {
306      it.first(classes);
307      return it;
308    }
309
310    bool valid(ClassIt const &it) const {
311      return it.valid();
312    }
313
314    ClassIt& next(ClassIt& it) const {
315      it.next(classes);
316      return it;
317    }
318
319
320    class ItemIt {
321      friend class UnionFindEnum;
322
323      IcIter i;
324      const ItemList *l;
325    public:
326      ItemIt(Invalid): i(0) {}
327      ItemIt() {}
328     
329      operator const T& () const { return i->me; }
330      bool operator == (ItemIt it) const {
331        return (i == it.i);
332      }
333      bool operator != (ItemIt it) const {
334        return (i != it.i);
335      }
336      bool operator < (ItemIt it) const {
337        return (i < it.i);
338      }
339
340      bool valid() const { return i != 0; }
341    private:
342      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
343      void next() {
344        ++i;
345        validate();
346      }
347      void validate() {
348        if ( i == l->end() )
349          i = 0;
350      }
351    };
352
353
354    ItemIt& first(ItemIt& it, const T& a) const {
355      it.first( * _find(m[a])->my_class );
356      return it;
357    }
358
359    bool valid(ItemIt const &it) const {
360      return it.valid();
361    }
362
363    ItemIt& next(ItemIt& it) const {
364      it.next();
365      return it;
366    }
367   
368
369
370  };
371
372} //namespace hugo
373
374#endif //HUGO_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.