29 #include "../../graph/core/Edge.h"
30 #include "../../graph/core/Vertex.h"
31 #include "../../graph/iterator/MemoryIterator.h"
61 int firstVertex = memIt->getFirstVertex()->getId();
64 std::vector< std::pair<int, double> > rootSet;
65 rootSet.push_back(std::vector< std::pair<int, double> >::value_type(firstVertex, 0.));
67 std::vector<std::size_t> rootsVertexId;
70 while(!rootSet.empty() && (rootSet.size() + rootsVertexId.size() < nGroups))
73 std::vector< std::pair<int, double> >::iterator rootIt;
74 std::vector< std::pair<int, double> >::iterator rootItMax;
75 double maxDiff = -std::numeric_limits<double>::max();
77 for(rootIt = rootSet.begin(); rootIt != rootSet.end(); ++rootIt)
79 if(rootIt->second > maxDiff)
81 maxDiff = rootIt->second;
86 std::size_t currentId = rootItMax->first;
88 rootSet.erase(rootItMax);
100 bool remove = edgeToRemove(currentId, diffA, diffB, edgeId);
107 int vertexTo = edge->
getIdTo();
110 m_graph->removeEdge(edgeId);
112 rootSet.push_back(std::vector< std::pair<int, double> >::value_type(vertexFrom, diffA));
113 rootSet.push_back(std::vector< std::pair<int, double> >::value_type(vertexTo, diffB));
117 rootsVertexId.push_back(currentId);
122 for(std::size_t t = 0; t < rootSet.size(); ++t)
124 rootsVertexId.push_back(rootSet[t].first);
127 return rootsVertexId;
140 int firstVertex = memIt->getFirstVertex()->getId();
143 std::vector< std::pair<int, double> > rootSet;
144 rootSet.push_back(std::vector< std::pair<int, double> >::value_type(firstVertex, 0.));
146 std::vector<std::size_t> rootsVertexId;
149 while(!rootSet.empty())
152 std::vector< std::pair<int, double> >::iterator rootIt;
153 std::vector< std::pair<int, double> >::iterator rootItMax;
154 double maxDiff = -std::numeric_limits<double>::max();
156 for(rootIt = rootSet.begin(); rootIt != rootSet.end(); ++rootIt)
158 if(rootIt->second > maxDiff)
160 maxDiff = rootIt->second;
165 std::size_t currentId = rootItMax->first;
167 rootSet.erase(rootItMax);
179 bool remove = edgeToRemove(currentId, diffA, diffB, edgeId);
186 int vertexTo = edge->
getIdTo();
189 m_graph->removeEdge(edgeId);
191 rootSet.push_back(std::vector< std::pair<int, double> >::value_type(vertexFrom, diffA));
192 rootSet.push_back(std::vector< std::pair<int, double> >::value_type(vertexTo, diffB));
196 rootsVertexId.push_back(currentId);
201 for(std::size_t t = 0; t < rootSet.size(); ++t)
203 rootsVertexId.push_back(rootSet[t].first);
206 return rootsVertexId;
212 std::vector<EdgeRemovalInfo> edgeRemovalVec;
215 std::size_t totalPop = 0;
216 std::vector<double> meanVecStart = calculateRootMean(startVertex, -1, totalPop);
217 double deviationStart = calculateRootDeviation(startVertex, -1, meanVecStart);
220 std::queue<int> queue;
221 std::set<int> visited;
223 queue.push(startVertex);
224 visited.insert(startVertex);
227 while(!queue.empty())
229 int currentId = queue.front();
239 std::set<int>::iterator itNeighbours = neighbours.begin();
241 while(itNeighbours != neighbours.end())
249 vTo = m_graph->getVertex(e->
getIdTo());
251 vTo = m_graph->getVertex(e->
getIdFrom());
257 if(visited.find(vTo->
getId()) == visited.end())
260 queue.push(vTo->
getId());
261 visited.insert(vTo->
getId());
264 double diffVFrom = 0.;
266 std::size_t popA = 0;
267 std::size_t popB = 0;
269 double ssdi = calculateEdgeDifference(vertex->
getId(), vTo->
getId(), diffVFrom, diffVTo, popA, popB);
271 double l = deviationStart - ssdi;
275 eri.
m_SSDT = deviationStart;
293 edgeRemovalVec.push_back(eri);
305 double maxDiff = -std::numeric_limits<double>::max();
307 for(std::size_t t = 0; t < edgeRemovalVec.size(); ++t)
309 if(edgeRemovalVec[t].m_l > maxDiff && edgeRemovalVec[t].m_popa >= m_popMin && edgeRemovalVec[t].m_popb >= m_popMin)
311 maxDiff = edgeRemovalVec[t].m_l;
313 edgeToRemoveId = edgeRemovalVec[t].m_edgeId;
315 diffA = edgeRemovalVec[t].m_SSDTa;
316 diffB = edgeRemovalVec[t].m_SSDTb;
323 m_SSDiValues.push_back(maxDiff);
325 edgeRemovalVec.clear();
333 std::vector<double> meanVecFrom = calculateRootMean(vertexFrom, vertexTo, popA);
334 diffA = calculateRootDeviation(vertexFrom, vertexTo, meanVecFrom);
337 std::vector<double> meanVecTo = calculateRootMean(vertexTo, vertexFrom, popB);
338 diffB = calculateRootDeviation(vertexTo, vertexFrom, meanVecTo);
341 return diffA + diffB;
346 std::vector<double> meanAttrs(m_attrs.size(), 0.);
348 std::queue<int> queue;
349 std::set<int> visited;
351 queue.push(startVertex);
352 visited.insert(startVertex);
354 std::size_t count = 0;
356 while(!queue.empty())
358 int currentId = queue.front();
365 for(std::size_t t = 0; t < m_attrs.size(); ++t)
367 std::string attrName = m_attrs[t];
386 std::set<int>::iterator itNeighbours = neighbours.begin();
388 while(itNeighbours != neighbours.end())
396 vTo = m_graph->getVertex(e->
getIdTo());
398 vTo = m_graph->getVertex(e->
getIdFrom());
401 if(vTo && vTo->
getId() != vertexToIgnore)
403 if(visited.find(vTo->
getId()) == visited.end())
405 queue.push(vTo->
getId());
406 visited.insert(vTo->
getId());
417 for(std::size_t t = 0; t < m_attrs.size(); ++t)
419 meanAttrs[t] /= count;
427 double deviation = 0.;
429 std::queue<int> queue;
430 std::set<int> visited;
432 queue.push(startVertex);
433 visited.insert(startVertex);
435 while(!queue.empty())
437 int currentId = queue.front();
444 deviation += calculateDistance(vertex, meanVec);
448 std::set<int>::iterator itNeighbours = neighbours.begin();
450 while(itNeighbours != neighbours.end())
458 vTo = m_graph->getVertex(e->
getIdTo());
460 vTo = m_graph->getVertex(e->
getIdFrom());
463 if(vTo && vTo->
getId() != vertexToIgnore)
465 if(visited.find(vTo->
getId()) == visited.end())
467 queue.push(vTo->
getId());
468 visited.insert(vTo->
getId());
482 double distance = 0.;
484 for(std::size_t t = 0; t < m_attrs.size(); ++t)
486 std::string attrName = m_attrs[t];
double m_SSDTa
Sum of Square Difference for Tree A.
SkaterPartition(te::graph::AbstractGraph *graph, std::vector< std::string > attrs)
Default constructor.
A struct that represents the skater partition values for each edge.
int getId()
It returns the edge identification.
std::vector< te::dt::AbstractData * > & getAttributes()
It returns the vector of attributes associated with this element.
double calculateRootDeviation(int startVertex, int vertexToIgnore, std::vector< double > &meanVec)
Utilitary function for spatial analysis module.
From the point of view of graph theory, vertices are treated as featureless and indivisible objects...
Class used to define the edge struct of a graph. Its compose with a identifier, the vertex origin and...
std::vector< double > calculateRootMean(int startVertex, int vertexToIgnore, std::size_t &pop)
This file contains a class that represents the skater partition operation.
~SkaterPartition()
Virtual destructor.
std::vector< std::size_t > execute(std::size_t nGroups, std::string popAttr="", std::size_t minPop=0)
Function to execute the skater partition.
Abstract class used to define the main functions of graph struct. All graph implementations must used...
double m_l
Difference between m_SSDT and m_SSDi;.
std::size_t m_edgeId
Edge identification.
std::size_t m_popa
Sum of population for Tree A.
int getIdFrom()
It returns the vertex origin identification.
std::set< int > & getNeighborhood()
Returns the Neighborhood vector.
bool edgeToRemove(int startVertex, double &diffA, double &diffB, std::size_t &edgeToRemoveId)
double m_SSDi
Sum of m_SSDa and m_SSDb.
double calculateEdgeDifference(int vertexFrom, int vertexTo, double &diffA, double &diffB, std::size_t &popA, std::size_t &popB)
TESAEXPORT bool GetGraphVertexAttrIndex(te::graph::AbstractGraph *graph, std::string attrName, int &index)
Function used to get the vertex attribute index in the graph of the gpm.
std::size_t m_popb
Sum of population for Tree B.
double m_SSDT
Sum of Square Difference for Tree.
int getId()
It returns the vertex id.
TESAEXPORT double GetDataValue(te::dt::AbstractData *ad)
Function used to get the numeric value from a gpm property.
double m_SSDTb
Sum of Square Difference for Tree B.
te::graph::AbstractGraph * m_graph
Pointer to a graph that represents a minimum spanning tree.
std::vector< std::string > m_attrs
Vector with attributes names used to calculate the skater operation.
double calculateDistance(te::graph::Vertex *vertex, std::vector< double > &meanVec)
int getIdTo()
It returns the vertex destiny identification.