COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 2229:4dbb6dd2dd4b

Last change on this file since 2229:4dbb6dd2dd4b was 2205:c20b0eb92a33, checked in by Balazs Dezso, 13 years ago

UnionFind?
Changing the representation of the union-find
it has the same running time but it takes just 2/3 space
! does not auto insert items /performance/

UnionFindEnum?
Changing the interface - more convenient to UnionFind?
Does not based on the stl data structures /it could be disadvantage/

=> does not use singular iterator assignment /not stl conform, but always work/

Just new iterator interface

MaxMatching? + UnionFindTest?
Using new iterator interface instead of the old

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