CXXGraph  0.1.6
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  class Partition : public Graph<T>
38  {
39  public:
40  Partition();
41  Partition(unsigned int partitionId);
42  Partition(const std::list<const Edge<T> *> &edgeSet);
43  Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet);
44  ~Partition() = default;
50  unsigned int getPartitionId() const;
56  void setPartitionId(unsigned int partitionId);
57 
58  private:
59  unsigned int partitionId;
60  };
61 
69  template <typename T>
70  static PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap);
71 
79  template <typename T>
80  static unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap);
81 
89  template <typename T>
90  static unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap);
91 
99  template <typename T>
100  static unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap);
101 
109  template <typename T>
110  static unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap);
111 
119  template <typename T>
120  static unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap);
121 
129  template <typename T>
130  static unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap);
131 
139  template <typename T>
140  static unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap);
141 
149  template <typename T>
150  static unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap);
151 
152  template <typename T>
154  {
155  partitionId = 0;
156  }
157 
158  template <typename T>
159  Partition<T>::Partition(unsigned int partitionId) : Graph<T>()
160  {
161  this->partitionId = partitionId;
162  }
163 
164  template <typename T>
165  Partition<T>::Partition(const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
166  {
167  partitionId = 0;
168  }
169 
170  template <typename T>
171  Partition<T>::Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
172  {
173  this->partitionId = partitionId;
174  }
175 
176  template <typename T>
177  unsigned int Partition<T>::getPartitionId() const
178  {
179  return partitionId;
180  }
181 
182  template <typename T>
183  void Partition<T>::setPartitionId(unsigned int partitionId)
184  {
185  this->partitionId = partitionId;
186  }
187 
188  template <typename T>
189  PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap)
190  {
191  PartitioningStats result;
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);
205  return result;
206  }
207 
208  template <typename T>
209  unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap)
210  {
211  unsigned int maxLoad = 0;
212  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
213  {
214  if (it->second->getEdgeSet().size() > maxLoad)
215  {
216  maxLoad = it->second->getEdgeSet().size();
217  }
218  }
219  return maxLoad;
220  }
221 
222  template <typename T>
223  unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap)
224  {
225  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
226  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
227  {
228  if (it->second->getEdgeSet().size() < minLoad)
229  {
230  minLoad = it->second->getEdgeSet().size();
231  }
232  }
233  return minLoad;
234  }
235 
236  template <typename T>
237  unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap)
238  {
239  unsigned int maxLoad = 0;
240  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
241  {
242  if (it->second->getNodeSet().size() > maxLoad)
243  {
244  maxLoad = it->second->getNodeSet().size();
245  }
246  }
247  return maxLoad;
248  }
249 
250  template <typename T>
251  unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap)
252  {
253  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
254  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
255  {
256  if (it->second->getNodeSet().size() < minLoad)
257  {
258  minLoad = it->second->getNodeSet().size();
259  }
260  }
261  return minLoad;
262  }
263 
264  template <typename T>
265  unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap)
266  {
267  unsigned int numberOfEdges = 0;
268  std::list<const Edge<T> *> edgeSet;
269 
270  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
271  {
272  const std::list<const Edge<T> *> partitionEdgeSet = it->second->getEdgeSet();
273  for (auto it2 = partitionEdgeSet.begin(); it2 != partitionEdgeSet.end(); ++it2)
274  {
275  if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](const Edge<T> *edge)
276  { return (*(*it2) == *edge); }) == edgeSet.end())
277  {
278  edgeSet.push_back(*it2);
279  }
280  }
281  }
282 
283  return edgeSet.size();
284  }
285 
286  template <typename T>
287  unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap)
288  {
289  unsigned int numberOfNodes = 0;
290  std::list<const Node<T> *> nodeSet;
291 
292  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
293  {
294  const std::list<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
295  for (auto it2 = partitionNodeSet.begin(); it2 != partitionNodeSet.end(); ++it2)
296  {
297  if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](const Node<T> *node)
298  { return (*(*it2) == *node); }) == nodeSet.end())
299  {
300  nodeSet.push_back(*it2);
301  }
302  }
303  }
304 
305  return nodeSet.size();
306  }
307 
308  template <typename T>
309  unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap)
310  {
311 
312  unsigned int numberOfEdges = 0;
313  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
314  {
315  numberOfEdges += it->second->getEdgeSet().size();
316  }
317  return numberOfEdges;
318  }
319 
320  template <typename T>
321  unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap)
322  {
323  unsigned int numberOfNodes = 0;
324  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
325  {
326  numberOfNodes += it->second->getNodeSet().size();
327  }
328  return numberOfNodes;
329  }
330  }
331 
332 }
333 
334 #endif // __PARTITION_H__
Definition: Edge.hpp:40
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