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
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]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
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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
[921]19#ifndef LEMON_UNION_FIND_H
20#define LEMON_UNION_FIND_H
[483]21
[491]22//!\ingroup auxdat
[483]23//!\file
24//!\brief Union-Find data structures.
[774]25//!
[483]26
27#include <vector>
28#include <list>
29#include <utility>
30#include <algorithm>
31
[1993]32#include <lemon/bits/invalid.h>
[483]33
[921]34namespace lemon {
[483]35
36  //! \addtogroup auxdat
37  //! @{
38
[2205]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>
[483]55  class UnionFind {
56   
57  public:
[2205]58    typedef Item ElementType;
[483]59
60  private:
[2205]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    }
[483]83
84  public:
85
[2205]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) {}
[483]94
[2205]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]);
[483]102    }
103
[2205]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);
[483]113      return n;
114    }
115
[2205]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]);
[483]125
[2205]126      if ( ka == kb )
[483]127        return false;
128
[2205]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;
[483]135      }
136      return true;
137    }
138
[2205]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];
[483]145    }
146
147  };
148
149
[2205]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;
[483]184
[2205]185      int nextItem, prevItem;
186      int nextClass, prevClass;
187    };
[483]188
[2205]189    std::vector<ItemT> items;
190    ItemIntMap& index;
[483]191
[2205]192    int firstClass;
[483]193
194
[2205]195    bool rep(int idx) const {
196      return items[idx].parent < 0;
[483]197    }
198
[2205]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       
[2003]230    }
231
[483]232  public:
233
[2205]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;
[483]244
[2205]245      int idx = items.size();
246      index.set(item, idx);
[483]247
[2205]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;
[483]259
[2205]260      items.push_back(t);
[483]261    }
262
[2205]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;
[483]270
[2205]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);
[483]285    }
286
[2205]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;
[483]292    }
293
[2205]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) {
[483]301
[2205]302      int ak = repIndex(index[a]);
303      int bk = repIndex(index[b]);
[483]304
[2205]305      if (ak == bk) {
[483]306        return false;
307      }
308
[2205]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;
[483]317      }
[2205]318      spliceItems(ak, bk);
[483]319
320      return true;
321    }
322
[2205]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;
[483]328    }
329
[2205]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;
[483]347
[2205]348        idx = next;
[483]349      }
350
[2205]351      items[idx].parent = -1;
352      items[idx].prevItem = idx;
353      items[idx].nextItem = idx;
354     
355      items[firstClass].prevClass = -1;
[483]356    }
357
[2205]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;
[483]383    }
384
[2205]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        }
[483]426
[2205]427        ++items[k].parent;
[483]428      }
429
[2205]430      idx = index[item];     
431      items[items[idx].prevItem].nextItem = items[idx].nextItem;
432      items[items[idx].nextItem].prevItem = items[idx].prevItem;
[483]433
[2205]434    }   
[483]435
[2205]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);
[483]446      return true;
447    }
448
449
[2205]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    }
[483]459
[2205]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;
[483]471      }
472
[2205]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;
[483]491      }
492
[2205]493      /// \brief Equality operator
494      ///
495      /// Equality operator
496      bool operator==(const ClassIt& i) {
497        return i.idx == idx;
498      }
[483]499
[2205]500      /// \brief Inequality operator
501      ///
502      /// Inequality operator
503      bool operator!=(const ClassIt& i) {
504        return i.idx != idx;
[2003]505      }
[483]506     
[2205]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]);
[483]534      }
535
[2205]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;
[2003]548      }
[2205]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;
[2003]555      }
556
[2205]557      /// \brief Equality operator
558      ///
559      /// Equality operator
560      bool operator==(const ItemIt& i) {
561        return i.idx == idx;
[2003]562      }
563
[2205]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;
[483]574    };
575
576  };
577
578
579  //! @}
580
[921]581} //namespace lemon
[483]582
[921]583#endif //LEMON_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.