6 #include "../base/algorithm.h"
7 #include "../base/inputsetter.h"
8 #include "../base/measuresetter.h"
9 #include "../datastructure/partitionsolution.h"
10 #include "../sampling/farthestfirsttraversal.h"
11 #include "../misc/dynamicbitset.h"
13 #include "../exception/invalidruntimeconfigurationexception.h"
14 #include "../exception/invalidargumentexception.h"
50 virtual void setInput(std::vector<T*>
const*);
82 measure(measure==0 ? 0 : measure->clone()),
91 measure(dl.measure == 0 ? 0 : dl.measure->clone()),
93 first_point(first_point),
104 Algorithm::operator= (dl);
108 first_point = first_point;
124 unsigned int numOfPoints = this->input->size();
128 if(this->measure == 0)
137 std::vector<T*> *numberedPoints = &dps->
proxysets[0];
140 std::vector<double> rValues;
141 std::vector<unsigned int> rPoints;
142 rValues.push_back(0);
143 for(
unsigned int i = 1; i < numOfPoints; i++)
145 double minDist = measure->dissimilarity(* (*numberedPoints)[i], * (*numberedPoints)[0]);
146 for(
unsigned int j = 1; j < i; j++)
148 double candDist = measure->dissimilarity(* (*numberedPoints)[i], * (*numberedPoints)[j]);
149 if(candDist < minDist)
152 rValues.push_back(minDist);
154 double r = alpha * rValues[1];
158 isLeveled.
set(first_point,
true);
160 std::vector<std::vector<unsigned int> > lValues;
161 lValues.push_back(std::vector<unsigned int>());
162 lValues[0].push_back(first_point);
163 for(
unsigned int i = 1; isLeveled.
count() < numOfPoints; i++)
165 lValues.push_back(std::vector<unsigned int>());
167 double lowerBound = r / std::pow(beta, (
double) i);
168 double upperBound = r / std::pow(beta, (
double)(i-1));
169 for(
unsigned int j = 0; j < numOfPoints; j++)
174 if(lowerBound < rValues[j] && rValues[j] <= upperBound)
176 isLeveled.
set(j,
true);
177 lValues[i].push_back(j);
183 unsigned int pi[numOfPoints];
185 unsigned int levels = lValues.size();
186 for(
unsigned int level = 1; level < levels; level++)
189 unsigned int levelSize = lValues[level].size();
190 for(
unsigned int levelIndex = 0; levelIndex < levelSize; levelIndex++)
193 T* currentPoint = (*numberedPoints)[lValues[level][levelIndex]];
194 double minDist = measure->dissimilarity(*currentPoint, * (*numberedPoints)[first_point]);
195 unsigned int minPoint = first_point;
196 for(
unsigned int lowerLevel = 1; lowerLevel < level; lowerLevel++)
199 unsigned int lowerLevelSize = lValues[lowerLevel].size();
200 for(
unsigned int lowerLevelIndex = 0; lowerLevelIndex < lowerLevelSize; lowerLevelIndex++)
203 double candDist = measure->dissimilarity(*currentPoint, * (*numberedPoints)[lValues[lowerLevel][lowerLevelIndex]]);
204 if(candDist < minDist)
207 minPoint = lValues[lowerLevel][lowerLevelIndex];
211 pi[lValues[level][levelIndex]] = minPoint;
229 std::vector<std::vector<std::vector<T*> > >& sets = solution->
partitions;
230 for(
unsigned int i = 0; i < levels; i++)
232 sets.push_back(std::vector<std::vector<T*> >());
233 std::vector<std::vector<T*> >& partitions = sets.back();
235 unsigned int recursivePi[numOfPoints];
237 for(
unsigned int j = 0; j <= i; j++)
239 unsigned int size = lValues[j].size();
240 for(
unsigned int k = 0; k < size; k++)
242 partitions.push_back(std::vector<T*>());
243 recursivePi[lValues[j][k]] = partitions.size()-1;
247 for(
unsigned int j = i+1; j < levels; j++)
249 unsigned int size = lValues[j].size();
250 for(
unsigned int k = 0; k < size; k++)
252 unsigned int index = lValues[j][k];
253 recursivePi[index] = recursivePi[pi[index]];
258 for(
unsigned int i = 0; i < numOfPoints; i++)
260 partitions[recursivePi[i]].push_back((*numberedPoints)[i]);
274 this->first_point = s;
304 if(this->measure != 0)
305 delete this->measure;
310 this->measure = measure->
clone();
std::vector< std::vector< std::vector< T * > > > partitions
DasguptaLong(DissimilarityMeasure< T > const *measure=0, std::vector< T * > const *input=0, unsigned int firstPoint=0)
Constructor for general usage.
DissimilarityMeasure< T > * measure
Data structure for discrete proxies.
unsigned long long count()
Number of set bits.
virtual void setMeasure(DissimilarityMeasure< T > const *measure)
std::vector< std::vector< T * > > proxysets
Dynamic bitset similiar to boost::dynamic_bitset.
std::vector< T * > const * input
virtual DissimilarityMeasure< T > * clone() const =0
void setGranularity(double alpha, double beta)
Sets the granularity.
Abstract base class for algorithms.
virtual void setInput(std::vector< T * > const *)
static DasguptaLong< T > * toDasguptaLong(Algorithm *s)
does a dynamic cast of the given Algorithm to DasguptaLong
Interface to propagate the ability to set a DissimilarityMeasure.
void set(size_t position, bool value)
Write access to the (position+1)-th bit.
Indicates invalid values of arguments.
Farthest first traversal algorithm.
Abstract base class for dissimilarity measurement.
virtual SolutionProvider * compute()
Indicates that a computation entered an invalid configuration state.
virtual SolutionProvider * compute()
Returns an ordered DiscretesProxySolution. The first point is the starting point. ...
DasguptaLong< T > & operator=(const DasguptaLong< T > &)
Abstract base class for algorithm solutions.
void setFirstPoint(unsigned int index)
Sets the starting point for farthest first traversal.
Data structure for partitions.