COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 2476:059dcdda37c5

Last change on this file since 2476:059dcdda37c5 was 2427:d40c31b08d6f, checked in by Balazs Dezso, 13 years ago

Clear for unionfinds

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