1 #ifndef FARTHESFIRSTSAMPLING_H
2 #define FARTHESFIRSTSAMPLING_H
6 #include "../base/inputsetter.h"
7 #include "../base/measuresetter.h"
8 #include "../base/algorithm.h"
9 #include "../datastructure/discreteproxysolution.h"
10 #include "../base/dissimilaritymeasure.h"
11 #include "../misc/dynamicbitset.h"
13 #include "../exception/invalidruntimeconfigurationexception.h"
56 virtual void setInput(std::vector<T*>
const*);
85 measure(measure==0 ? 0 : measure->clone()),
93 measure(fft.measure == 0 ? 0 : fft.measure->clone()),
94 number_of_samples(fft.number_of_samples),
95 first_point(fft.number_of_samples)
104 Algorithm::operator= (fft);
123 unsigned int inputSize = this->input->size();
127 if(this->measure == 0)
131 if(this->number_of_samples == 0)
133 if(this->number_of_samples > inputSize)
137 start = std::time(0);
139 std::vector<T*> numberedPoints;
140 unsigned int max = this->number_of_samples > 0 ? this->number_of_samples : inputSize;
144 T* firstPoint = (*this->input)[this->first_point];
145 isNumbered.
set(this->first_point,
true);
146 numberedPoints.push_back(firstPoint);
149 std::vector<double> distances;
150 for(
unsigned int i = 0; i < inputSize; i++)
152 distances.push_back(this->measure->dissimilarity(*firstPoint, *(*this->input)[i]));
155 for(
unsigned int i = 1; i < max; i++)
157 bool next_found =
false;
158 unsigned int next_number = 0;
159 double next_distance = 0;
161 for(
unsigned int j = 0; j < inputSize; j++)
167 double testDist = measure->dissimilarity(*numberedPoints[i-1], * (*this->input)[j]);
168 if(testDist < distances[j])
169 distances[j] = testDist;
171 if(distances[j] > next_distance || !next_found)
175 next_distance = distances[j];
179 isNumbered.
set(next_number,
true);
180 numberedPoints.push_back((*this->input)[next_number]);
184 solution->
proxysets.push_back(numberedPoints);
197 this->first_point = s;
202 this->number_of_samples = n;
212 if(this->measure != 0)
213 delete this->measure;
218 this->measure = measure->
clone();
void setNumberOfSamples(unsigned int number)
Sets the desired number of proxies.
virtual void setMeasure(DissimilarityMeasure< T > const *measure)
Data structure for discrete proxies.
virtual ~FarthestFirstTraversal()
FarthestFirstTraversal(DissimilarityMeasure< T > const *measure=0, std::vector< T * > const *input=0, unsigned int numOfSamples=0, unsigned int firstPoint=0)
Constructor for general usage.
std::vector< std::vector< T * > > proxysets
Dynamic bitset similiar to boost::dynamic_bitset.
virtual DissimilarityMeasure< T > * clone() const =0
DissimilarityMeasure< T > * measure
virtual void setInput(std::vector< T * > const *)
static FarthestFirstTraversal< T > * toFarthestFirstTraversal(Algorithm *s)
does a dynamic cast of the given Algorithm to FarthestFirstTraversal
Abstract base class for algorithms.
void setFirstPoint(unsigned int index)
Sets the starting point.
Interface to propagate the ability to set a DissimilarityMeasure.
void set(size_t position, bool value)
Write access to the (position+1)-th bit.
Farthest first traversal algorithm.
unsigned int number_of_samples
Abstract base class for dissimilarity measurement.
FarthestFirstTraversal< T > & operator=(const FarthestFirstTraversal< T > &)
Indicates that a computation entered an invalid configuration state.
virtual SolutionProvider * compute()
Returns an ordered DiscretesProxySolution. The first point is the starting point. ...
Abstract base class for algorithm solutions.
std::vector< T * > const * input