1 #ifndef UTILS_EQUIVALENCE_MAP_H 2 #define UTILS_EQUIVALENCE_MAP_H 5 #include <KrisLibrary/errors.h> 12 inline void InverseMapping(
const std::vector<int>& fwd,std::vector<vector<int> >& bwd) {
14 bwd.reserve(fwd.size());
15 if(fwd.empty())
return;
16 int N=*max_element(fwd.begin(),fwd.end());
18 for(
size_t i=0;i<fwd.size();i++) {
19 Assert(0<=fwd[i]&&fwd[i]<=N);
20 bwd[fwd[i]].push_back(i);
23 for(
size_t i=0;i<bwd.size();i++) {
27 FatalError(
"InverseMapping error! inserted only %d of %d items",n,fwd.size());
39 template <
class T,
class EqFn>
40 void EquivalenceMap(
const std::vector<T>& x,std::vector<vector<int> >& eq,EqFn& Eq)
44 for(
int i=0;i<n;i++) {
46 for(
int j=0;j<i;j++) {
63 vector<vector<int> >::iterator it,prev;
66 for(it=eq.begin();it!=eq.end();it++,i++) {
67 num += (int)it->size();
From an indexed set of elments, allows fast unioning of the elements into sets.
Definition: unionfind.h:18
void EquivalenceMap(const std::vector< T > &x, std::vector< vector< int > > &eq, EqFn &Eq)
Forms the equivalence map on x, given an equivalence function.
Definition: EquivalenceMap.h:40
void GetSets(std::vector< int > &sets)
Returns the sets to which the items belong, such that sets[i] = set(xi)
Definition: unionfind.cpp:51
void InverseMapping(const std::vector< int > &fwd, std::vector< vector< int > > &bwd)
For a mapping f:i->fwd[i], this gets the inverse multi-mapping g:j->{i|fwd[i]=j}. ...
Definition: EquivalenceMap.h:12
int Union(const int i, const int j)
Unions the sets to which xi and xj belong.
Definition: unionfind.cpp:34
int FindSet(const int i)
Returns the id of the set to which xi belongs.
Definition: unionfind.cpp:26