CXXGraph  0.2.0
CXXGraph is a header only, that manages the Graphs and it's algorithm in C++
Partition.hpp
1 /***********************************************************/
2 /*** ______ ____ ______ _ ***/
3 /*** / ___\ \/ /\ \/ / ___|_ __ __ _ _ __ | |__ ***/
4 /*** | | \ / \ / | _| '__/ _` | '_ \| '_ \ ***/
5 /*** | |___ / \ / \ |_| | | | (_| | |_) | | | | ***/
6 /*** \____/_/\_\/_/\_\____|_| \__,_| .__/|_| |_| ***/
7 /*** |_| ***/
8 /***********************************************************/
9 /*** Header-Only C++ Library for Graph ***/
10 /*** Representation and Algorithms ***/
11 /***********************************************************/
12 /*** Author: ZigRazor ***/
13 /*** E-Mail: zigrazor@gmail.com ***/
14 /***********************************************************/
15 /*** Collaboration: ----------- ***/
16 /***********************************************************/
17 /*** License: AGPL v3.0 ***/
18 /***********************************************************/
19 
20 #ifndef __PARTITION_H__
21 #define __PARTITION_H__
22 
23 #pragma once
24 
25 #include <list>
26 
27 #include "Utility/Typedef.hpp"
28 #include "PartitioningStats.hpp"
29 
30 namespace CXXGRAPH
31 {
32  template <typename T>
33  class Graph;
34  namespace PARTITIONING
35  {
36  template <typename T>
37  std::ostream &operator<<(std::ostream &o, const Partition<T> &partition);
38 
39  template <typename T>
40  class Partition : public Graph<T>
41  {
42  public:
43  Partition();
44  Partition(unsigned int partitionId);
45  Partition(const std::list<const Edge<T> *> &edgeSet);
46  Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet);
47  ~Partition() = default;
53  unsigned int getPartitionId() const;
59  void setPartitionId(unsigned int partitionId);
60 
61  private:
62  unsigned int partitionId;
63  };
64 
72  template <typename T>
73  static PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap);
74 
82  template <typename T>
83  static unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap);
84 
92  template <typename T>
93  static unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap);
94 
102  template <typename T>
103  static unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap);
104 
112  template <typename T>
113  static unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap);
114 
122  template <typename T>
123  static unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap);
124 
132  template <typename T>
133  static unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap);
134 
142  template <typename T>
143  static unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap);
144 
152  template <typename T>
153  static unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap);
154 
155  template <typename T>
157  {
158  partitionId = 0;
159  }
160 
161  template <typename T>
162  Partition<T>::Partition(unsigned int partitionId) : Graph<T>()
163  {
164  this->partitionId = partitionId;
165  }
166 
167  template <typename T>
168  Partition<T>::Partition(const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
169  {
170  partitionId = 0;
171  }
172 
173  template <typename T>
174  Partition<T>::Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
175  {
176  this->partitionId = partitionId;
177  }
178 
179  template <typename T>
180  unsigned int Partition<T>::getPartitionId() const
181  {
182  return partitionId;
183  }
184 
185  template <typename T>
186  void Partition<T>::setPartitionId(unsigned int partitionId)
187  {
188  this->partitionId = partitionId;
189  }
190 
191  template <typename T>
192  PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap)
193  {
194  PartitioningStats result;
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);
208  return result;
209  }
210 
211  template <typename T>
212  unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap)
213  {
214  unsigned int maxLoad = 0;
215  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
216  {
217  if (it->second->getEdgeSet().size() > maxLoad)
218  {
219  maxLoad = it->second->getEdgeSet().size();
220  }
221  }
222  return maxLoad;
223  }
224 
225  template <typename T>
226  unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap)
227  {
228  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
229  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
230  {
231  if (it->second->getEdgeSet().size() < minLoad)
232  {
233  minLoad = it->second->getEdgeSet().size();
234  }
235  }
236  return minLoad;
237  }
238 
239  template <typename T>
240  unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap)
241  {
242  unsigned int maxLoad = 0;
243  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
244  {
245  if (it->second->getNodeSet().size() > maxLoad)
246  {
247  maxLoad = it->second->getNodeSet().size();
248  }
249  }
250  return maxLoad;
251  }
252 
253  template <typename T>
254  unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap)
255  {
256  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
257  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
258  {
259  if (it->second->getNodeSet().size() < minLoad)
260  {
261  minLoad = it->second->getNodeSet().size();
262  }
263  }
264  return minLoad;
265  }
266 
267  template <typename T>
268  unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap)
269  {
270  unsigned int numberOfEdges = 0;
271  std::list<const Edge<T> *> edgeSet;
272 
273  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
274  {
275  const std::list<const Edge<T> *> partitionEdgeSet = it->second->getEdgeSet();
276  for (auto it2 = partitionEdgeSet.begin(); it2 != partitionEdgeSet.end(); ++it2)
277  {
278  if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](const Edge<T> *edge)
279  { return (*(*it2) == *edge); }) == edgeSet.end())
280  {
281  edgeSet.push_back(*it2);
282  }
283  }
284  }
285 
286  return edgeSet.size();
287  }
288 
289  template <typename T>
290  unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap)
291  {
292  unsigned int numberOfNodes = 0;
293  std::list<const Node<T> *> nodeSet;
294 
295  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
296  {
297  const std::list<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
298  for (auto it2 = partitionNodeSet.begin(); it2 != partitionNodeSet.end(); ++it2)
299  {
300  if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](const Node<T> *node)
301  { return (*(*it2) == *node); }) == nodeSet.end())
302  {
303  nodeSet.push_back(*it2);
304  }
305  }
306  }
307 
308  return nodeSet.size();
309  }
310 
311  template <typename T>
312  unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap)
313  {
314 
315  unsigned int numberOfEdges = 0;
316  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
317  {
318  numberOfEdges += it->second->getEdgeSet().size();
319  }
320  return numberOfEdges;
321  }
322 
323  template <typename T>
324  unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap)
325  {
326  unsigned int numberOfNodes = 0;
327  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
328  {
329  numberOfNodes += it->second->getNodeSet().size();
330  }
331  return numberOfNodes;
332  }
333 
334  template <typename T>
335  std::ostream &operator<<(std::ostream &os, const Partition<T> &partition)
336  {
337  os << "Partition " << partition.getPartitionId() << ":\n";
338  auto edgeList = partition.getEdgeSet();
339  auto it = edgeList.begin();
340  for (it; it != edgeList.end(); ++it)
341  {
342  if (((*it)->isDirected().has_value()&& (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
343  {
344  os << dynamic_cast<const DirectedWeightedEdge<T> &>(**it) << "\n";
345  }
346  else if (((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
347  {
348  os << dynamic_cast<const DirectedEdge<T> &>(**it) << "\n";
349  }
350  else if (!((*it)->isDirected().has_value() && (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
351  {
352  os << dynamic_cast<const UndirectedWeightedEdge<T> &>(**it) << "\n";
353  }
354  else if (!((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
355  {
356  os << dynamic_cast<const UndirectedEdge<T> &>(**it) << "\n";
357  }
358  else
359  {
360  os << **it << "\n";
361  }
362  }
363  return os;
364  }
365  }
366 
367 }
368 
369 #endif // __PARTITION_H__
Definition: Edge.hpp:39
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