/usr/include/opengm/utilities/disjoint-set.hxx is in libopengm-dev 2.3.6+20160905-1build2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #pragma once
#ifndef OPENGM_DISJOINT_SET_HXX
#define OPENGM_DISJOINT_SET_HXX
#include <map>
#include <vector>
#include <string>
#include <iostream>
namespace opengm{
template<class T= size_t>
class disjoint_set{
public:
typedef struct{
T rank;
T p;
T size;
}elem;
disjoint_set(T);
T find(T);
void join(T,T);
T size(T) ;
T numberOfSets() const;
void representativeLabeling(std::map<T, T>&) ;
private:
elem *elements_;
T numberOfElements_;
T numberOfSets_;
};
// end Class
template<class T>
T disjoint_set<T>::size(T i) {
i = find(i);
return elements_[i].size;
}
template<class T>
disjoint_set<T>::disjoint_set(T numberOfElements){
elements_ = new elem[numberOfElements];
numberOfElements_ = numberOfElements;
numberOfSets_ = numberOfElements;
for(T i=0;i < numberOfElements;++i){
elements_[i].rank = 0;
elements_[i].size=1;
elements_[i].p = i;
}
}
template<class T>
T disjoint_set<T>::find(T x){
T y = x;
while(y != elements_[y].p){
y=elements_[y].p;
}
elements_[x].p = y;
return y;
}
template<class T>
void disjoint_set<T>::join(T x,T y){
x = find(x);
y = find(y);
if(x!=y){
if(elements_[x].rank > elements_[y].rank){
elements_[y].p = x;
elements_[x].size += elements_[y].size;
}
else {
elements_[x].p = y;
elements_[y].size += elements_[x].size;
if(elements_[x].rank == elements_[y].rank){
elements_[y].rank++;
}
}
numberOfSets_--;
}
}
template<class T>
T disjoint_set<T>::numberOfSets() const{
return numberOfSets_;
}
template<class T>
void disjoint_set<T>::representativeLabeling(std::map<T,T>& repL) {
repL.clear();
T n=0;
for(T i=0;i<numberOfElements_;++i){
T x = find(i);
if(i==x){
repL[i]=n;
n++;
}
}
}
}
#endif
|