1.1 --- a/src/work/johanna/Makefile	Sat Apr 24 15:19:17 2004 +0000
     1.2 +++ b/src/work/johanna/Makefile	Sat Apr 24 16:03:25 2004 +0000
     1.3 @@ -1,4 +1,4 @@
     1.4 -BINARIES = kruskal_test ma_order_test
     1.5 +BINARIES = kruskal_test ma_order_test unionfind_test
     1.6  INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
     1.7  include ../makefile
     1.8  

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/johanna/contract_wrapper.h	Sat Apr 24 16:03:25 2004 +0000
     2.3 @@ -0,0 +1,36 @@
     2.4 +// -*- C++ -*- //
     2.5 +
     2.6 +#ifndef HUGO_CONTRACT_WRAPPER
     2.7 +#define HUGO_CONTRACT_WRAPPER
     2.8 +
     2.9 +#include <graph_wrapper.h>
    2.10 +
    2.11 +namespace hugo {
    2.12 +
    2.13 +  template<typename Graph>
    2.14 +  class ConractWrapper : public GraphWrapper<const Graph> {
    2.15 +
    2.16 +  public:
    2.17 +    typedef typename Parent::NodeMap NodeMap;
    2.18 +    class Node;
    2.19 +
    2.20 +  private:
    2.21 +    typedef GraphWrapper<Graph> Parent;
    2.22 +    
    2.23 +
    2.24 +    UnionFindEnum<Node, NodeMap> parts; 
    2.25 + 
    2.26 +  public:
    2.27 +
    2.28 +    ConractWrapper(const Graph& _graph) : Parent(_graph) { }
    2.29 +
    2.30 +
    2.31 +
    2.32 +
    2.33 +
    2.34 +  };
    2.35 +
    2.36 +
    2.37 +
    2.38 +}
    2.39 +#endif

     3.1 --- a/src/work/johanna/kruskal.h	Sat Apr 24 15:19:17 2004 +0000
     3.2 +++ b/src/work/johanna/kruskal.h	Sat Apr 24 16:03:25 2004 +0000
     3.3 @@ -25,7 +25,7 @@
     3.4      EdgeCost tot_cost = 0;
     3.5      for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
     3.6  	 p!=edges.end(); ++p ) {
     3.7 -      if ( uf.joinComponents(G.head(edges.first(p)),
     3.8 +      if ( uf.join(G.head(edges.first(p)),
     3.9  			     G.tail(edges.first(p))) ) {
    3.10  	out_map.set(edges.first(p), true);
    3.11  	tot_cost += edges.second(p);

     4.1 --- a/src/work/johanna/unionfind.h	Sat Apr 24 15:19:17 2004 +0000
     4.2 +++ b/src/work/johanna/unionfind.h	Sat Apr 24 16:03:25 2004 +0000
     4.3 @@ -3,7 +3,11 @@
     4.4  #define HUGO_UNION_FIND_H
     4.5  
     4.6  #include <vector>
     4.7 +#include <list>
     4.8  #include <utility>
     4.9 +#include <algorithm>
    4.10 +
    4.11 +#include <invalid.h>
    4.12  
    4.13  namespace hugo {
    4.14  
    4.15 @@ -22,11 +26,11 @@
    4.16      UnionFind(TIntMap& m) : map(m) {}
    4.17  
    4.18  
    4.19 -    int whichComponent(T a)
    4.20 +    int find(T a)
    4.21      {
    4.22        int comp0 = map[a];
    4.23        if (comp0 < 0) {
    4.24 -	return insertNewElement(a);
    4.25 +	return insert(a);
    4.26        }
    4.27        int comp = comp0;
    4.28        int next;
    4.29 @@ -41,18 +45,18 @@
    4.30        return comp;
    4.31      }
    4.32  
    4.33 -    int insertNewElement(T a)
    4.34 +    int insert(T a)
    4.35      {
    4.36        int n = data.size();
    4.37 -      data.push_back(make_pair(n, 1));
    4.38 +      data.push_back(std::make_pair(n, 1));
    4.39        map.set(a,n);
    4.40        return n;
    4.41      }
    4.42  
    4.43 -    bool joinComponents(T a, T b)
    4.44 +    bool join(T a, T b)
    4.45      {
    4.46 -      int ca = whichComponent(a);
    4.47 -      int cb = whichComponent(b);
    4.48 +      int ca = find(a);
    4.49 +      int cb = find(b);
    4.50  
    4.51        if ( ca == cb ) 
    4.52  	return false;
    4.53 @@ -68,14 +72,303 @@
    4.54        return true;
    4.55      }
    4.56  
    4.57 -    int componentSize(T a)
    4.58 +    int size(T a)
    4.59      {
    4.60 -      int ca = whichComponent(a);
    4.61 +      int ca = find(a);
    4.62        return data[ca].second;
    4.63      }
    4.64  
    4.65    };
    4.66  
    4.67 +
    4.68 +
    4.69 +
    4.70 +  /*******************************************************/
    4.71 +
    4.72 +
    4.73 +
    4.74 +  template <typename T>
    4.75 +  struct UnionFindEnumItem {
    4.76 +
    4.77 +    typedef std::list<UnionFindEnumItem> ItemList;
    4.78 +    typedef std::list<ItemList> ClassList;
    4.79 +    typedef typename ItemList::iterator IIter;
    4.80 +    typedef typename ClassList::iterator CIter;
    4.81 +
    4.82 +    T me;
    4.83 +    IIter parent;
    4.84 +    int size;
    4.85 +    CIter my_class;
    4.86 +
    4.87 +    UnionFindEnumItem() {}
    4.88 +    UnionFindEnumItem(const T &_me, CIter _my_class): 
    4.89 +      me(_me), size(1), my_class(_my_class) {}
    4.90 +  };
    4.91 +
    4.92 +  template <typename T, template <typename Item> class Map>
    4.93 +  class UnionFindEnum {
    4.94 +
    4.95 +    typedef std::list<UnionFindEnumItem<T> > ItemList;
    4.96 +    typedef std::list<ItemList> ClassList;
    4.97 +    typedef typename ItemList::iterator IIter;
    4.98 +    typedef typename ItemList::const_iterator IcIter;
    4.99 +    typedef typename ClassList::iterator CIter;
   4.100 +    typedef typename ClassList::const_iterator CcIter;
   4.101 +
   4.102 +  public:
   4.103 +    typedef T ElementType;
   4.104 +    typedef UnionFindEnumItem<T> ItemType;
   4.105 +    typedef Map< IIter > MapType;
   4.106 +
   4.107 +  private:
   4.108 +    MapType& m;
   4.109 +    ClassList classes;
   4.110 +
   4.111 +    //    IIter where(const T &a) { return m[a]; }
   4.112 +    //    IIter parent(IIter a) { return a->parent; }
   4.113 +    //    P sibling(P a) { return &m[a->sibling]; }
   4.114 +
   4.115 +    IIter _find(IIter a) const {
   4.116 +      IIter comp = a;
   4.117 +      IIter next;
   4.118 +      while( (next = comp->parent) != comp ) {
   4.119 +	comp = next;
   4.120 +      }
   4.121 +
   4.122 +      IIter comp1 = a;
   4.123 +      while( (next = comp1->parent) != comp ) {
   4.124 +	comp1->parent = comp->parent;
   4.125 +	comp1 = next;
   4.126 +      }
   4.127 +      return comp;
   4.128 +    }
   4.129 +
   4.130 +  public:
   4.131 +    UnionFindEnum(MapType& _m) : m(_m) {}
   4.132 +
   4.133 +    void insert(const T &a)
   4.134 +    {
   4.135 +
   4.136 +
   4.137 +      classes.push_back(ItemList());
   4.138 +      CIter aclass = classes.end();
   4.139 +      --aclass;
   4.140 +
   4.141 +      ItemList &alist = *aclass;
   4.142 +      alist.push_back(ItemType(a, aclass));
   4.143 +      IIter ai = alist.begin();
   4.144 +
   4.145 +      ai->parent = ai;
   4.146 +      m.set(a, ai);
   4.147 +
   4.148 +    }
   4.149 +
   4.150 +    T find(const T &a) const {
   4.151 +      return _find(m[a])->me;
   4.152 +    }
   4.153 +
   4.154 +    bool join(T a, T b) {
   4.155 +
   4.156 +      IIter ca = _find(m[a]);
   4.157 +      IIter cb = _find(m[b]);
   4.158 +
   4.159 +      if ( ca == cb ) {
   4.160 +	return false;
   4.161 +      }
   4.162 +
   4.163 +      if ( ca->size > cb->size ) {
   4.164 +
   4.165 +	cb->parent = ca->parent;
   4.166 +	ca->size += cb->size;
   4.167 +	
   4.168 +	ItemList &alist = *ca->my_class;
   4.169 +	alist.splice(alist.end(),*cb->my_class);
   4.170 +
   4.171 +	classes.erase(cb->my_class);
   4.172 +	cb->my_class = 0;
   4.173 +      }
   4.174 +      else {
   4.175 +
   4.176 +	ca->parent = cb->parent;
   4.177 +	cb->size += ca->size;
   4.178 +	
   4.179 +	ItemList &blist = *cb->my_class;
   4.180 +	blist.splice(blist.end(),*ca->my_class);
   4.181 +
   4.182 +	classes.erase(ca->my_class);
   4.183 +	ca->my_class = 0;
   4.184 +      }
   4.185 +
   4.186 +      return true;
   4.187 +    }
   4.188 +
   4.189 +    int size(const T &a) const {
   4.190 +      return _find(m[a])->size;
   4.191 +    }
   4.192 +
   4.193 +    
   4.194 +    void split(const T &a) {
   4.195 +
   4.196 +      IIter ca = _find(m[a]);
   4.197 + 
   4.198 +      if ( ca->size == 1 )
   4.199 +	return;
   4.200 +      
   4.201 +      CIter aclass = ca->my_class;
   4.202 +
   4.203 +      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
   4.204 +	classes.push_back(ItemList());
   4.205 +	CIter nl = --classes.end();
   4.206 +	nl->splice(nl->end(), *aclass, curr);
   4.207 +
   4.208 +	curr->size=1;
   4.209 +	curr->parent=curr;
   4.210 +	curr->my_class = nl;
   4.211 +      }
   4.212 +
   4.213 +      ca->size=1;
   4.214 +      return;
   4.215 +    }
   4.216 +
   4.217 +    void erase(const T &a) {
   4.218 +
   4.219 +      IIter ma = m[a];
   4.220 +      if (ma == 0) return;
   4.221 +
   4.222 +      IIter la = _find(ma);
   4.223 +      if (la == ma) {
   4.224 +	if (ma -> size == 1){
   4.225 +	  classes.erase(ma->my_class);
   4.226 +	  m.set(a,0);
   4.227 +	  return;
   4.228 +	}
   4.229 +	++la;
   4.230 +	la->size = ma->size - 1; 
   4.231 +	la->my_class = ma->my_class;	
   4.232 +      }
   4.233 +
   4.234 +      for (IIter i = la; i != la->my_class->end(); ++i) {
   4.235 +	i->parent = la;
   4.236 +      }
   4.237 +
   4.238 +      la->my_class->erase(ma);
   4.239 +      m.set(a,0);
   4.240 +    }
   4.241 +
   4.242 +    void eraseClass(const T &a) {
   4.243 +      IIter ma = m[a];
   4.244 +      if (ma == 0) return;
   4.245 +#     ifdef DEBUG
   4.246 +      CIter c = _find(ma)->my_class;
   4.247 +      for (IIter i=c->begin(); i!=c->end(); ++i)
   4.248 +	m.set(i->me, 0);
   4.249 +#     endif
   4.250 +      classes.erase(_find(ma)->my_class);
   4.251 +    }
   4.252 +
   4.253 +
   4.254 +    class ClassIt {
   4.255 +      friend class UnionFindEnum;
   4.256 +
   4.257 +      CcIter i;
   4.258 +    public:
   4.259 +      ClassIt(Invalid): i(0) {}
   4.260 +      ClassIt() {}
   4.261 +      
   4.262 +      operator const T& () const { 
   4.263 +	ItemList const &ll = *i;
   4.264 +	return (ll.begin())->me; }
   4.265 +      bool operator == (ClassIt it) const {
   4.266 +	return (i == it.i);
   4.267 +      }
   4.268 +      bool operator != (ClassIt it) const {
   4.269 +	return (i != it.i);
   4.270 +      }
   4.271 +      bool operator < (ClassIt it) const {
   4.272 +	return (i < it.i);
   4.273 +      }
   4.274 +
   4.275 +      bool valid() const { return i != 0; }
   4.276 +    private:
   4.277 +      void first(const ClassList &l) { i = l.begin(); validate(l); }
   4.278 +      void next(const ClassList &l) {
   4.279 +	++i; 
   4.280 +	validate(l);
   4.281 +      }
   4.282 +      void validate(const ClassList &l) {
   4.283 +	if ( i == l.end() ) 
   4.284 +	  i = 0;
   4.285 +      }
   4.286 +    };
   4.287 +
   4.288 +
   4.289 +    ClassIt& first(ClassIt& it) const {
   4.290 +      it.first(classes);
   4.291 +      return it;
   4.292 +    }
   4.293 +
   4.294 +    bool valid(ClassIt const &it) const {
   4.295 +      return it.valid(); 
   4.296 +    }
   4.297 +
   4.298 +    ClassIt& next(ClassIt& it) const {
   4.299 +      it.next(classes);
   4.300 +      return it;
   4.301 +    }
   4.302 +
   4.303 +
   4.304 +    class ItemIt {
   4.305 +      friend class UnionFindEnum;
   4.306 +
   4.307 +      IcIter i;
   4.308 +      const ItemList *l;
   4.309 +    public:
   4.310 +      ItemIt(Invalid): i(0) {}
   4.311 +      ItemIt() {}
   4.312 +      
   4.313 +      operator const T& () const { return i->me; }
   4.314 +      bool operator == (ItemIt it) const {
   4.315 +	return (i == it.i);
   4.316 +      }
   4.317 +      bool operator != (ItemIt it) const {
   4.318 +	return (i != it.i);
   4.319 +      }
   4.320 +      bool operator < (ItemIt it) const {
   4.321 +	return (i < it.i);
   4.322 +      }
   4.323 +
   4.324 +      bool valid() const { return i != 0; }
   4.325 +    private:
   4.326 +      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
   4.327 +      void next() {
   4.328 +	++i; 
   4.329 +	validate();
   4.330 +      }
   4.331 +      void validate() {
   4.332 +	if ( i == l->end() ) 
   4.333 +	  i = 0;
   4.334 +      }
   4.335 +    };
   4.336 +
   4.337 +
   4.338 +    ItemIt& first(ItemIt& it, const T& a) const {
   4.339 +      it.first( * _find(m[a])->my_class );
   4.340 +      return it;
   4.341 +    }
   4.342 +
   4.343 +    bool valid(ItemIt const &it) const {
   4.344 +      return it.valid(); 
   4.345 +    }
   4.346 +
   4.347 +    ItemIt& next(ItemIt& it) const {
   4.348 +      it.next();
   4.349 +      return it;
   4.350 +    }
   4.351 +    
   4.352 +
   4.353 +
   4.354 +  };
   4.355 +
   4.356  } //namespace hugo
   4.357  
   4.358  #endif //HUGO_UNION_FIND_H

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/work/johanna/unionfind_test.cc	Sat Apr 24 16:03:25 2004 +0000
     5.3 @@ -0,0 +1,114 @@
     5.4 +#include <iostream>
     5.5 +
     5.6 +#include <maps.h>
     5.7 +#include <unionfind.h>
     5.8 +
     5.9 +using namespace hugo;
    5.10 +using namespace std;
    5.11 +
    5.12 +bool passed = true;
    5.13 +
    5.14 +void check(bool rc) {
    5.15 +  passed = passed && rc;
    5.16 +  if(!rc) {
    5.17 +    cout << "Test failed!" << endl;
    5.18 +  }
    5.19 +}
    5.20 +
    5.21 +template <typename T>
    5.22 +class BaseMap : public StdMap<int,T> {};
    5.23 +
    5.24 +typedef UnionFindEnum<int, BaseMap> UFE;
    5.25 +
    5.26 +void print(UFE const &ufe) {
    5.27 +  UFE::ClassIt cit;
    5.28 +  cout << "printing the classes of the structure:" << endl;
    5.29 +  int i = 1;
    5.30 +  for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
    5.31 +    cout << "  " << i << " (" << cit << "):" << flush;
    5.32 +    UFE::ItemIt iit;
    5.33 +    for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
    5.34 +      cout << " " << iit << flush;
    5.35 +    }
    5.36 +    cout << endl;
    5.37 +    i++;
    5.38 +  }
    5.39 +  cout << "done" << endl;
    5.40 +}
    5.41 +
    5.42 +
    5.43 +int main() {
    5.44 +  UFE::MapType base;
    5.45 +  UFE U(base);
    5.46 +
    5.47 +  print(U);
    5.48 +
    5.49 +  cout << "Inserting 1..." << endl;
    5.50 +  U.insert(1);
    5.51 +  print(U);
    5.52 +  
    5.53 +  cout << "Inserting 2..." << endl;
    5.54 +  U.insert(2);
    5.55 +  print(U);
    5.56 +  
    5.57 +  cout << "Joining 1 and 2..." << endl;
    5.58 +  check(U.join(1,2));
    5.59 +  print(U);
    5.60 +
    5.61 +  cout << "Inserting 3, 4, 5, 6, 7..." << endl;
    5.62 +  U.insert(3);
    5.63 +  U.insert(4);
    5.64 +  U.insert(5);
    5.65 +  U.insert(6);
    5.66 +  U.insert(7);
    5.67 +  print (U);
    5.68 +
    5.69 +  cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
    5.70 +  check(U.join(1,4));
    5.71 +  check(!U.join(2,4));
    5.72 +  check(U.join(3,5));
    5.73 +  print(U);
    5.74 +
    5.75 +  cout << "size of the class of 4: " << U.size(4) << endl;
    5.76 +  check(U.size(4) == 3);
    5.77 +  cout << "size of the class of 5: " << U.size(5) << endl;
    5.78 +  check(U.size(5) == 2);
    5.79 +  cout << "size of the class of 6: " << U.size(6) << endl;
    5.80 +  check(U.size(6) == 1);
    5.81 +
    5.82 +  cout <<"erase 1: " << endl;
    5.83 +  U.erase(1);
    5.84 +  print(U);
    5.85 +
    5.86 +  cout <<"erase 1: " << endl;
    5.87 +  U.erase(1);
    5.88 +  print(U);
    5.89 +
    5.90 +  cout <<"erase 6: " << endl;
    5.91 +  U.erase(6);
    5.92 +  print(U);
    5.93 +
    5.94 +  cout << "split the class of 5: " << endl;
    5.95 +  U.split(5);
    5.96 +  print(U);
    5.97 +
    5.98 +  cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
    5.99 +  check(U.join(3,4));
   5.100 +  check(!U.join(2,4));
   5.101 +  print(U);
   5.102 +
   5.103 +  cout << "eraseClass 4 ..." << endl;
   5.104 +  U.eraseClass(4);
   5.105 +  print(U);
   5.106 +
   5.107 +  cout << "eraseClass 7 ..." << endl;
   5.108 +  U.eraseClass(7);
   5.109 +  print(U);
   5.110 +
   5.111 +  cout << "done" << endl;
   5.112 +
   5.113 +  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
   5.114 +       << endl;
   5.115 +
   5.116 +  return passed ? 0 : 1;
   5.117 +}