-
Notifications
You must be signed in to change notification settings - Fork 0
/
Taxonomy1.cpp
145 lines (120 loc) · 5.09 KB
/
Taxonomy1.cpp
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <algorithm>
#include <boost/bind.hpp>
#include <boost/noncopyable.hpp>
#include <boost/functional/hash.hpp>
#include "LookupTable.h"
#include "Taxonomy1.h"
class Taxonomy1Evaluator {
typedef std::vector<unsigned long> InnerFrequencyVector;
const std::set<Partition>& pOrbit;
public:
typedef std::multiset<InnerFrequencyVector> FrequencyVector;
Taxonomy1Evaluator(const std::set<Partition>& _pOrbit) : pOrbit(_pOrbit) {}
FrequencyVector operator()(const Subset& B) const {
FrequencyVector result;
for (std::set<Partition>::const_iterator it = pOrbit.begin(); it != pOrbit.end(); ++it) {
// Construct the inner frequency vector, similar to the Anchor Set approach
InnerFrequencyVector fv(B.size() + 1);
for (Partition::const_iterator jt = it->begin(); jt != it->end(); ++jt) {
fv[setIntersection(*jt, B).size()]++;
}
result.insert(fv);
}
return result;
}
};
/* ************************************************************************************************** */
class Taxonomy1LookupTable : public SizeIndependentLookupTable<Taxonomy1Evaluator> {
typedef SizeIndependentLookupTable<Taxonomy1Evaluator> super_type;
public:
typedef super_type::mapped_type Subtable;
Taxonomy1LookupTable(const Taxonomy1& fn) : super_type(fn.createEvaluator()) {}
};
/* ************************************************************************************************** */
class Taxonomy1EvalCache : public boost::noncopyable, public HeapValueStdMapCache<Taxonomy1, Taxonomy1LookupTable, HeapValueFromKeyInsertDelegate<Taxonomy1LookupTable>, Taxonomy1WeakOrdering>::type {
// boost::noncopyable also implicitly deletes move constructors
public:
static Taxonomy1EvalCache& getInstance() {
static Taxonomy1EvalCache instance;
return instance;
}
private:
Taxonomy1EvalCache() {}
};
/* ************************************************************************************************** */
// Taxonomy1WeakOrdering methods
bool Taxonomy1WeakOrdering::operator()(const Taxonomy1& lhs, const Taxonomy1& rhs) const {
if (GroupWeakOrdering()(lhs.getGroup(), rhs.getGroup())) return true;
// As Permutation is a wrapper around std::vector (of some integral type), but doesn't actually have
// operator<() implemented, we have to reinvent the wheel here. We can't even use std::lexicographical_compare()
// since we don't have iterators either!
const Permutation& leftPerm = lhs.getBasePerm();
const Permutation& rightPerm = rhs.getBasePerm();
int il = 0;
int ir = 0;
while (il != leftPerm.size()) {
if (ir == rightPerm.size() || rightPerm.at(ir) < leftPerm.at(il)) return false;
else if (leftPerm.at(il) < rightPerm.at(ir)) return true;
il++;
ir++;
}
return ir != rightPerm.size();
}
/* ************************************************************************************************** */
// Taxonomy1 methods
/**
* Creates a new Taxonomy1 from a permutation in the group.
* Precondition: basePerm must be a permutation from the group G.
*/
Taxonomy1::Taxonomy1(const Group& G, const Permutation& _basePerm) :
GInvariant(G), basePerm(_basePerm), pOrbit() {
// The subgroup generated by basePerm has a system of orbits that partitions X = {1, .., v}
// To get to this partition we simply interpret the disjoint cycle form as a set of subsets.
Partition partition;
std::vector<Cycle> cycleForm = permutationCycles(basePerm, G.getNumPoints());
for (std::vector<Cycle>::const_iterator it = cycleForm.begin(); it != cycleForm.end(); it++) {
partition.insert(Subset(it->begin(), it->end()));
}
// Then generate the orbit of the partition as follows: a Permutation in G acts on the partition
// by acting on each Subset individually, so the result is a set of Subsets.
for (GroupElementIterator it = G.elementsBegin(); it != G.elementsEnd(); it++) {
Permutation g = *it;
Partition image;
for (Partition::const_iterator jt = partition.begin(); jt != partition.end(); jt++) {
// Apply g to *jt
Subset p;
std::transform(jt->begin(), jt->end(), std::inserter(p, p.begin()), boost::bind(&Permutation::at, g, _1));
image.insert(p);
}
pOrbit.insert(image);
}
}
/**
* Compares Taxonomy1 for equality.
*
* Two Taxonomy1 instances over the same group are equal if they are generated by the same element.
*/
bool Taxonomy1::equals(const GInvariant& rhs) const {
if (!GInvariant::equals(rhs)) return false;
const Taxonomy1& other = static_cast<const Taxonomy1&>(rhs);
return basePerm == other.basePerm;
}
std::size_t Taxonomy1::hash() const {
std::size_t seed = 0;
boost::hash_combine(seed, getGroup());
boost::hash_combine(seed, getBasePerm());
return seed;
}
Taxonomy1::Evaluator Taxonomy1::createEvaluator() const {
return Evaluator(pOrbit);
}
unsigned long Taxonomy1::evaluate(const Subset& B) const {
Taxonomy1LookupTable& cache = Taxonomy1EvalCache::getInstance().query(*this);
Taxonomy1LookupTable::Subtable& table = cache.query(B.size());
return table.query(B);
}
bool Taxonomy1::hasCachedResult(const Subset& B) const {
Taxonomy1LookupTable& cache = Taxonomy1EvalCache::getInstance().query(*this);
Taxonomy1LookupTable::Subtable& table = cache.query(B.size());
return table.contains(B);
}