1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/athos/union_find.h	Fri Mar 26 14:59:18 2004 +0000
     1.3 @@ -0,0 +1,94 @@
     1.4 +// -*- C++ -*- //
     1.5 +/*
     1.6 +Union-Find structure
     1.7 +
     1.8 +* Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
     1.9 +* minden szobajovo kulcs ertekre, -1 -es ertekkel!
    1.10 + 
    1.11 +*/
    1.12 +#ifndef UNION_FIND_H
    1.13 +#define UNION_FIND_H
    1.14 +
    1.15 +#include <vector>
    1.16 +//#include <map>
    1.17 +
    1.18 +
    1.19 +namespace hugo {
    1.20 +  
    1.21 +  template <typename KeyType, typename KeyIntMap>
    1.22 +    class UnionFind {
    1.23 +    KeyIntMap& pointmap;
    1.24 +    struct VectorElementType {
    1.25 +      int boss;
    1.26 +      int count;
    1.27 +      VectorElementType(int _boss, int _count){
    1.28 +	boss = _boss;
    1.29 +	count = _count;
    1.30 +      }
    1.31 +    };
    1.32 +    std::vector<VectorElementType> container;
    1.33 +    public:
    1.34 +      
    1.35 +    UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){
    1.36 +      
    1.37 +    } 
    1.38 +    
    1.39 +    //Give a component of one point to the structure
    1.40 +    int addPoint(KeyType u){
    1.41 +      int _index = container.size();
    1.42 +      VectorElementType buf(_index,1);
    1.43 +      container.push_back(buf);
    1.44 +      return _index;
    1.45 +    }
    1.46 +
    1.47 +    
    1.48 +    //Finds the big boss of u
    1.49 +    int find(KeyType u){
    1.50 +      if (pointmap.get(u)==-1){
    1.51 +	int whoami = addPoint(u);
    1.52 +	pointmap.set(u, whoami);
    1.53 +	return whoami;
    1.54 +      }
    1.55 +      else{
    1.56 +	int emp = pointmap.get(u);
    1.57 +	int boss = container[emp].boss;
    1.58 +	while(emp != boss){
    1.59 +	  emp = boss;
    1.60 +	  boss = container[emp].boss;
    1.61 +	}
    1.62 +	return boss;
    1.63 +      }
    1.64 +    }
    1.65 +
    1.66 +    //Finds u and v in the structures and merges the comopnents, if not equal
    1.67 +    bool findAndMerge(KeyType u,KeyType v){
    1.68 +      int bu = find(u);
    1.69 +      int bv = find(v);
    1.70 +      if (bu != bv){
    1.71 +	unio(bu,bv);
    1.72 +	return true;
    1.73 +      }
    1.74 +      else{
    1.75 +	return false;
    1.76 +      }
    1.77 +    }
    1.78 +
    1.79 +    //Merges a into b
    1.80 +    void mergeInto(int a, int b){
    1.81 +      container[a].boss = b;
    1.82 +      container[b].count +=  container[a].count;
    1.83 +    }
    1.84 +    
    1.85 +    //Makes the union
    1.86 +    void unio(int b1, int b2){
    1.87 +      if (container[b1].count>container[b2].count){
    1.88 +	mergeInto(b2,b1);
    1.89 +      }
    1.90 +      else{
    1.91 +	mergeInto(b1,b2);
    1.92 +      }
    1.93 +    }//unio
    1.94 +  };
    1.95 +  
    1.96 +}//namespace hugo
    1.97 +#endif