COIN-OR::LEMON - Graph Library

Changeset 394:3a34c5626e52 in lemon-0.x


Ignore:
Timestamp:
04/24/04 18:03:25 (21 years ago)
Author:
beckerjc
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@525
Message:

New union-find structure with enumerable classes.

Location:
src/work/johanna
Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/johanna/Makefile

    r350 r394  
    1 BINARIES = kruskal_test ma_order_test
     1BINARIES = kruskal_test ma_order_test unionfind_test
    22INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
    33include ../makefile
  • src/work/johanna/kruskal.h

    r352 r394  
    2626    for (typename InputEdgeOrder::const_iterator p = edges.begin();
    2727         p!=edges.end(); ++p ) {
    28       if ( uf.joinComponents(G.head(edges.first(p)),
     28      if ( uf.join(G.head(edges.first(p)),
    2929                             G.tail(edges.first(p))) ) {
    3030        out_map.set(edges.first(p), true);
  • src/work/johanna/unionfind.h

    r349 r394  
    44
    55#include <vector>
     6#include <list>
    67#include <utility>
     8#include <algorithm>
     9
     10#include <invalid.h>
    711
    812namespace hugo {
     
    2327
    2428
    25     int whichComponent(T a)
     29    int find(T a)
    2630    {
    2731      int comp0 = map[a];
    2832      if (comp0 < 0) {
    29         return insertNewElement(a);
     33        return insert(a);
    3034      }
    3135      int comp = comp0;
     
    4246    }
    4347
    44     int insertNewElement(T a)
     48    int insert(T a)
    4549    {
    4650      int n = data.size();
    47       data.push_back(make_pair(n, 1));
     51      data.push_back(std::make_pair(n, 1));
    4852      map.set(a,n);
    4953      return n;
    5054    }
    5155
    52     bool joinComponents(T a, T b)
    53     {
    54       int ca = whichComponent(a);
    55       int cb = whichComponent(b);
     56    bool join(T a, T b)
     57    {
     58      int ca = find(a);
     59      int cb = find(b);
    5660
    5761      if ( ca == cb )
     
    6973    }
    7074
    71     int componentSize(T a)
    72     {
    73       int ca = whichComponent(a);
     75    int size(T a)
     76    {
     77      int ca = find(a);
    7478      return data[ca].second;
    7579    }
     
    7781  };
    7882
     83
     84
     85
     86  /*******************************************************/
     87
     88
     89
     90  template <typename T>
     91  struct UnionFindEnumItem {
     92
     93    typedef std::list<UnionFindEnumItem> ItemList;
     94    typedef std::list<ItemList> ClassList;
     95    typedef typename ItemList::iterator IIter;
     96    typedef typename ClassList::iterator CIter;
     97
     98    T me;
     99    IIter parent;
     100    int size;
     101    CIter my_class;
     102
     103    UnionFindEnumItem() {}
     104    UnionFindEnumItem(const T &_me, CIter _my_class):
     105      me(_me), size(1), my_class(_my_class) {}
     106  };
     107
     108  template <typename T, template <typename Item> class Map>
     109  class UnionFindEnum {
     110
     111    typedef std::list<UnionFindEnumItem<T> > ItemList;
     112    typedef std::list<ItemList> ClassList;
     113    typedef typename ItemList::iterator IIter;
     114    typedef typename ItemList::const_iterator IcIter;
     115    typedef typename ClassList::iterator CIter;
     116    typedef typename ClassList::const_iterator CcIter;
     117
     118  public:
     119    typedef T ElementType;
     120    typedef UnionFindEnumItem<T> ItemType;
     121    typedef Map< IIter > MapType;
     122
     123  private:
     124    MapType& m;
     125    ClassList classes;
     126
     127    //    IIter where(const T &a) { return m[a]; }
     128    //    IIter parent(IIter a) { return a->parent; }
     129    //    P sibling(P a) { return &m[a->sibling]; }
     130
     131    IIter _find(IIter a) const {
     132      IIter comp = a;
     133      IIter next;
     134      while( (next = comp->parent) != comp ) {
     135        comp = next;
     136      }
     137
     138      IIter comp1 = a;
     139      while( (next = comp1->parent) != comp ) {
     140        comp1->parent = comp->parent;
     141        comp1 = next;
     142      }
     143      return comp;
     144    }
     145
     146  public:
     147    UnionFindEnum(MapType& _m) : m(_m) {}
     148
     149    void insert(const T &a)
     150    {
     151
     152
     153      classes.push_back(ItemList());
     154      CIter aclass = classes.end();
     155      --aclass;
     156
     157      ItemList &alist = *aclass;
     158      alist.push_back(ItemType(a, aclass));
     159      IIter ai = alist.begin();
     160
     161      ai->parent = ai;
     162      m.set(a, ai);
     163
     164    }
     165
     166    T find(const T &a) const {
     167      return _find(m[a])->me;
     168    }
     169
     170    bool join(T a, T b) {
     171
     172      IIter ca = _find(m[a]);
     173      IIter cb = _find(m[b]);
     174
     175      if ( ca == cb ) {
     176        return false;
     177      }
     178
     179      if ( ca->size > cb->size ) {
     180
     181        cb->parent = ca->parent;
     182        ca->size += cb->size;
     183       
     184        ItemList &alist = *ca->my_class;
     185        alist.splice(alist.end(),*cb->my_class);
     186
     187        classes.erase(cb->my_class);
     188        cb->my_class = 0;
     189      }
     190      else {
     191
     192        ca->parent = cb->parent;
     193        cb->size += ca->size;
     194       
     195        ItemList &blist = *cb->my_class;
     196        blist.splice(blist.end(),*ca->my_class);
     197
     198        classes.erase(ca->my_class);
     199        ca->my_class = 0;
     200      }
     201
     202      return true;
     203    }
     204
     205    int size(const T &a) const {
     206      return _find(m[a])->size;
     207    }
     208
     209   
     210    void split(const T &a) {
     211
     212      IIter ca = _find(m[a]);
     213 
     214      if ( ca->size == 1 )
     215        return;
     216     
     217      CIter aclass = ca->my_class;
     218
     219      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
     220        classes.push_back(ItemList());
     221        CIter nl = --classes.end();
     222        nl->splice(nl->end(), *aclass, curr);
     223
     224        curr->size=1;
     225        curr->parent=curr;
     226        curr->my_class = nl;
     227      }
     228
     229      ca->size=1;
     230      return;
     231    }
     232
     233    void erase(const T &a) {
     234
     235      IIter ma = m[a];
     236      if (ma == 0) return;
     237
     238      IIter la = _find(ma);
     239      if (la == ma) {
     240        if (ma -> size == 1){
     241          classes.erase(ma->my_class);
     242          m.set(a,0);
     243          return;
     244        }
     245        ++la;
     246        la->size = ma->size - 1;
     247        la->my_class = ma->my_class;   
     248      }
     249
     250      for (IIter i = la; i != la->my_class->end(); ++i) {
     251        i->parent = la;
     252      }
     253
     254      la->my_class->erase(ma);
     255      m.set(a,0);
     256    }
     257
     258    void eraseClass(const T &a) {
     259      IIter ma = m[a];
     260      if (ma == 0) return;
     261#     ifdef DEBUG
     262      CIter c = _find(ma)->my_class;
     263      for (IIter i=c->begin(); i!=c->end(); ++i)
     264        m.set(i->me, 0);
     265#     endif
     266      classes.erase(_find(ma)->my_class);
     267    }
     268
     269
     270    class ClassIt {
     271      friend class UnionFindEnum;
     272
     273      CcIter i;
     274    public:
     275      ClassIt(Invalid): i(0) {}
     276      ClassIt() {}
     277     
     278      operator const T& () const {
     279        ItemList const &ll = *i;
     280        return (ll.begin())->me; }
     281      bool operator == (ClassIt it) const {
     282        return (i == it.i);
     283      }
     284      bool operator != (ClassIt it) const {
     285        return (i != it.i);
     286      }
     287      bool operator < (ClassIt it) const {
     288        return (i < it.i);
     289      }
     290
     291      bool valid() const { return i != 0; }
     292    private:
     293      void first(const ClassList &l) { i = l.begin(); validate(l); }
     294      void next(const ClassList &l) {
     295        ++i;
     296        validate(l);
     297      }
     298      void validate(const ClassList &l) {
     299        if ( i == l.end() )
     300          i = 0;
     301      }
     302    };
     303
     304
     305    ClassIt& first(ClassIt& it) const {
     306      it.first(classes);
     307      return it;
     308    }
     309
     310    bool valid(ClassIt const &it) const {
     311      return it.valid();
     312    }
     313
     314    ClassIt& next(ClassIt& it) const {
     315      it.next(classes);
     316      return it;
     317    }
     318
     319
     320    class ItemIt {
     321      friend class UnionFindEnum;
     322
     323      IcIter i;
     324      const ItemList *l;
     325    public:
     326      ItemIt(Invalid): i(0) {}
     327      ItemIt() {}
     328     
     329      operator const T& () const { return i->me; }
     330      bool operator == (ItemIt it) const {
     331        return (i == it.i);
     332      }
     333      bool operator != (ItemIt it) const {
     334        return (i != it.i);
     335      }
     336      bool operator < (ItemIt it) const {
     337        return (i < it.i);
     338      }
     339
     340      bool valid() const { return i != 0; }
     341    private:
     342      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
     343      void next() {
     344        ++i;
     345        validate();
     346      }
     347      void validate() {
     348        if ( i == l->end() )
     349          i = 0;
     350      }
     351    };
     352
     353
     354    ItemIt& first(ItemIt& it, const T& a) const {
     355      it.first( * _find(m[a])->my_class );
     356      return it;
     357    }
     358
     359    bool valid(ItemIt const &it) const {
     360      return it.valid();
     361    }
     362
     363    ItemIt& next(ItemIt& it) const {
     364      it.next();
     365      return it;
     366    }
     367   
     368
     369
     370  };
     371
    79372} //namespace hugo
    80373
Note: See TracChangeset for help on using the changeset viewer.