20 #ifndef __PARTITION_H__
21 #define __PARTITION_H__
27 #include "Utility/Typedef.hpp"
28 #include "PartitioningStats.hpp"
34 namespace PARTITIONING
43 Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet);
59 unsigned int partitionId;
80 static unsigned int getMaxEdgesLoad(
const PartitionMap<T> &partitionMap);
90 static unsigned int getMinEdgesLoad(
const PartitionMap<T> &partitionMap);
100 static unsigned int getMaxNodesLoad(
const PartitionMap<T> &partitionMap);
109 template <
typename T>
110 static unsigned int getMinNodesLoad(
const PartitionMap<T> &partitionMap);
119 template <
typename T>
120 static unsigned int getNumberOfEdges(
const PartitionMap<T> &partitionMap);
129 template <
typename T>
130 static unsigned int getNumberOfNodes(
const PartitionMap<T> &partitionMap);
139 template <
typename T>
140 static unsigned int getNumberOfReplicatedEdges(
const PartitionMap<T> &partitionMap);
149 template <
typename T>
150 static unsigned int getNumberOfReplicatedNodes(
const PartitionMap<T> &partitionMap);
152 template <
typename T>
158 template <
typename T>
159 Partition<T>::Partition(
unsigned int partitionId) :
Graph<T>()
161 this->partitionId = partitionId;
164 template <
typename T>
165 Partition<T>::Partition(
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
170 template <
typename T>
171 Partition<T>::Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
173 this->partitionId = partitionId;
176 template <
typename T>
182 template <
typename T>
185 this->partitionId = partitionId;
188 template <
typename T>
192 result.numberOfPartitions = partitionMap.size();
193 result.numberOfNodes = getNumberOfNodes(partitionMap);
194 result.numberOfEdges = getNumberOfEdges(partitionMap);
195 result.replicatedNodesCount = getNumberOfReplicatedNodes(partitionMap);
196 result.replicatedEdgesCount = getNumberOfReplicatedEdges(partitionMap);
197 result.maxEdgesLoad = getMaxEdgesLoad(partitionMap);
198 result.minEdgesLoad = getMinEdgesLoad(partitionMap);
199 result.maxNodesLoad = getMaxNodesLoad(partitionMap);
200 result.minNodesLoad = getMinNodesLoad(partitionMap);
201 result.edgesReplicationFactor = (double)result.replicatedEdgesCount / result.numberOfEdges;
202 result.nodesReplicationFactor = (
double)result.replicatedNodesCount / result.numberOfNodes;
203 result.balanceEdgesFactor = (double)(result.maxEdgesLoad - result.minEdgesLoad) / (result.maxEdgesLoad);
204 result.balanceNodesFactor = (double)(result.maxNodesLoad - result.minNodesLoad) / (result.maxNodesLoad);
208 template <
typename T>
209 unsigned int getMaxEdgesLoad(
const PartitionMap<T> &partitionMap)
211 unsigned int maxLoad = 0;
212 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
214 if (it->second->getEdgeSet().size() > maxLoad)
216 maxLoad = it->second->getEdgeSet().size();
222 template <
typename T>
223 unsigned int getMinEdgesLoad(
const PartitionMap<T> &partitionMap)
225 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
226 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
228 if (it->second->getEdgeSet().size() < minLoad)
230 minLoad = it->second->getEdgeSet().size();
236 template <
typename T>
237 unsigned int getMaxNodesLoad(
const PartitionMap<T> &partitionMap)
239 unsigned int maxLoad = 0;
240 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
242 if (it->second->getNodeSet().size() > maxLoad)
244 maxLoad = it->second->getNodeSet().size();
250 template <
typename T>
251 unsigned int getMinNodesLoad(
const PartitionMap<T> &partitionMap)
253 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
254 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
256 if (it->second->getNodeSet().size() < minLoad)
258 minLoad = it->second->getNodeSet().size();
264 template <
typename T>
265 unsigned int getNumberOfEdges(
const PartitionMap<T> &partitionMap)
267 unsigned int numberOfEdges = 0;
268 std::list<const Edge<T> *> edgeSet;
270 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
272 const std::list<const Edge<T> *> partitionEdgeSet = it->second->getEdgeSet();
273 for (
auto it2 = partitionEdgeSet.begin(); it2 != partitionEdgeSet.end(); ++it2)
275 if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](
const Edge<T> *edge)
276 { return (*(*it2) == *edge); }) == edgeSet.end())
278 edgeSet.push_back(*it2);
283 return edgeSet.size();
286 template <
typename T>
287 unsigned int getNumberOfNodes(
const PartitionMap<T> &partitionMap)
289 unsigned int numberOfNodes = 0;
290 std::list<const Node<T> *> nodeSet;
292 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
294 const std::list<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
295 for (
auto it2 = partitionNodeSet.begin(); it2 != partitionNodeSet.end(); ++it2)
297 if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](
const Node<T> *node)
298 { return (*(*it2) == *node); }) == nodeSet.end())
300 nodeSet.push_back(*it2);
305 return nodeSet.size();
308 template <
typename T>
309 unsigned int getNumberOfReplicatedEdges(
const PartitionMap<T> &partitionMap)
312 unsigned int numberOfEdges = 0;
313 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
315 numberOfEdges += it->second->getEdgeSet().size();
317 return numberOfEdges;
320 template <
typename T>
321 unsigned int getNumberOfReplicatedNodes(
const PartitionMap<T> &partitionMap)
323 unsigned int numberOfNodes = 0;
324 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
326 numberOfNodes += it->second->getNodeSet().size();
328 return numberOfNodes;
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:76
Definition: Partition.hpp:38
void setPartitionId(unsigned int partitionId)
Set the Partition ID.
Definition: Partition.hpp:183
unsigned int getPartitionId() const
Get the Partition ID.
Definition: Partition.hpp:177
Definition: PartitioningStats.hpp:30