20 #ifndef __PARTITION_H__
21 #define __PARTITION_H__
27 #include "Utility/Typedef.hpp"
28 #include "PartitioningStats.hpp"
34 namespace PARTITIONING
37 std::ostream &operator<<(std::ostream &o,
const Partition<T> &partition);
46 Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet);
62 unsigned int partitionId;
83 static unsigned int getMaxEdgesLoad(
const PartitionMap<T> &partitionMap);
93 static unsigned int getMinEdgesLoad(
const PartitionMap<T> &partitionMap);
102 template <
typename T>
103 static unsigned int getMaxNodesLoad(
const PartitionMap<T> &partitionMap);
112 template <
typename T>
113 static unsigned int getMinNodesLoad(
const PartitionMap<T> &partitionMap);
122 template <
typename T>
123 static unsigned int getNumberOfEdges(
const PartitionMap<T> &partitionMap);
132 template <
typename T>
133 static unsigned int getNumberOfNodes(
const PartitionMap<T> &partitionMap);
142 template <
typename T>
143 static unsigned int getNumberOfReplicatedEdges(
const PartitionMap<T> &partitionMap);
152 template <
typename T>
153 static unsigned int getNumberOfReplicatedNodes(
const PartitionMap<T> &partitionMap);
155 template <
typename T>
161 template <
typename T>
162 Partition<T>::Partition(
unsigned int partitionId) :
Graph<T>()
164 this->partitionId = partitionId;
167 template <
typename T>
168 Partition<T>::Partition(
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
173 template <
typename T>
174 Partition<T>::Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
176 this->partitionId = partitionId;
179 template <
typename T>
185 template <
typename T>
188 this->partitionId = partitionId;
191 template <
typename T>
195 result.numberOfPartitions = partitionMap.size();
196 result.numberOfNodes = getNumberOfNodes(partitionMap);
197 result.numberOfEdges = getNumberOfEdges(partitionMap);
198 result.replicatedNodesCount = getNumberOfReplicatedNodes(partitionMap);
199 result.replicatedEdgesCount = getNumberOfReplicatedEdges(partitionMap);
200 result.maxEdgesLoad = getMaxEdgesLoad(partitionMap);
201 result.minEdgesLoad = getMinEdgesLoad(partitionMap);
202 result.maxNodesLoad = getMaxNodesLoad(partitionMap);
203 result.minNodesLoad = getMinNodesLoad(partitionMap);
204 result.edgesReplicationFactor = (double)result.replicatedEdgesCount / result.numberOfEdges;
205 result.nodesReplicationFactor = (
double)result.replicatedNodesCount / result.numberOfNodes;
206 result.balanceEdgesFactor = (double)(result.maxEdgesLoad - result.minEdgesLoad) / (result.maxEdgesLoad);
207 result.balanceNodesFactor = (double)(result.maxNodesLoad - result.minNodesLoad) / (result.maxNodesLoad);
211 template <
typename T>
212 unsigned int getMaxEdgesLoad(
const PartitionMap<T> &partitionMap)
214 unsigned int maxLoad = 0;
215 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
217 if (it->second->getEdgeSet().size() > maxLoad)
219 maxLoad = it->second->getEdgeSet().size();
225 template <
typename T>
226 unsigned int getMinEdgesLoad(
const PartitionMap<T> &partitionMap)
228 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
229 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
231 if (it->second->getEdgeSet().size() < minLoad)
233 minLoad = it->second->getEdgeSet().size();
239 template <
typename T>
240 unsigned int getMaxNodesLoad(
const PartitionMap<T> &partitionMap)
242 unsigned int maxLoad = 0;
243 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
245 if (it->second->getNodeSet().size() > maxLoad)
247 maxLoad = it->second->getNodeSet().size();
253 template <
typename T>
254 unsigned int getMinNodesLoad(
const PartitionMap<T> &partitionMap)
256 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
257 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
259 if (it->second->getNodeSet().size() < minLoad)
261 minLoad = it->second->getNodeSet().size();
267 template <
typename T>
268 unsigned int getNumberOfEdges(
const PartitionMap<T> &partitionMap)
270 unsigned int numberOfEdges = 0;
271 std::list<const Edge<T> *> edgeSet;
273 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
275 const std::list<const Edge<T> *> partitionEdgeSet = it->second->getEdgeSet();
276 for (
auto it2 = partitionEdgeSet.begin(); it2 != partitionEdgeSet.end(); ++it2)
278 if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](
const Edge<T> *edge)
279 { return (*(*it2) == *edge); }) == edgeSet.end())
281 edgeSet.push_back(*it2);
286 return edgeSet.size();
289 template <
typename T>
290 unsigned int getNumberOfNodes(
const PartitionMap<T> &partitionMap)
292 unsigned int numberOfNodes = 0;
293 std::list<const Node<T> *> nodeSet;
295 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
297 const std::list<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
298 for (
auto it2 = partitionNodeSet.begin(); it2 != partitionNodeSet.end(); ++it2)
300 if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](
const Node<T> *node)
301 { return (*(*it2) == *node); }) == nodeSet.end())
303 nodeSet.push_back(*it2);
308 return nodeSet.size();
311 template <
typename T>
312 unsigned int getNumberOfReplicatedEdges(
const PartitionMap<T> &partitionMap)
315 unsigned int numberOfEdges = 0;
316 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
318 numberOfEdges += it->second->getEdgeSet().size();
320 return numberOfEdges;
323 template <
typename T>
324 unsigned int getNumberOfReplicatedNodes(
const PartitionMap<T> &partitionMap)
326 unsigned int numberOfNodes = 0;
327 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
329 numberOfNodes += it->second->getNodeSet().size();
331 return numberOfNodes;
334 template <
typename T>
335 std::ostream &operator<<(std::ostream &os,
const Partition<T> &partition)
337 os <<
"Partition " << partition.getPartitionId() <<
":\n";
338 auto edgeList = partition.getEdgeSet();
339 auto it = edgeList.begin();
340 for (it; it != edgeList.end(); ++it)
342 if (((*it)->isDirected().has_value()&& (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
344 os << dynamic_cast<const DirectedWeightedEdge<T> &>(**it) <<
"\n";
346 else if (((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
348 os << dynamic_cast<const DirectedEdge<T> &>(**it) <<
"\n";
350 else if (!((*it)->isDirected().has_value() && (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
352 os << dynamic_cast<const UndirectedWeightedEdge<T> &>(**it) <<
"\n";
354 else if (!((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
356 os << dynamic_cast<const UndirectedEdge<T> &>(**it) <<
"\n";
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:78
Definition: Partition.hpp:41
void setPartitionId(unsigned int partitionId)
Set the Partition ID.
Definition: Partition.hpp:186
unsigned int getPartitionId() const
Get the Partition ID.
Definition: Partition.hpp:180
Definition: PartitioningStats.hpp:30