COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 2316:c0fae4bbaa5c

Last change on this file since 2316:c0fae4bbaa5c was 2308:cddae1c4fee6, checked in by Balazs Dezso, 17 years ago

Erasing unionfind Item template parameter

File size: 15.8 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  /// \ingroup auxdat
37  ///
38  /// \brief A \e Union-Find data structure implementation
39  ///
40  /// The class implements the \e Union-Find data structure.
41  /// The union operation uses rank heuristic, while
42  /// the find operation uses path compression.
43  /// This is a very simple but efficient implementation, providing
44  /// only four methods: join (union), find, insert and size.
45  /// For more features see the \ref UnionFindEnum class.
46  ///
47  /// It is primarily used in Kruskal algorithm for finding minimal
48  /// cost spanning tree in a graph.
49  /// \sa kruskal()
50  ///
51  /// \pre You need to add all the elements by the \ref insert()
52  /// method. 
53  template <typename _ItemIntMap>
54  class UnionFind {
55  public:
56
57    typedef _ItemIntMap ItemIntMap;
58    typedef typename ItemIntMap::Key Item;
59
60  private:
61    // If the items vector stores negative value for an item then
62    // that item is root item and it has -items[it] component size.
63    // Else the items[it] contains the index of the parent.
64    std::vector<int> items;
65    ItemIntMap& index;
66
67    bool rep(int idx) const {
68      return items[idx] < 0;
69    }
70
71    int repIndex(int idx) const {
72      int k = idx;
73      while (!rep(k)) {
74        k = items[k] ;
75      }
76      while (idx != k) {
77        int next = items[idx];
78        const_cast<int&>(items[idx]) = k;
79        idx = next;
80      }
81      return k;
82    }
83
84  public:
85
86    /// \brief Constructor
87    ///
88    /// Constructor of the UnionFind class. You should give an item to
89    /// integer map which will be used from the data structure. If you
90    /// modify directly this map that may cause segmentation fault,
91    /// invalid data structure, or infinite loop when you use again
92    /// the union-find.
93    UnionFind(ItemIntMap& m) : index(m) {}
94
95    /// \brief Returns the index of the element's component.
96    ///
97    /// The method returns the index of the element's component.
98    /// This is an integer between zero and the number of inserted elements.
99    ///
100    int find(const Item& a) {
101      return repIndex(index[a]);
102    }
103
104    /// \brief Inserts a new element into the structure.
105    ///
106    /// This method inserts a new element into the data structure.
107    ///
108    /// The method returns the index of the new component.
109    int insert(const Item& a) {
110      int n = items.size();
111      items.push_back(-1);
112      index.set(a,n);
113      return n;
114    }
115
116    /// \brief Joining the components of element \e a and element \e b.
117    ///
118    /// This is the \e union operation of the Union-Find structure.
119    /// Joins the component of element \e a and component of
120    /// element \e b. If \e a and \e b are in the same component then
121    /// it returns false otherwise it returns true.
122    bool join(const Item& a, const Item& b) {
123      int ka = repIndex(index[a]);
124      int kb = repIndex(index[b]);
125
126      if ( ka == kb )
127        return false;
128
129      if (items[ka] < items[kb]) {
130        items[ka] += items[kb];
131        items[kb] = ka;
132      } else {
133        items[kb] += items[ka];
134        items[ka] = kb;
135      }
136      return true;
137    }
138
139    /// \brief Returns the size of the component of element \e a.
140    ///
141    /// Returns the size of the component of element \e a.
142    int size(const Item& a) {
143      int k = repIndex(index[a]);
144      return - items[k];
145    }
146
147  };
148
149  /// \ingroup auxdat
150  ///
151  /// \brief A \e Union-Find data structure implementation which
152  /// is able to enumerate the components.
153  ///
154  /// The class implements a \e Union-Find data structure
155  /// which is able to enumerate the components and the items in
156  /// a component. If you don't need this feature then perhaps it's
157  /// better to use the \ref UnionFind class which is more efficient.
158  ///
159  /// The union operation uses rank heuristic, while
160  /// the find operation uses path compression.
161  ///
162  /// \pre You need to add all the elements by the \ref insert()
163  /// method.
164  ///
165  template <typename _ItemIntMap>
166  class UnionFindEnum {
167  public:
168   
169    typedef _ItemIntMap ItemIntMap;
170    typedef typename ItemIntMap::Key Item;
171
172  private:
173   
174    // If the parent stores negative value for an item then that item
175    // is root item and it has -items[it].parent component size.  Else
176    // the items[it].parent contains the index of the parent.
177    //
178    // The \c nextItem and \c prevItem provides the double-linked
179    // cyclic list of one component's items. The \c prevClass and
180    // \c nextClass gives the double linked list of the representant
181    // items.
182    struct ItemT {
183      int parent;
184      Item item;
185
186      int nextItem, prevItem;
187      int nextClass, prevClass;
188    };
189
190    std::vector<ItemT> items;
191    ItemIntMap& index;
192
193    int firstClass;
194
195
196    bool rep(int idx) const {
197      return items[idx].parent < 0;
198    }
199
200    int repIndex(int idx) const {
201      int k = idx;
202      while (!rep(k)) {
203        k = items[k].parent;
204      }
205      while (idx != k) {
206        int next = items[idx].parent;
207        const_cast<int&>(items[idx].parent) = k;
208        idx = next;
209      }
210      return k;
211    }
212
213    void unlaceClass(int k) {
214      if (items[k].prevClass != -1) {
215        items[items[k].prevClass].nextClass = items[k].nextClass;
216      } else {
217        firstClass = items[k].nextClass;
218      }
219      if (items[k].nextClass != -1) {
220        items[items[k].nextClass].prevClass = items[k].prevClass;
221      }
222    }
223
224    void spliceItems(int ak, int bk) {
225      items[items[ak].prevItem].nextItem = bk;
226      items[items[bk].prevItem].nextItem = ak;
227      int tmp = items[ak].prevItem;
228      items[ak].prevItem = items[bk].prevItem;
229      items[bk].prevItem = tmp;
230       
231    }
232
233  public:
234
235    UnionFindEnum(ItemIntMap& _index)
236      : items(), index(_index), firstClass(-1) {}
237   
238    /// \brief Inserts the given element into a new component.
239    ///
240    /// This method creates a new component consisting only of the
241    /// given element.
242    ///
243    void insert(const Item& item) {
244      ItemT t;
245
246      int idx = items.size();
247      index.set(item, idx);
248
249      t.nextItem = idx;
250      t.prevItem = idx;
251      t.item = item;
252      t.parent = -1;
253     
254      t.nextClass = firstClass;
255      if (firstClass != -1) {
256        items[firstClass].prevClass = idx;
257      }
258      t.prevClass = -1;
259      firstClass = idx;
260
261      items.push_back(t);
262    }
263
264    /// \brief Inserts the given element into the component of the others.
265    ///
266    /// This methods inserts the element \e a into the component of the
267    /// element \e comp.
268    void insert(const Item& item, const Item& comp) {
269      int k = repIndex(index[comp]);
270      ItemT t;
271
272      int idx = items.size();
273      index.set(item, idx);
274
275      t.prevItem = k;
276      t.nextItem = items[k].nextItem;
277      items[items[k].nextItem].prevItem = idx;
278      items[k].nextItem = idx;
279
280      t.item = item;
281      t.parent = k;
282
283      --items[k].parent;
284
285      items.push_back(t);
286    }
287
288    /// \brief Finds the leader of the component of the given element.
289    ///
290    /// The method returns the leader of the component of the given element.
291    const Item& find(const Item &item) const {
292      return items[repIndex(index[item])].item;
293    }
294
295    /// \brief Joining the component of element \e a and element \e b.
296    ///
297    /// This is the \e union operation of the Union-Find structure.
298    /// Joins the component of element \e a and component of
299    /// element \e b. If \e a and \e b are in the same component then
300    /// returns false else returns true.
301    bool join(const Item& a, const Item& b) {
302
303      int ak = repIndex(index[a]);
304      int bk = repIndex(index[b]);
305
306      if (ak == bk) {
307        return false;
308      }
309
310      if ( items[ak].parent < items[bk].parent ) {
311        unlaceClass(bk);
312        items[ak].parent += items[bk].parent;
313        items[bk].parent = ak;
314      } else {
315        unlaceClass(bk);
316        items[bk].parent += items[ak].parent;
317        items[ak].parent = bk;
318      }
319      spliceItems(ak, bk);
320
321      return true;
322    }
323
324    /// \brief Returns the size of the component of element \e a.
325    ///
326    /// Returns the size of the component of element \e a.
327    int size(const Item &item) const {
328      return - items[repIndex(index[item])].parent;
329    }
330
331    /// \brief Splits up the component of the element.
332    ///
333    /// Splitting the component of the element into sigleton
334    /// components (component of size one).
335    void split(const Item &item) {
336      int k = repIndex(index[item]);
337      int idx = items[k].nextItem;
338      while (idx != k) {
339        int next = items[idx].nextItem;
340       
341        items[idx].parent = -1;
342        items[idx].prevItem = idx;
343        items[idx].nextItem = idx;
344       
345        items[idx].nextClass = firstClass;
346        items[firstClass].prevClass = idx;
347        firstClass = idx;
348
349        idx = next;
350      }
351
352      items[idx].parent = -1;
353      items[idx].prevItem = idx;
354      items[idx].nextItem = idx;
355     
356      items[firstClass].prevClass = -1;
357    }
358
359    /// \brief Sets the given element to the leader element of its component.
360    ///
361    /// Sets the given element to the leader element of its component.
362    void makeRep(const Item &item) {
363      int nk = index[item];
364      int k = repIndex(nk);
365      if (nk == k) return;
366     
367      if (items[k].prevClass != -1) {
368        items[items[k].prevClass].nextClass = nk;
369      } else {
370        firstClass = nk;
371      }
372      if (items[k].nextClass != -1) {
373        items[items[k].nextClass].prevClass = nk;
374      }
375     
376      int idx = items[k].nextItem;
377      while (idx != k) {
378        items[idx].parent = nk;
379        idx = items[idx].nextItem;
380      }
381     
382      items[nk].parent = items[k].parent;
383      items[k].parent = nk;
384    }
385
386    /// \brief Removes the given element from the structure.
387    ///
388    /// Removes the element from its component and if the component becomes
389    /// empty then removes that component from the component list.
390    ///
391    /// \warning It is an error to remove an element which is not in
392    /// the structure.
393    void erase(const Item &item) {
394      int idx = index[item];
395      if (rep(idx)) {
396        int k = idx;
397        if (items[k].parent == -1) {
398          unlaceClass(idx);
399          return;
400        } else {
401          int nk = items[k].nextItem;
402          if (items[k].prevClass != -1) {
403            items[items[k].prevClass].nextClass = nk;
404          } else {
405            firstClass = nk;
406          }
407          if (items[k].nextClass != -1) {
408            items[items[k].nextClass].prevClass = nk;
409          }
410     
411          int idx = items[k].nextItem;
412          while (idx != k) {
413            items[idx].parent = nk;
414            idx = items[idx].nextItem;
415          }
416         
417          items[nk].parent = items[k].parent + 1;
418        }
419      } else {
420       
421        int k = repIndex(idx);
422        idx = items[k].nextItem;
423        while (idx != k) {
424          items[idx].parent = k;
425          idx = items[idx].nextItem;
426        }
427
428        ++items[k].parent;
429      }
430
431      idx = index[item];     
432      items[items[idx].prevItem].nextItem = items[idx].nextItem;
433      items[items[idx].nextItem].prevItem = items[idx].prevItem;
434
435    }   
436
437    /// \brief Moves the given element to another component.
438    ///
439    /// This method moves the element \e a from its component
440    /// to the component of \e comp.
441    /// If \e a and \e comp are in the same component then
442    /// it returns false otherwise it returns true.
443    bool move(const Item &item, const Item &comp) {
444      if (repIndex(index[item]) == repIndex(index[comp])) return false;
445      erase(item);
446      insert(item, comp);
447      return true;
448    }
449
450
451    /// \brief Removes the component of the given element from the structure.
452    ///
453    /// Removes the component of the given element from the structure.
454    ///
455    /// \warning It is an error to give an element which is not in the
456    /// structure.
457    void eraseClass(const Item &item) {
458      unlaceClass(repIndex(index[item]));
459    }
460
461    /// \brief Lemon style iterator for the representant items.
462    ///
463    /// ClassIt is a lemon style iterator for the components. It iterates
464    /// on the representant items of the classes.
465    class ClassIt {
466    public:
467      /// \brief Constructor of the iterator
468      ///
469      /// Constructor of the iterator
470      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
471        idx = unionFind->firstClass;
472      }
473
474      /// \brief Constructor to get invalid iterator
475      ///
476      /// Constructor to get invalid iterator
477      ClassIt(Invalid) : unionFind(0), idx(-1) {}
478     
479      /// \brief Increment operator
480      ///
481      /// It steps to the next representant item.
482      ClassIt& operator++() {
483        idx = unionFind->items[idx].nextClass;
484        return *this;
485      }
486     
487      /// \brief Conversion operator
488      ///
489      /// It converts the iterator to the current representant item.
490      operator const Item&() const {
491        return unionFind->items[idx].item;
492      }
493
494      /// \brief Equality operator
495      ///
496      /// Equality operator
497      bool operator==(const ClassIt& i) {
498        return i.idx == idx;
499      }
500
501      /// \brief Inequality operator
502      ///
503      /// Inequality operator
504      bool operator!=(const ClassIt& i) {
505        return i.idx != idx;
506      }
507     
508    private:
509      const UnionFindEnum* unionFind;
510      int idx;
511    };
512
513    /// \brief Lemon style iterator for the items of a component.
514    ///
515    /// ClassIt is a lemon style iterator for the components. It iterates
516    /// on the items of a class. By example if you want to iterate on
517    /// each items of each classes then you may write the next code.
518    ///\code
519    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
520    ///   std::cout << "Class: ";
521    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
522    ///     std::cout << toString(iit) << ' ' << std::endl;
523    ///   }
524    ///   std::cout << std::endl;
525    /// }
526    ///\endcode
527    class ItemIt {
528    public:
529      /// \brief Constructor of the iterator
530      ///
531      /// Constructor of the iterator. The iterator iterates
532      /// on the class of the \c item.
533      ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {
534        idx = unionFind->repIndex(unionFind->index[item]);
535      }
536
537      /// \brief Constructor to get invalid iterator
538      ///
539      /// Constructor to get invalid iterator
540      ItemIt(Invalid) : unionFind(0), idx(-1) {}
541     
542      /// \brief Increment operator
543      ///
544      /// It steps to the next item in the class.
545      ItemIt& operator++() {
546        idx = unionFind->items[idx].nextItem;
547        if (unionFind->rep(idx)) idx = -1;
548        return *this;
549      }
550     
551      /// \brief Conversion operator
552      ///
553      /// It converts the iterator to the current item.
554      operator const Item&() const {
555        return unionFind->items[idx].item;
556      }
557
558      /// \brief Equality operator
559      ///
560      /// Equality operator
561      bool operator==(const ItemIt& i) {
562        return i.idx == idx;
563      }
564
565      /// \brief Inequality operator
566      ///
567      /// Inequality operator
568      bool operator!=(const ItemIt& i) {
569        return i.idx != idx;
570      }
571     
572    private:
573      const UnionFindEnum* unionFind;
574      int idx;
575    };
576
577  };
578
579
580  //! @}
581
582} //namespace lemon
583
584#endif //LEMON_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.