CluE  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
balcanblumgupta.h
Go to the documentation of this file.
1 #ifndef BALCANBLUMGUPTA_H
2 #define BALCANBLUMGUPTA_H
3 
4 #include <map>
5 #include <lemon/list_graph.h>
6 
7 #include "../base/algorithm.h"
8 #include "../base/dissimilaritymeasure.h"
9 #include "../base/inputsetter.h"
10 #include "../base/measuresetter.h"
11 #include "../datastructure/partitionsolution.h"
12 
13 #include "../exception/invalidruntimeconfigurationexception.h"
14 #include "../exception/invalidargumentexception.h"
15 
16 namespace CluE
17 {
26 template<typename T> class BalcanBlumGupta : public Algorithm, public InputSetter<T>, public MeasureSetter<T>
27 {
28 public:
29 
30  BalcanBlumGupta(DissimilarityMeasure<T> const *measure = 0, std::vector<T*> const* input = 0, unsigned int numOfPartitons = 1);
31 
34  virtual ~BalcanBlumGupta();
35 
41  virtual PartitionSolution<T>* compute();
42 
43  virtual void setInput(std::vector<T*> const*);
44 
45  virtual void setMeasure(DissimilarityMeasure<T> const *measure);
46 
51  void setAlpha(double alpha);
52 
57  void setBeta(double beta);
58 
63  void setEpsilon(double epsilon);
64 
68  void setOmega(double omega);
69 
74  void setNumberOfPartitions(unsigned int number);
75 
81 
82 private:
84  std::vector<T*> const *input;
85  unsigned int numPartitions;
86  double alpha;
87  double beta;
88  double epsilon;
89  double omega;
90 };
91 
92 template<typename T> BalcanBlumGupta<T>::BalcanBlumGupta(DissimilarityMeasure<T> const *measure, std::vector<T*> const* input, unsigned int numOfPartitons) :
93  measure(measure==0 ? 0 : measure->clone()),
94  input(input),
95  numPartitions(numOfPartitons),
96  alpha(1),
97  beta(4),
98  epsilon(1),
99  omega(1)
100 {
101 }
102 
103 template<typename T> BalcanBlumGupta<T>::BalcanBlumGupta(const BalcanBlumGupta<T>& bbg) :
104  measure(bbg.measure==0 ? 0 : bbg.measure->clone()),
105  input(bbg.input),
106  numPartitions(bbg.numPartitions),
107  alpha(bbg.alpha),
108  beta(bbg.beta),
109  epsilon(bbg.epsilon),
110  omega(1)
111 {
112 }
113 
115 {
116  if(measure != 0)
117  delete measure;
118 
119  Algorithm::operator= (bbg);
120 
121  measure = bbg.measure == 0 ? 0 : bbg.measure->clone();
122  input = bbg.input;
123  epsilon = bbg.epsilon;
124  alpha = bbg.alpha;
125  beta = bbg.beta;
126  numPartitions = bbg.numPartitions;
127  omega = bbg.omega;
128 
129  return *this;
130 }
131 
133 {
134  if(measure != 0)
135  delete measure;
136 }
137 
139 {
140  using namespace lemon;
141 
142  if(this->input == 0)
143  throw InvalidRuntimeConfigurationException(0, "Input is NULL.");
144  if(this->measure == 0)
145  throw InvalidRuntimeConfigurationException(1, "Dissimilarity measure is NULL.");
146 
147  size_t inputSize = input->size();
148  double tau = (alpha * omega) / (5 * beta * epsilon);
149 
150  //Step 1
151  ListGraph threshGraph;
152  ListGraph::NodeMap<T*> tMap(threshGraph);
153  std::map<T*, ListGraph::Node> tNodeMap;
154  for(size_t i = 0; i < inputSize; i++)
155  {
156  ListGraph::Node u = threshGraph.addNode();
157  tMap[u] = (*input)[i];
158  tNodeMap[(*input)[i]] = u;
159  }
160  for(size_t i = 0; i < inputSize; i++)
161  {
162  for(size_t j = i+1; j < inputSize; j++)
163  {
164  T* p = (*input)[i];
165  T* q = (*input)[j];
166  if(measure->dissimilarity(*p, *q) < tau)
167  threshGraph.addEdge(tNodeMap[p], tNodeMap[q]);
168  }
169  }
170 
171  //Step 2
172  PartitionSolution<T> *solution = new PartitionSolution<T>();
173  solution->partitions.push_back(std::vector<std::vector<T*> >());
174  for(size_t i = 0; i < numPartitions-1; i++)
175  {
176  solution->partitions[0].push_back(std::vector<T*>());
177  std::vector<T*>& partition = solution->partitions[0].back();
178 
179  int maxEdges = 0;
180  ListGraph::Node maxNode = INVALID;
181  for(ListGraph::NodeIt u(threshGraph); u != INVALID; ++u)
182  {
183  int edges = countIncEdges(threshGraph, u);
184  if(edges > maxEdges)
185  {
186  maxEdges = edges;
187  maxNode = u;
188  }
189  }
190  if(maxNode == INVALID)
191  throw InvalidRuntimeConfigurationException(2, "Threshold graph: Empty node set.");
192 
193  std::vector<ListGraph::Node> nodesToErase;
194  for(ListGraph::IncEdgeIt e(threshGraph, maxNode); e != INVALID; ++e)
195  {
196  ListGraph::Node n;
197  if(threshGraph.u(e) != maxNode)
198  n = threshGraph.u(e);
199  else
200  n = threshGraph.v(e);
201  partition.push_back(tMap[n]);
202  nodesToErase.push_back(n);
203  }
204  partition.push_back(tMap[maxNode]);
205  for(std::vector<ListGraph::Node>::iterator it = nodesToErase.begin(); it != nodesToErase.end(); it++)
206  threshGraph.erase(*it);
207  threshGraph.erase(maxNode);
208  }
209 
210  solution->partitions[0].push_back(std::vector<T*>());
211  std::vector<T*>& partition = solution->partitions[0].back();
212  for(ListGraph::NodeIt u(threshGraph); u != INVALID; ++u)
213  partition.push_back(tMap[u]);
214 
215  return solution;
216 }
217 
218 template<typename T> void BalcanBlumGupta<T>::setNumberOfPartitions(unsigned int numOfPartitions)
219 {
220  this->numPartitions = numOfPartitions;
221 }
222 
223 template<typename T> void BalcanBlumGupta<T>::setAlpha(double alpha)
224 {
225  if(alpha > 0)
226  this->alpha = alpha;
227  else
228  throw InvalidArgumentException(0, "The given value of alpha is invalid. No changes were made.", "alpha");
229 }
230 
231 template<typename T> void BalcanBlumGupta<T>::setBeta(double beta)
232 {
233  if(beta > 0)
234  this->beta = beta;
235  else
236  throw InvalidArgumentException(0, "The given value of beta is invalid. No changes were made.", "beta");
237 }
238 
239 template<typename T> void BalcanBlumGupta<T>::setEpsilon(double epsilon)
240 {
241  if(epsilon > 0)
242  this->epsilon = epsilon;
243  else
244  throw InvalidArgumentException(0, "The given value of epsilon is invalid. No changes were made.", "epsilon");
245 }
246 
247 template<typename T> void BalcanBlumGupta<T>::setOmega(double omega)
248 {
249  this->omega = omega;
250 }
251 
252 template<typename T> void BalcanBlumGupta<T>::setInput(std::vector<T*> const* data)
253 {
254  this->input = data;
255 }
256 
257 template<typename T> void BalcanBlumGupta<T>::setMeasure(DissimilarityMeasure<T> const *measure)
258 {
259  if(this->measure != 0)
260  delete this->measure;
261 
262  if(measure == 0)
263  this->measure = 0;
264  else
265  this->measure = measure->clone();
266 }
267 
269 {
270  return dynamic_cast<BalcanBlumGupta<T>*>(s);
271 }
272 
273 }
274 #endif
std::vector< std::vector< std::vector< T * > > > partitions
void setEpsilon(double epsilon)
virtual void setInput(std::vector< T * > const *)
void setOmega(double omega)
virtual void setMeasure(DissimilarityMeasure< T > const *measure)
DissimilarityMeasure< T > * measure
virtual DissimilarityMeasure< T > * clone() const =0
void setBeta(double beta)
unsigned int numPartitions
Abstract base class for algorithms.
Definition: algorithm.h:17
virtual PartitionSolution< T > * compute()
void setAlpha(double alpha)
BalcanBlumGupta< T > & operator=(const BalcanBlumGupta< T > &)
Interface to propagate the ability to set a DissimilarityMeasure.
Definition: measuresetter.h:13
Indicates invalid values of arguments.
std::vector< T * > const * input
BalcanBlumGupta algorithm.
void setNumberOfPartitions(unsigned int number)
Sets the desired number of partitions.
BalcanBlumGupta(DissimilarityMeasure< T > const *measure=0, std::vector< T * > const *input=0, unsigned int numOfPartitons=1)
Abstract base class for dissimilarity measurement.
Indicates that a computation entered an invalid configuration state.
static BalcanBlumGupta< T > * toBalcanBlumGupta(Algorithm *s)
does a dynamic cast of the given Algorithm to BalcanBlumGupta
Data structure for partitions.
Interface to propagate the ability to set input data.
Definition: inputsetter.h:13