1.1 --- a/src/work/athos/union_find.h	Sun Apr 17 18:57:22 2005 +0000
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,94 +0,0 @@
     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 lemon {
    1.20 -  
    1.21 -  template <typename Key, 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(Key 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(Key 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(Key u,Key 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 lemon
    1.97 -#endif