1 #ifndef BALCANBLUMGUPTA_H
2 #define BALCANBLUMGUPTA_H
5 #include <lemon/list_graph.h>
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"
13 #include "../exception/invalidruntimeconfigurationexception.h"
14 #include "../exception/invalidargumentexception.h"
43 virtual void setInput(std::vector<T*>
const*);
93 measure(measure==0 ? 0 : measure->clone()),
95 numPartitions(numOfPartitons),
104 measure(bbg.measure==0 ? 0 : bbg.measure->clone()),
106 numPartitions(bbg.numPartitions),
109 epsilon(bbg.epsilon),
119 Algorithm::operator= (bbg);
140 using namespace lemon;
144 if(this->measure == 0)
147 size_t inputSize = input->size();
148 double tau = (alpha * omega) / (5 * beta * epsilon);
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++)
156 ListGraph::Node u = threshGraph.addNode();
157 tMap[u] = (*input)[i];
158 tNodeMap[(*input)[i]] = u;
160 for(
size_t i = 0; i < inputSize; i++)
162 for(
size_t j = i+1; j < inputSize; j++)
166 if(measure->dissimilarity(*p, *q) < tau)
167 threshGraph.addEdge(tNodeMap[p], tNodeMap[q]);
173 solution->
partitions.push_back(std::vector<std::vector<T*> >());
174 for(
size_t i = 0; i < numPartitions-1; i++)
176 solution->partitions[0].push_back(std::vector<T*>());
177 std::vector<T*>& partition = solution->partitions[0].back();
180 ListGraph::Node maxNode = INVALID;
181 for(ListGraph::NodeIt u(threshGraph); u != INVALID; ++u)
183 int edges = countIncEdges(threshGraph, u);
190 if(maxNode == INVALID)
193 std::vector<ListGraph::Node> nodesToErase;
194 for(ListGraph::IncEdgeIt e(threshGraph, maxNode); e != INVALID; ++e)
197 if(threshGraph.u(e) != maxNode)
198 n = threshGraph.u(e);
200 n = threshGraph.v(e);
201 partition.push_back(tMap[n]);
202 nodesToErase.push_back(n);
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);
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]);
220 this->numPartitions = numOfPartitions;
242 this->epsilon = epsilon;
259 if(this->measure != 0)
260 delete this->measure;
265 this->measure = measure->
clone();
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.
virtual PartitionSolution< T > * compute()
void setAlpha(double alpha)
BalcanBlumGupta< T > & operator=(const BalcanBlumGupta< T > &)
virtual ~BalcanBlumGupta()
Interface to propagate the ability to set a DissimilarityMeasure.
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.