CluE  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
farthestfirsttraversal.h
Go to the documentation of this file.
1 #ifndef FARTHESFIRSTSAMPLING_H
2 #define FARTHESFIRSTSAMPLING_H
3 
4 #include <ctime>
5 
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"
12 
13 #include "../exception/invalidruntimeconfigurationexception.h"
14 
15 namespace CluE
16 {
17 
30 template<typename T> class FarthestFirstTraversal : public Algorithm, public InputSetter<T>, public MeasureSetter<T>
31 {
32 public:
40  FarthestFirstTraversal(DissimilarityMeasure<T> const * measure = 0, std::vector<T*> const* input = 0, unsigned int numOfSamples = 0, unsigned int firstPoint = 0);
41 
44  virtual ~FarthestFirstTraversal();
45 
54  virtual SolutionProvider* compute();
55 
56  virtual void setInput(std::vector<T*> const*);
57 
58  virtual void setMeasure(DissimilarityMeasure<T> const * measure);
59 
63  void setNumberOfSamples(unsigned int number);
64 
68  void setFirstPoint(unsigned int index);
69 
75 
76 private:
77  std::vector<T*> const* input;
79  unsigned int number_of_samples;
80  unsigned int first_point;
81 };
82 
83 template<typename T> FarthestFirstTraversal<T>::FarthestFirstTraversal(DissimilarityMeasure<T> const *measure, std::vector<T*> const* data, unsigned int n, unsigned int s) :
84  input(data),
85  measure(measure==0 ? 0 : measure->clone()),
86  number_of_samples(n),
87  first_point(s)
88 {
89 }
90 
92  input(fft.input),
93  measure(fft.measure == 0 ? 0 : fft.measure->clone()),
94  number_of_samples(fft.number_of_samples),
95  first_point(fft.number_of_samples)
96 {
97 }
98 
100 {
101  if(measure != 0)
102  delete measure;
103 
104  Algorithm::operator= (fft);
105 
106  input = fft.input;
107  measure == fft.measure == 0 ? 0 : fft.measure->clone();
108  number_of_samples = fft.number_of_samples;
109  first_point = fft.number_of_samples;
110 
111  return *this;
112 }
113 
115 {
116  if(measure != 0)
117  delete measure;
118 }
119 
121 {
123  unsigned int inputSize = this->input->size();
124 
125  if(this->input == 0)
126  throw InvalidRuntimeConfigurationException(0, "Input is NULL.");
127  if(this->measure == 0)
128  throw InvalidRuntimeConfigurationException(1, "Dissimilarity measure is NULL.");
129  if(inputSize == 0)
130  throw InvalidRuntimeConfigurationException(2, "Empty input set.");
131  if(this->number_of_samples == 0)
132  throw InvalidRuntimeConfigurationException(3, "Desired number of samples is 0.");
133  if(this->number_of_samples > inputSize)
134  throw InvalidRuntimeConfigurationException(4, "Desired number of samples is larger than input size.");
135 
136  time_t start, end;
137  start = std::time(0);
138 
139  std::vector<T*> numberedPoints;
140  unsigned int max = this->number_of_samples > 0 ? this->number_of_samples : inputSize;
141  DynamicBitset<> isNumbered(inputSize);
142 
143  //First point
144  T* firstPoint = (*this->input)[this->first_point];
145  isNumbered.set(this->first_point, true);
146  numberedPoints.push_back(firstPoint);
147 
148  //Min-distance caching
149  std::vector<double> distances;
150  for(unsigned int i = 0; i < inputSize; i++)
151  {
152  distances.push_back(this->measure->dissimilarity(*firstPoint, *(*this->input)[i]));
153  }
154 
155  for(unsigned int i = 1; i < max; i++)
156  {
157  bool next_found = false;
158  unsigned int next_number = 0;
159  double next_distance = 0;
160 
161  for(unsigned int j = 0; j < inputSize; j++)
162  {
163  if(isNumbered[j])
164  continue;
165 
166  //min(cached distance of candidate, distance between last numbered point and candidate)
167  double testDist = measure->dissimilarity(*numberedPoints[i-1], * (*this->input)[j]);
168  if(testDist < distances[j])
169  distances[j] = testDist;
170 
171  if(distances[j] > next_distance || !next_found)
172  {
173  next_found = true;
174  next_number = j;
175  next_distance = distances[j];
176  }
177  }
178 
179  isNumbered.set(next_number, true);
180  numberedPoints.push_back((*this->input)[next_number]);
181  }
182 
183  end = time(0);
184  solution->proxysets.push_back(numberedPoints);
185  solution->seconds = end-start;
186 
187  return solution;
188 }
189 
190 template<typename T> void FarthestFirstTraversal<T>::setInput(std::vector<T*> const* data)
191 {
192  this->input = data;
193 }
194 
195 template<typename T> void FarthestFirstTraversal<T>::setFirstPoint(unsigned int s)
196 {
197  this->first_point = s;
198 }
199 
200 template<typename T> void FarthestFirstTraversal<T>::setNumberOfSamples(unsigned int n)
201 {
202  this->number_of_samples = n;
203 }
204 
206 {
207  return dynamic_cast<FarthestFirstTraversal<T>*>(s);
208 }
209 
210 template<typename T> void FarthestFirstTraversal<T>::setMeasure(DissimilarityMeasure<T> const *measure)
211 {
212  if(this->measure != 0)
213  delete this->measure;
214 
215  if(measure == 0)
216  this->measure = 0;
217  else
218  this->measure = measure->clone();
219 }
220 
221 }
222 #endif
void setNumberOfSamples(unsigned int number)
Sets the desired number of proxies.
virtual void setMeasure(DissimilarityMeasure< T > const *measure)
Data structure for discrete proxies.
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.
Definition: dynamicbitset.h:15
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.
Definition: algorithm.h:17
void setFirstPoint(unsigned int index)
Sets the starting point.
Interface to propagate the ability to set a DissimilarityMeasure.
Definition: measuresetter.h:13
void set(size_t position, bool value)
Write access to the (position+1)-th bit.
Definition: dynamicbitset.h:67
Farthest first traversal algorithm.
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
Interface to propagate the ability to set input data.
Definition: inputsetter.h:13