KrisLibrary  1.0.0
EquivalenceMap.h
1 #ifndef UTILS_EQUIVALENCE_MAP_H
2 #define UTILS_EQUIVALENCE_MAP_H
3 
4 #include "unionfind.h"
5 #include <KrisLibrary/errors.h>
6 #include <map>
7 
12 inline void InverseMapping(const std::vector<int>& fwd,std::vector<vector<int> >& bwd) {
13  bwd.clear();
14  bwd.reserve(fwd.size());
15  if(fwd.empty()) return;
16  int N=*max_element(fwd.begin(),fwd.end());
17  bwd.resize(N+1);
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);
21  }
22  size_t n=0;
23  for(size_t i=0;i<bwd.size();i++) {
24  n+=bwd[i].size();
25  }
26  if(n != fwd.size()) {
27  FatalError("InverseMapping error! inserted only %d of %d items",n,fwd.size());
28  }
29 }
30 
39 template <class T,class EqFn>
40 void EquivalenceMap(const std::vector<T>& x,std::vector<vector<int> >& eq,EqFn& Eq)
41 {
42  int n=(int)x.size();
43  UnionFind uf(n);
44  for(int i=0;i<n;i++) {
45  int seti=i;
46  for(int j=0;j<i;j++) {
47  int setj = uf.FindSet(j);
48  if(seti != setj) {
49  if(Eq(x[i],x[j])) {
50  //merge i->j
51  uf.Union(j,i);
52  Assert(uf.FindSet(j) == setj);
53  Assert(uf.FindSet(i) == setj);
54  seti = setj;
55  }
56  }
57  }
58  }
59  vector<int> sets;
60  uf.GetSets(sets);
61  InverseMapping(sets,eq);
62  //remove empty sets
63  vector<vector<int> >::iterator it,prev;
64  int i=0;
65  int num=0;
66  for(it=eq.begin();it!=eq.end();it++,i++) {
67  num += (int)it->size();
68  if(it->empty()) {
69  prev = it; prev--;
70  eq.erase(it);
71  it = prev;
72  }
73  }
74  Assert(num==n);
75 }
76 
77 
78 #endif
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