| CXXGraph 0.4.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: MPL v2.0 ***/
18 /***********************************************************/
19
20 #ifndef __CXXGRAPH_PARTITION_H__
21 #define __CXXGRAPH_PARTITION_H__
22
23 #pragma once
24
25 #include <list>
26 #include <unordered_set>
27
28 #include "Utility/Typedef.hpp"
29 #include "PartitioningStats.hpp"
30
31 namespace CXXGRAPH
32 {
33 template <typename T>
34 class Graph;
35
36 template<typename T>
37 using T_EdgeSet = std::unordered_set<const Edge<T> *>;
38 namespace PARTITIONING
39 {
40 template <typename T>
41 std::ostream &operator<<(std::ostream &o, const Partition<T> &partition);
42
43 template <typename T>
44 class Partition : public Graph<T>
45 {
46 public:
47 Partition();
48 Partition(unsigned int partitionId);
49 Partition(const T_EdgeSet<T> &edgeSet);
50 Partition(unsigned int partitionId, const T_EdgeSet<T> &edgeSet);
51 ~Partition() = default;
57 unsigned int getPartitionId() const;
63 void setPartitionId(unsigned int partitionId);
64
65 private:
66 unsigned int partitionId = 0;
67 };
68
76 template <typename T>
77 static PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap);
78
86 template <typename T>
87 static unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap);
88
96 template <typename T>
97 static unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap);
98
106 template <typename T>
107 static unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap);
108
116 template <typename T>
117 static unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap);
118
126 template <typename T>
127 static unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap);
128
136 template <typename T>
137 static unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap);
138
146 template <typename T>
147 static unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap);
148
156 template <typename T>
157 static unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap);
158
159 template <typename T>
160 Partition<T>::Partition() : Graph<T>()
161 {
162 partitionId = 0;
163 }
164
165 template <typename T>
166 Partition<T>::Partition(unsigned int partitionId) : Graph<T>()
167 {
168 this->partitionId = partitionId;
169 }
170
171 template <typename T>
172 Partition<T>::Partition(const T_EdgeSet<T> &edgeSet) : Graph<T>(edgeSet)
173 {
174 partitionId = 0;
175 }
176
177 template <typename T>
178 Partition<T>::Partition(unsigned int partitionId, const T_EdgeSet<T> &edgeSet) : Graph<T>(edgeSet)
179 {
180 this->partitionId = partitionId;
181 }
182
183 template <typename T>
184 unsigned int Partition<T>::getPartitionId() const
185 {
186 return partitionId;
187 }
188
189 template <typename T>
190 void Partition<T>::setPartitionId(unsigned int partitionId)
191 {
192 this->partitionId = partitionId;
193 }
194
195 template <typename T>
196 PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap)
197 {
198 PartitioningStats result;
199 result.numberOfPartitions = partitionMap.size();
200 result.numberOfNodes = getNumberOfNodes(partitionMap);
201 result.numberOfEdges = getNumberOfEdges(partitionMap);
202 result.replicatedNodesCount = getNumberOfReplicatedNodes(partitionMap);
203 result.replicatedEdgesCount = getNumberOfReplicatedEdges(partitionMap);
204 result.maxEdgesLoad = getMaxEdgesLoad(partitionMap);
205 result.minEdgesLoad = getMinEdgesLoad(partitionMap);
206 result.maxNodesLoad = getMaxNodesLoad(partitionMap);
207 result.minNodesLoad = getMinNodesLoad(partitionMap);
208 result.edgesReplicationFactor = static_cast<double>(result.replicatedEdgesCount / result.numberOfEdges);
209 result.nodesReplicationFactor = static_cast<double>(result.replicatedNodesCount / result.numberOfNodes);
210 result.balanceEdgesFactor = static_cast<double>((result.maxEdgesLoad - result.minEdgesLoad) / (result.maxEdgesLoad));
211 result.balanceNodesFactor = static_cast<double>((result.maxNodesLoad - result.minNodesLoad) / (result.maxNodesLoad));
212 return result;
213 }
214
215 template <typename T>
216 unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap)
217 {
218 unsigned int maxLoad = 0;
219 for (const auto& it : partitionMap)
220 {
221 if (it.second->getEdgeSet().size() > maxLoad)
222 {
223 maxLoad = it.second->getEdgeSet().size();
224 }
225 }
226 return maxLoad;
227 }
228
229 template <typename T>
230 unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap)
231 {
232 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
233 for (const auto& it : partitionMap)
234 {
235 if (it.second->getEdgeSet().size() < minLoad)
236 {
237 minLoad = it.second->getEdgeSet().size();
238 }
239 }
240 return minLoad;
241 }
242
243 template <typename T>
244 unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap)
245 {
246 unsigned int maxLoad = 0;
247 for (const auto& it : partitionMap)
248 {
249 if (it.second->getNodeSet().size() > maxLoad)
250 {
251 maxLoad = it.second->getNodeSet().size();
252 }
253 }
254 return maxLoad;
255 }
256
257 template <typename T>
258 unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap)
259 {
260 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
261 for (const auto& it : partitionMap)
262 {
263 if (it.second->getNodeSet().size() < minLoad)
264 {
265 minLoad = it.second->getNodeSet().size();
266 }
267 }
268 return minLoad;
269 }
270
271 template <typename T>
272 unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap)
273 {
274 unsigned int numberOfEdges = 0;
275 T_EdgeSet<T> edgeSet;
276
277 for (const auto& it : partitionMap)
278 {
279 const T_EdgeSet<T> partitionEdgeSet = it.second->getEdgeSet();
280 for (const auto& it2 : partitionEdgeSet)
281 {
282 if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](const Edge<T> *edge)
283 { return (*it2 == *edge); }) == edgeSet.end())
284 {
285 edgeSet.insert(it2);
286 }
287 }
288 }
289
290 return edgeSet.size();
291 }
292
293 template <typename T>
294 unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap)
295 {
296 unsigned int numberOfNodes = 0;
297 std::deque<const Node<T> *> nodeSet;
298
299 for (const auto& it : partitionMap)
300 {
301 const std::deque<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
302 for (const auto& it2 : partitionNodeSet)
303 {
304 if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](const Node<T> *node)
305 { return (*it2 == *node); }) == nodeSet.end())
306 {
307 nodeSet.push_back(*it2);
308 }
309 }
310 }
311
312 return nodeSet.size();
313 }
314
315 template <typename T>
316 unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap)
317 {
318
319 unsigned int numberOfEdges = 0;
320 for (const auto& it : partitionMap)
321 {
322 numberOfEdges += it.second->getEdgeSet().size();
323 }
324 return numberOfEdges;
325 }
326
327 template <typename T>
328 unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap)
329 {
330 unsigned int numberOfNodes = 0;
331 for (const auto& it : partitionMap)
332 {
333 numberOfNodes += it.second->getNodeSet().size();
334 }
335 return numberOfNodes;
336 }
337
338 template <typename T>
339 std::ostream &operator<<(std::ostream &os, const Partition<T> &partition)
340 {
341 os << "Partition " << partition.getPartitionId() << ":\n";
342 auto edgeList = partition.getEdgeSet();
343 for (const auto& it : edgeList)
344 {
345 if(!(*it)->isDirected().has_value() && !(*it)->isWeighted().has_value()){
346 // Edge Case
347 os << **it << "\n";
348 }
349 else if (((*it)->isDirected().has_value()&& (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
350 {
351 os << dynamic_cast<const DirectedWeightedEdge<T> &>(*it) << "\n";
352 }
353 else if ((it->isDirected().has_value() && it->isDirected().value()) && !(it->isWeighted().has_value() && it->isWeighted().value()))
354 {
355 os << dynamic_cast<const DirectedEdge<T> &>(*it) << "\n";
356 }
357 else if (!(it->isDirected().has_value() && it->isDirected().value()) && (it->isWeighted().has_value() && it->isWeighted().value()))
358 {
359 os << dynamic_cast<const UndirectedWeightedEdge<T> &>(*it) << "\n";
360 }
361 else if (!(it->isDirected().has_value() && it->isDirected().value()) && !(it->isWeighted().has_value() && it->isWeighted().value()))
362 {
363 os << dynamic_cast<const UndirectedEdge<T> &>(*it) << "\n";
364 }
365 else
366 {
367 //Should never happens
368 os << "Wrong Edge Class" << "\n";
369 }
370 }
371 return os;
372 }
373 }
374
375 }
376
377 #endif // __CXXGRAPH_PARTITION_H__
CXXGRAPH::Graph
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:91
CXXGRAPH::PARTITIONING::Partition
Definition: Partition.hpp:45
CXXGRAPH::PARTITIONING::Partition::setPartitionId
void setPartitionId(unsigned int partitionId)
Set the Partition ID.
Definition: Partition.hpp:190
CXXGRAPH::PARTITIONING::Partition::getPartitionId
unsigned int getPartitionId() const
Get the Partition ID.
Definition: Partition.hpp:184
CXXGRAPH::PARTITIONING::PartitioningStats
Definition: PartitioningStats.hpp:30