COIN-OR::LEMON - Graph Library

Changeset 2205:c20b0eb92a33 in lemon-0.x


Ignore:
Timestamp:
09/06/06 13:17:12 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2930
Message:

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

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/kruskal.h

    r2111 r2205  
    2525#include <lemon/bits/utility.h>
    2626#include <lemon/bits/traits.h>
     27#include <lemon/time_measure.h>
     28#include <iostream>
    2729
    2830///\ingroup spantree
     
    118120    typedef typename GR::Node Node;
    119121
    120     NodeIntMap comp(g, -1);
    121     UnionFind<Node,NodeIntMap> uf(comp);
     122    Timer timer;
     123    NodeIntMap comp(g);
     124    UnionFind<Node,NodeIntMap> uf(comp);
     125    for (typename GR::NodeIt it(g); it != INVALID; ++it) {
     126      uf.insert(it);
     127    }
    122128     
    123129    EdgeCost tot_cost = 0;
     
    133139      }
    134140    }
     141    std::cout << timer << std::endl;
    135142    return tot_cost;
    136143  }
  • lemon/max_matching.h

    r2042 r2205  
    6666    typedef typename Graph::IncEdgeIt IncEdgeIt;
    6767
    68     typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
     68    typedef typename Graph::template NodeMap<int> UFECrossRef;
     69    typedef UnionFindEnum<Node, UFECrossRef> UFE;
    6970
    7071  public:
     
    122123      //representative elements of UFE blossom) and for the nodes in C
    123124     
    124       typename UFE::MapType blossom_base(g);
     125      UFECrossRef blossom_base(g);
    125126      UFE blossom(blossom_base);
    126       typename UFE::MapType tree_base(g);
     127
     128      UFECrossRef tree_base(g);
    127129      UFE tree(tree_base);
     130
    128131      //If these UFE's would be members of the class then also
    129132      //blossom_base and tree_base should be a member.
     
    550553    }
    551554    Node y=blossom.find(x);
    552     typename UFE::ItemIt it;
    553     for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
    554       if ( position[it] == D ) {
    555         typename UFE::ItemIt b_it;
    556         for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) { 
    557           position.set( b_it ,C);
     555    for (typename UFE::ItemIt tit(tree, y); tit != INVALID; ++tit) {   
     556      if ( position[tit] == D ) {
     557        for (typename UFE::ItemIt bit(blossom, tit); bit != INVALID; ++bit) { 
     558          position.set( bit ,C);
    558559        }
    559         blossom.eraseClass(it);
    560       } else position.set( it ,C);
     560        blossom.eraseClass(tit);
     561      } else position.set( tit ,C);
    561562    }
    562563    tree.eraseClass(y);
  • lemon/unionfind.h

    r2006 r2205  
    3737  //! @{
    3838
    39   /**
    40    * \brief A \e Union-Find data structure implementation
    41    *
    42    * The class implements the \e Union-Find data structure.
    43    * The union operation uses rank heuristic, while
    44    * the find operation uses path compression.
    45    * This is a very simple but efficient implementation, providing
    46    * only four methods: join (union), find, insert and size.
    47    * For more features see the \ref UnionFindEnum class.
    48    *
    49    * It is primarily used in Kruskal algorithm for finding minimal
    50    * cost spanning tree in a graph.
    51    * \sa kruskal()
    52    *
    53    * \pre The elements are automatically added only if the map
    54    * given to the constructor was filled with -1's. Otherwise you
    55    * need to add all the elements by the \ref insert() method.
    56    * \bug It is not clear what the constructor parameter is used for.
    57    */
    58 
    59   template <typename T, typename TIntMap>
     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>
    6055  class UnionFind {
    6156   
    6257  public:
    63     typedef T ElementType;
    64     typedef std::pair<int,int> PairType;
     58    typedef Item ElementType;
    6559
    6660  private:
    67     std::vector<PairType> data;
    68     TIntMap& map;
     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    }
    6983
    7084  public:
    71     UnionFind(TIntMap& m) : map(m) {}
    72 
    73     /**
    74      * \brief Returns the index of the element's component.
    75      *
    76      * The method returns the index of the element's component.
    77      * This is an integer between zero and the number of inserted elements.
    78      */
    79 
    80     int find(T a)
    81     {
    82       int comp0 = map[a];
    83       if (comp0 < 0) {
    84         return insert(a);
    85       }
    86       int comp = comp0;
    87       int next;
    88       while ( (next = data[comp].first) != comp) {
    89         comp = next;
    90       }
    91       while ( (next = data[comp0].first) != comp) {
    92         data[comp0].first = comp;
    93         comp0 = next;
    94       }
    95 
    96       return comp;
    97     }
    98 
    99     /**
    100      * \brief Inserts a new element into the structure.
    101      *
    102      * This method inserts a new element into the data structure.
    103      *
    104      * It is not required to use this method:
    105      * if the map given to the constructor was filled
    106      * with -1's then it is called automatically
    107      * on the first \ref find or \ref join.
    108      *
    109      * The method returns the index of the new component.
    110      */
    111 
    112     int insert(T a)
    113     {
    114       int n = data.size();
    115       data.push_back(std::make_pair(n, 1));
    116       map.set(a,n);
     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);
    117113      return n;
    118114    }
    119115
    120     /**
    121      * \brief Joining the components of element \e a and element \e b.
    122      *
    123      * This is the \e union operation of the Union-Find structure.
    124      * Joins the component of element \e a and component of
    125      * element \e b. If \e a and \e b are in the same component then
    126      * it returns false otherwise it returns true.
    127      */
    128 
    129     bool join(T a, T b)
    130     {
    131       int ca = find(a);
    132       int cb = find(b);
    133 
    134       if ( ca == cb )
     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 )
    135127        return false;
    136128
    137       if ( data[ca].second > data[cb].second ) {
    138         data[cb].first = ca;
    139         data[ca].second += data[cb].second;
    140       }
    141       else {
    142         data[ca].first = cb;
    143         data[cb].second += data[ca].second;
     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;
    144135      }
    145136      return true;
    146137    }
    147138
    148     /**
    149      * \brief Returns the size of the component of element \e a.
    150      *
    151      * Returns the size of the component of element \e a.
    152      */
    153 
    154     int size(T a)
    155     {
    156       int ca = find(a);
    157       return data[ca].second;
     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];
    158145    }
    159146
     
    161148
    162149
    163 
    164 
    165   /*******************************************************/
    166 
    167 
    168 #ifdef DEVELOPMENT_DOCS
    169 
    170   /**
    171    * \brief The auxiliary class for the \ref UnionFindEnum class.
    172    *
    173    * In the \ref UnionFindEnum class all components are represented as
    174    * a std::list.
    175    * Items of these lists are UnionFindEnumItem structures.
    176    *
    177    * The class has four fields:
    178    *  - T me - the actual element
    179    *  - IIter parent - the parent of the element in the union-find structure
    180    *  - int size - the size of the component of the element.
    181    *            Only valid if the element
    182    *            is the leader of the component.
    183    *  - CIter my_class - pointer into the list of components
    184    *            pointing to the component of the element.
    185    *            Only valid if the element is the leader of the component.
    186    */
    187 
    188 #endif
    189 
    190   template <typename T>
    191   struct UnionFindEnumItem {
    192 
    193     typedef std::list<UnionFindEnumItem> ItemList;
    194     typedef std::list<ItemList> ClassList;
    195     typedef typename ItemList::iterator IIter;
    196     typedef typename ClassList::iterator CIter;
    197 
    198     T me;
    199     IIter parent;
    200     int size;
    201     CIter my_class;
    202 
    203     UnionFindEnumItem() {}
    204     UnionFindEnumItem(const T &_me, CIter _my_class):
    205       me(_me), size(1), my_class(_my_class) {}
     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
    206576  };
    207577
    208578
    209   /**
    210    * \brief A \e Union-Find data structure implementation which
    211    * is able to enumerate the components.
    212    *
    213    * The class implements a \e Union-Find data structure
    214    * which is able to enumerate the components and the items in
    215    * a component. If you don't need this feature then perhaps it's
    216    * better to use the \ref UnionFind class which is more efficient.
    217    *
    218    * The union operation uses rank heuristic, while
    219    * the find operation uses path compression.
    220    *
    221    * \pre You
    222    * need to add all the elements by the \ref insert() method.
    223    */
    224 
    225 
    226   template <typename T, template <typename Item> class Map>
    227   class UnionFindEnum {
    228 
    229     typedef std::list<UnionFindEnumItem<T> > ItemList;
    230     typedef std::list<ItemList> ClassList;
    231     typedef typename ItemList::iterator IIter;
    232     typedef typename ItemList::const_iterator IcIter;
    233     typedef typename ClassList::iterator CIter;
    234     typedef typename ClassList::const_iterator CcIter;
    235 
    236   public:
    237     typedef T ElementType;
    238     typedef UnionFindEnumItem<T> ItemType;
    239     typedef Map< IIter > MapType;
    240 
    241   private:
    242     MapType& m;
    243     ClassList classes;
    244 
    245     IIter _find(IIter a) const {
    246       IIter comp = a;
    247       IIter next;
    248       while( (next = comp->parent) != comp ) {
    249         comp = next;
    250       }
    251 
    252       IIter comp1 = a;
    253       while( (next = comp1->parent) != comp ) {
    254         comp1->parent = comp->parent;
    255         comp1 = next;
    256       }
    257       return comp;
    258     }
    259 
    260     const ItemList& classOf(const T &a) const {
    261       return *_find(m[a])->my_class;
    262     }
    263 
    264   public:
    265     UnionFindEnum(MapType& _m) : m(_m) {}
    266 
    267 
    268     /**
    269      * \brief Inserts the given element into a new component.
    270      *
    271      * This method creates a new component consisting only of the
    272      * given element.
    273      */
    274 
    275     void insert(const T &a)
    276     {
    277 
    278 
    279       classes.push_back(ItemList());
    280       CIter aclass = classes.end();
    281       --aclass;
    282 
    283       ItemList &alist = *aclass;
    284       alist.push_back(ItemType(a, aclass));
    285       IIter ai = alist.begin();
    286 
    287       ai->parent = ai;
    288       m.set(a, ai);
    289 
    290     }
    291 
    292     /**
    293      * \brief Inserts the given element into the component of the others.
    294      *
    295      * This methods inserts the element \e a into the component of the
    296      * element \e comp.
    297      */
    298 
    299     void insert(const T &a, const T &comp) {
    300      
    301       IIter clit = _find(m[comp]);
    302       ItemList &c = *clit->my_class;
    303       c.push_back(ItemType(a,CIter()));
    304       IIter ai = c.end();
    305       --ai;
    306       ai->parent = clit;
    307       m.set(a, ai);
    308       ++clit->size;
    309     }
    310 
    311 
    312     /**
    313      * \brief Finds the leader of the component of the given element.
    314      *
    315      * The method returns the leader of the component of the given element.
    316      */
    317 
    318     T find(const T &a) const {
    319       return _find(m[a])->me;
    320     }
    321 
    322 
    323     /**
    324      * \brief Joining the component of element \e a and element \e b.
    325      *
    326      * This is the \e union operation of the Union-Find structure.
    327      * Joins the component of element \e a and component of
    328      * element \e b. If \e a and \e b are in the same component then
    329      * returns false else returns true.
    330      */
    331 
    332     bool join(T a, T b) {
    333 
    334       IIter ca = _find(m[a]);
    335       IIter cb = _find(m[b]);
    336 
    337       if ( ca == cb ) {
    338         return false;
    339       }
    340 
    341       if ( ca->size > cb->size ) {
    342 
    343         cb->parent = ca->parent;
    344         ca->size += cb->size;
    345        
    346         ItemList &alist = *ca->my_class;
    347         alist.splice(alist.end(),*cb->my_class);
    348 
    349         classes.erase(cb->my_class);
    350       }
    351       else {
    352 
    353         ca->parent = cb->parent;
    354         cb->size += ca->size;
    355        
    356         ItemList &blist = *cb->my_class;
    357         blist.splice(blist.end(),*ca->my_class);
    358 
    359         classes.erase(ca->my_class);
    360       }
    361 
    362       return true;
    363     }
    364 
    365 
    366     /**
    367      * \brief Returns the size of the component of element \e a.
    368      *
    369      * Returns the size of the component of element \e a.
    370      */
    371 
    372     int size(const T &a) const {
    373       return _find(m[a])->size;
    374     }
    375 
    376 
    377     /**
    378      * \brief Splits up the component of the element.
    379      *
    380      * Splitting the component of the element into sigleton
    381      * components (component of size one).
    382      */
    383 
    384     void split(const T &a) {
    385 
    386       IIter ca = _find(m[a]);
    387  
    388       if ( ca->size == 1 )
    389         return;
    390      
    391       CIter aclass = ca->my_class;
    392 
    393       for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
    394         classes.push_back(ItemList());
    395         CIter nl = --classes.end();
    396         nl->splice(nl->end(), *aclass, curr);
    397 
    398         curr->size=1;
    399         curr->parent=curr;
    400         curr->my_class = nl;
    401       }
    402 
    403       ca->size=1;
    404       return;
    405     }
    406 
    407 
    408     /**
    409      * \brief Sets the given element to the leader element of its component.
    410      *
    411      * Sets the given element to the leader element of its component.
    412      */
    413 
    414     void makeRep(const T &a) {
    415 
    416       IIter ia = m[a];
    417       IIter la = _find(ia);
    418       if (la == ia) return;
    419 
    420       ia->my_class = la->my_class;
    421 
    422       ia->size = la->size;
    423 
    424       CIter l = ia->my_class;
    425       l->splice(l->begin(),*l,ia);
    426 
    427       ia->parent = ia;
    428       la->parent = ia;
    429     }
    430 
    431     /**
    432      * \brief Moves the given element to another component.
    433      *
    434      * This method moves the element \e a from its component
    435      * to the component of \e comp.
    436      * If \e a and \e comp are in the same component then
    437      * it returns false otherwise it returns true.
    438      */
    439 
    440     bool move(const T &a, const T &comp) {
    441 
    442       IIter ai = m[a];
    443       IIter lai = _find(ai);
    444       IIter clit = _find(m[comp]);
    445 
    446       if (lai == clit)
    447         return false;
    448 
    449       ItemList &cl = *clit->my_class,
    450         &al = *lai->my_class;
    451 
    452       bool is_leader = (lai == ai);
    453       bool singleton = false;
    454 
    455       if (is_leader) {
    456         ++lai;
    457       }
    458 
    459       cl.splice(cl.end(), al, ai);
    460 
    461       if (is_leader) {
    462         if (ai->size == 1) {
    463           classes.erase(ai->my_class);
    464           singleton = true;
    465         }
    466         else {
    467           lai->size = ai->size;
    468           lai->my_class = ai->my_class;
    469         }
    470       }
    471       if (!singleton) {
    472         for (IIter i = lai; i != al.end(); ++i)
    473           i->parent = lai;
    474         --lai->size;
    475       }
    476 
    477       ai->parent = clit;
    478       ++clit->size;
    479 
    480       return true;
    481     }
    482 
    483 
    484     /**
    485      * \brief Removes the given element from the structure.
    486      *
    487      * Removes the element from its component and if the component becomes
    488      * empty then removes that component from the component list.
    489      *
    490      * It is an error to remove an element which is not in the structure.
    491      */
    492     void erase(const T &a) {
    493 
    494       IIter ma = m[a];
    495 
    496       IIter la = _find(ma);
    497       if (la == ma) {
    498         if (ma -> size == 1){
    499           classes.erase(ma->my_class);
    500           return;
    501         }
    502         ++la;
    503         la->size = ma->size;
    504         la->my_class = ma->my_class;   
    505       }
    506 
    507       for (IIter i = la; i != la->my_class->end(); ++i) {
    508         i->parent = la;
    509       }
    510 
    511       la->size--;
    512       la->my_class->erase(ma);
    513     }
    514 
    515     /**
    516      * \brief Removes the component of the given element from the structure.
    517      *
    518      * Removes the component of the given element from the structure.
    519      *
    520      * It is an error to give an element which is not in the structure.
    521      */
    522 
    523     void eraseClass(const T &a) {
    524       IIter ma = m[a];
    525       classes.erase(_find(ma)->my_class);
    526     }
    527 
    528 
    529     class ClassIt {
    530       friend class UnionFindEnum;
    531 
    532       CcIter i;
    533       const ClassList *l;
    534 
    535     public:
    536       ClassIt(Invalid): l(0) {}
    537       ClassIt() {}
    538       ClassIt(UnionFindEnum const &ufe) {
    539         l = &ufe.classes;
    540         i = l->begin();
    541       }
    542      
    543       operator const T& () const {
    544         ItemList const &ll = *i;
    545         return (ll.begin())->me;
    546       }
    547       bool operator == (ClassIt const &it) const {
    548         return (l==it.l && i==it.i) || (!valid() && !it.valid());
    549       }
    550       bool operator != (ClassIt const &it) const {
    551         return !(*this == it);
    552       }
    553       bool operator < (ClassIt const &it) const {
    554         return (i < it.i);
    555       }
    556 
    557       bool operator==(Invalid) const {
    558         return !valid();
    559       }
    560       bool operator!=(Invalid) const {
    561         return valid();
    562       }
    563 
    564       ClassIt& operator++() {
    565         ++i;
    566         return *this;
    567       }
    568 
    569       // obsoleted:
    570       bool valid() const { return l!=0 && i!=l->end(); }
    571     };
    572 
    573     /**
    574      * \brief Sets the iterator to point to the first component.
    575      *
    576      * Sets the iterator to point to the first component.
    577      *
    578      * With the \ref first, \ref valid and \ref next methods you can
    579      * iterate through the components. For example:
    580      * \code
    581      * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
    582      * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
    583      * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
    584      *  for (U.first(iter); U.valid(iter); U.next(iter)) {
    585      *    // iter is convertible to Graph::Node
    586      *    cout << iter << endl;
    587      *  }
    588      * \endcode
    589      *
    590      * \bug obsoleted, use the new LEMON iterator interface instead
    591      */
    592 
    593     ClassIt& first(ClassIt& it) const {
    594       it = ClassIt(*this);
    595       return it;
    596     }
    597 
    598     /**
    599      * \brief Returns whether the iterator is valid.
    600      *
    601      * Returns whether the iterator is valid.
    602      *
    603      * With the \ref first, \ref valid and \ref next methods you can
    604      * iterate through the components. See the example here: \ref first.
    605      *
    606      * \bug obsoleted, use the new LEMON iterator interface instead
    607      */
    608 
    609     bool valid(ClassIt const &it) const {
    610       return it.valid();
    611     }
    612 
    613     /**
    614      * \brief Steps the iterator to the next component.
    615      *
    616      * Steps the iterator to the next component.
    617      *
    618      * With the \ref first, \ref valid and \ref next methods you can
    619      * iterate through the components. See the example here: \ref first.
    620      */
    621 
    622     ClassIt& next(ClassIt& it) const {
    623       return ++it;
    624     }
    625 
    626 
    627     class ItemIt {
    628       friend class UnionFindEnum;
    629 
    630       IcIter i;
    631       const ItemList *l;
    632     public:
    633       ItemIt(Invalid): l(0) {}
    634       ItemIt() {}
    635       ItemIt(UnionFindEnum const &ufe, const T& a) {
    636         l = &ufe.classOf(a);
    637         i = l->begin();
    638       }
    639      
    640       operator const T& () const { return i->me; }
    641       bool operator == (ItemIt const &it) const {
    642         return (l==it.l && i==it.i) || (!valid() && !it.valid());
    643       }
    644       bool operator != (ItemIt const &it) const {
    645         return !(*this == it);
    646       }
    647       bool operator < (ItemIt const &it) const {
    648         return (i < it.i);
    649       }
    650 
    651       bool operator==(Invalid) const {
    652         return !valid();
    653       }
    654       bool operator!=(Invalid) const {
    655         return valid();
    656       }
    657 
    658       ItemIt& operator++() {
    659         ++i;
    660         return *this;
    661       }
    662 
    663       // obsoleted:
    664       bool valid() const { return l!=0 && i!=l->end(); }
    665     };
    666 
    667 
    668 
    669     /**
    670      * \brief Sets the iterator to point to the first element of the component.
    671      *
    672      * \anchor first2
    673      * Sets the iterator to point to the first element of the component.
    674      *
    675      * With the \ref first2 "first", \ref valid2 "valid"
    676      * and \ref next2 "next" methods you can
    677      * iterate through the elements of a component. For example
    678      * (iterating through the component of the node \e node):
    679      * \code
    680      * Graph::Node node = ...;
    681      * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
    682      * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
    683      * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
    684      *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
    685      *     // iiter is convertible to Graph::Node
    686      *     cout << iiter << endl;
    687      *   }
    688      * \endcode
    689      *
    690      * \bug obsoleted, use the new LEMON iterator interface instead
    691      */
    692    
    693     ItemIt& first(ItemIt& it, const T& a) const {
    694       it = ItemIt(*this, a);
    695       return it;
    696     }
    697 
    698     /**
    699      * \brief Returns whether the iterator is valid.
    700      *
    701      * \anchor valid2
    702      * Returns whether the iterator is valid.
    703      *
    704      * With the \ref first2 "first", \ref valid2 "valid"
    705      * and \ref next2 "next" methods you can
    706      * iterate through the elements of a component.
    707      * See the example here: \ref first2 "first".
    708      *
    709      * \bug obsoleted, use the new LEMON iterator interface instead
    710      */
    711 
    712     bool valid(ItemIt const &it) const {
    713       return it.valid();
    714     }
    715 
    716     /**
    717      * \brief Steps the iterator to the next component.
    718      *
    719      * \anchor next2
    720      * Steps the iterator to the next component.
    721      *
    722      * With the \ref first2 "first", \ref valid2 "valid"
    723      * and \ref next2 "next" methods you can
    724      * iterate through the elements of a component.
    725      * See the example here: \ref first2 "first".
    726      *
    727      * \bug obsoleted, use the new LEMON iterator interface instead
    728      */
    729 
    730     ItemIt& next(ItemIt& it) const {
    731       return ++it;
    732     }
    733    
    734   };
    735 
    736 
    737579  //! @}
    738580
  • test/unionfind_test.cc

    r2005 r2205  
    2626using namespace std;
    2727
    28 template <typename T>
    29 class BaseMap : public StdMap<int,T> {};
    30 
    31 typedef UnionFindEnum<int, BaseMap> UFE;
     28typedef UnionFindEnum<int, StdMap<int, int> > UFE;
    3229
    3330void print(UFE const &ufe) {
    34   UFE::ClassIt cit;
    3531  cout << "Print the classes of the structure:" << endl;
    3632  int i = 1;
    37   for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
     33  for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {
    3834    cout << "  " << i << " (" << cit << "):" << flush;
    39     UFE::ItemIt iit;
    40     for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
     35    for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
    4136      cout << " " << iit << flush;
    4237    }
     
    4944
    5045int main() {
    51   UFE::MapType base;
     46  StdMap<int, int> base;
    5247  UFE U(base);
    5348
     
    7671  U.insert(9);
    7772  U.insert(10,9);
     73
    7874  check(U.join(8,10),"Test failed.");
    7975
Note: See TracChangeset for help on using the changeset viewer.