CXXGraph  0.1.5
CXXGraph is a small library, header only, that manages the Graph and it's algorithm in C++
Graph.hpp
1 #ifndef __CXXGRAPH_H__
2 #define __CXXGRAPH_H__
3 
4 #pragma once
5 
6 #include <utility>
7 #include <set>
8 #include <map>
9 #include <optional>
10 #include <iostream>
11 #include <limits>
12 #include <list>
13 #include <queue>
14 #include <string>
15 #include <functional>
16 #include <fstream>
17 #include <limits.h>
18 #include <mutex>
19 
20 namespace CXXGRAPH
21 {
22  //STRING ERROR CONST EXPRESSION
23  constexpr char ERR_NO_DIR_OR_UNDIR_EDGE[] = "Edge are neither Directed neither Undirected";
24  constexpr char ERR_NO_WEIGHTED_EDGE[] = "Edge are not Weighted";
25  constexpr char ERR_TARGET_NODE_NOT_REACHABLE[] = "Target Node not Reachable";
26  constexpr char ERR_TARGET_NODE_NOT_IN_GRAPH[] = "Target Node not inside Graph";
27  constexpr char ERR_SOURCE_NODE_NOT_IN_GRAPH[] = "Source Node not inside Graph";
29  constexpr double INF_DOUBLE = std::numeric_limits<double>::max();
30  template <typename T>
31  class Node;
32  template <typename T>
33  class Edge;
34  template <typename T>
35  class DirectedEdge;
36  template <typename T>
37  class UndirectedEdge;
38  template <typename T>
39  class DirectedWeightedEdge;
40  template <typename T>
41  class UndirectedWeightedEdge;
42  template <typename T>
43  class Graph;
44  template <typename T>
45  class Partition;
46 
47  class Weighted;
48 
49  class ThreadSafe;
50 
51  template <typename T>
52  class Writer;
53  template <typename T>
54  class Reader;
55 
58  {
59  bool success; // TRUE if the function does not return error, FALSE otherwise
60  std::string errorMessage; //message of error
61  double result; //result (valid only if success is TRUE)
62  };
64 
67  {
68  bool success; // TRUE if the function does not return error, FALSE otherwise
69  std::string errorMessage; //message of error
70  std::map<unsigned long, long> minDistanceMap; //result a map that contains the node id and the minumum distance from source (valid only if success is TRUE)
71  };
73 
76  {
77  unsigned int numberOfPartitions; // The number of Partitions
78  unsigned int numberOfNodes; // The number of Nodes
79  unsigned int replicatedNodesCount; // The number of Nodes that are replicated
80  unsigned int numberOfEdges; // The number of edges
81  unsigned int replicatedEdgesCount; // The number of edges that are replicated
82  unsigned int maxEdgesLoad; // Maximum edges load of the partitions
83  unsigned int minEdgesLoad; // Minimun edges load of the partitions
84  unsigned int maxNodesLoad; // Maximum nodes load of the partitions
85  unsigned int minNodesLoad; // Minimun nodes load of the partitions
86  double balanceEdgesFactor; // The balance edges factor of the partitions (maxEdgesLoad - minEdgesLoad) / (maxEdgesLoad), 0 is the optimal partitioning
87  double balanceNodesFactor; // The balance edges factor of the partitions (maxNodesLoad - minNodesLoad) / (maxNodesLoad), 0 is the optimal partitioning
88  double nodesReplicationFactor; // The replication factor of the Nodes (replicatedNodesCount / numberOfNodes), 1 is the optimal partitioning
89  double edgesReplicationFactor; // The replication factor of the edges (replicatedEdgesCount / numberOfEdges), 1 is the optimal partitioning
90 
91  friend std::ostream &operator<<(std::ostream &os, const PartitioningStats_struct &partitionStats)
92  {
93  os << "Partitioning Stats:\n";
94  os << "\tNumber of Partitions: " << partitionStats.numberOfPartitions << "\n";
95  os << "\tNumber of Nodes: " << partitionStats.numberOfNodes << "\n";
96  os << "\tNumber of Edges: " << partitionStats.numberOfEdges << "\n";
97  os << "\tNumber of Nodes Replica: " << partitionStats.replicatedNodesCount << "\n";
98  os << "\tNumber of Edges Replica: " << partitionStats.replicatedEdgesCount << "\n";
99  os << "\tNodes Replication Factor: " << partitionStats.nodesReplicationFactor << "\n";
100  os << "\tEdges Replication Factor: " << partitionStats.edgesReplicationFactor << "\n";
101  os << "\tMax Edges Load: " << partitionStats.maxEdgesLoad << "\n";
102  os << "\tMin Edges Load: " << partitionStats.minEdgesLoad << "\n";
103  os << "\tBalance Edges Factor: " << partitionStats.balanceEdgesFactor << "\n";
104  os << "\tMax Nodes Load: " << partitionStats.maxNodesLoad << "\n";
105  os << "\tMin Nodes Load: " << partitionStats.minNodesLoad << "\n";
106  os << "\tBalance Nodes Factor: " << partitionStats.balanceNodesFactor << "\n";
107  return os;
108  }
109  };
111 
112  template <typename T>
113  using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *, const Edge<T> *>>>;
114 
115  template <typename T>
116  std::ostream &operator<<(std::ostream &o, const Node<T> &node);
117  template <typename T>
118  std::ostream &operator<<(std::ostream &o, const Edge<T> &edge);
119  template <typename T>
120  std::ostream &operator<<(std::ostream &o, const DirectedEdge<T> &edge);
121  template <typename T>
122  std::ostream &operator<<(std::ostream &o, const UndirectedEdge<T> &edge);
123  template <typename T>
124  std::ostream &operator<<(std::ostream &o, const DirectedWeightedEdge<T> &edge);
125  template <typename T>
126  std::ostream &operator<<(std::ostream &o, const UndirectedWeightedEdge<T> &edge);
127  template <typename T>
128  std::ostream &operator<<(std::ostream &o, const Graph<T> &graph);
129  template <typename T>
130  std::ostream &operator<<(std::ostream &o, const AdjacencyMatrix<T> &adj);
131  template <typename T>
132  using PartitionMap = std::map<unsigned int, Partition<T> *>;
133 
134  template <typename T>
135  class Node
136  {
137  private:
138  unsigned long id;
139  T data;
140 
141  public:
142  Node(const unsigned long id, const T &data);
143  ~Node() = default;
144  const unsigned long &getId() const;
145  const T &getData() const;
146  //operator
147  bool operator==(const Node<T> &b) const;
148  bool operator<(const Node<T> &b) const;
149  friend std::ostream &operator<<<>(std::ostream &os, const Node<T> &node);
150  };
151 
152  template <typename T>
153  Node<T>::Node(const unsigned long id, const T &data)
154  {
155  this->id = id;
156  this->data = data;
157  }
158 
159  template <typename T>
160  const unsigned long &Node<T>::getId() const
161  {
162  return id;
163  }
164 
165  template <typename T>
166  const T &Node<T>::getData() const
167  {
168  return data;
169  }
170 
171  template <typename T>
172  bool Node<T>::operator==(const Node<T> &b) const
173  {
174  return (this->id == b.id && this->data == b.data);
175  }
176 
177  template <typename T>
178  bool Node<T>::operator<(const Node<T> &b) const
179  {
180  return (this->id < b.id);
181  }
182 
183  class Weighted
184  {
185  private:
186  double weight;
187 
188  public:
189  Weighted();
190  Weighted(const double weight);
191  virtual ~Weighted() = default;
192  double getWeight() const;
193  void setWeight(const double weight);
194  };
195 
196  //inline because the implementation of non-template function in header file
197  inline Weighted::Weighted()
198  {
199  weight = 0.0;
200  }
201 
202  //inline because the implementation of non-template function in header file
203  inline Weighted::Weighted(const double weight)
204  {
205  this->weight = weight;
206  }
207 
208  //inline because the implementation of non-template function in header file
209  inline double Weighted::getWeight() const
210  {
211  return weight;
212  }
213 
214  //inline because the implementation of non-template function in header file
215  inline void Weighted::setWeight(const double weight)
216  {
217  this->weight = weight;
218  }
219 
221  {
222  public:
223  void getLock() const;
224  void releaseLock() const;
225 
226  protected:
227  mutable std::mutex mutex;
228  };
229  //inline because the implementation of non-template function in header file
230  inline void ThreadSafe::getLock() const
231  {
232  mutex.lock();
233  }
234  //inline because the implementation of non-template function in header file
235  inline void ThreadSafe::releaseLock() const
236  {
237  mutex.unlock();
238  }
239 
240  template <typename T>
241  class Edge
242  {
243  private:
244  unsigned long id;
245  std::pair<const Node<T> *, const Node<T> *> nodePair;
246 
247  public:
248  Edge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
249  Edge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
250  virtual ~Edge() = default;
251  const unsigned long &getId() const;
252  const std::pair<const Node<T> *, const Node<T> *> &getNodePair() const;
253  virtual const std::optional<bool> isDirected() const;
254  virtual const std::optional<bool> isWeighted() const;
255  //operator
256  virtual bool operator==(const Edge<T> &b) const;
257  bool operator<(const Edge<T> &b) const;
258  //operator DirectedEdge<T>() const { return DirectedEdge<T>(id, nodePair); }
259  //operator UndirectedEdge<T>() const { return UndirectedEdge<T>(id, nodePair); }
260 
261  friend std::ostream &operator<<<>(std::ostream &os, const Edge<T> &edge);
262  };
263 
264  template <typename T>
265  Edge<T>::Edge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : nodePair(&node1, &node2)
266  {
267  this->id = id;
268  }
269 
270  template <typename T>
271  Edge<T>::Edge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : nodePair(nodepair)
272  {
273  this->id = id;
274  }
275 
276  template <typename T>
277  const unsigned long &Edge<T>::getId() const
278  {
279  return id;
280  }
281 
282  template <typename T>
283  const std::pair<const Node<T> *, const Node<T> *> &Edge<T>::getNodePair() const
284  {
285  return nodePair;
286  }
287 
288  template <typename T>
289  const std::optional<bool> Edge<T>::isDirected() const
290  {
291  return std::nullopt;
292  }
293 
294  template <typename T>
295  const std::optional<bool> Edge<T>::isWeighted() const
296  {
297  return std::nullopt;
298  }
299 
300  template <typename T>
301  bool Edge<T>::operator==(const Edge<T> &b) const
302  {
303  return (this->id == b.id && this->nodePair == b.nodePair);
304  }
305 
306  template <typename T>
307  bool Edge<T>::operator<(const Edge<T> &b) const
308  {
309  return (this->id < b.id);
310  }
311 
312  template <typename T>
313  class DirectedEdge : public Edge<T>
314  {
315  public:
316  DirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
317  DirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
318  DirectedEdge(const Edge<T> &edge);
319  virtual ~DirectedEdge() = default;
320  const Node<T> &getFrom() const;
321  const Node<T> &getTo() const;
322  const std::optional<bool> isDirected() const override;
323  const std::optional<bool> isWeighted() const override;
324  //operator
325  explicit operator UndirectedEdge<T>() const { return UndirectedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair()); }
326 
327  friend std::ostream &operator<<<>(std::ostream &os, const DirectedEdge<T> &edge);
328  };
329 
330  template <typename T>
331  DirectedEdge<T>::DirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : Edge<T>(id, node1, node2)
332  {
333  }
334 
335  template <typename T>
336  DirectedEdge<T>::DirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
337  {
338  }
339 
340  template <typename T>
341  DirectedEdge<T>::DirectedEdge(const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
342  {
343  }
344 
345  template <typename T>
346  const Node<T> &DirectedEdge<T>::getFrom() const
347  {
348  return *(Edge<T>::getNodePair().first);
349  }
350 
351  template <typename T>
352  const Node<T> &DirectedEdge<T>::getTo() const
353  {
354  return *(Edge<T>::getNodePair().second);
355  }
356 
357  template <typename T>
358  const std::optional<bool> DirectedEdge<T>::isDirected() const
359  {
360  return true;
361  }
362 
363  template <typename T>
364  const std::optional<bool> DirectedEdge<T>::isWeighted() const
365  {
366  return false;
367  }
368 
369  template <typename T>
370  class UndirectedEdge : public Edge<T>
371  {
372  public:
373  UndirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
374  UndirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
375  UndirectedEdge(const Edge<T> &edge);
376  virtual ~UndirectedEdge() = default;
377  const Node<T> &getNode1() const;
378  const Node<T> &getNode2() const;
379  const std::optional<bool> isDirected() const override;
380  const std::optional<bool> isWeighted() const override;
381  //operator
382  explicit operator DirectedEdge<T>() const { return DirectedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair()); }
383 
384  friend std::ostream &operator<<<>(std::ostream &os, const UndirectedEdge<T> &edge);
385  };
386 
387  template <typename T>
388  UndirectedEdge<T>::UndirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : Edge<T>(id, node1, node2)
389  {
390  }
391 
392  template <typename T>
393  UndirectedEdge<T>::UndirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
394  {
395  }
396 
397  template <typename T>
398  UndirectedEdge<T>::UndirectedEdge(const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
399  {
400  }
401 
402  template <typename T>
403  const Node<T> &UndirectedEdge<T>::getNode1() const
404  {
405  return *(Edge<T>::getNodePair().first);
406  }
407 
408  template <typename T>
409  const Node<T> &UndirectedEdge<T>::getNode2() const
410  {
411  return *(Edge<T>::getNodePair().second);
412  }
413 
414  template <typename T>
415  const std::optional<bool> UndirectedEdge<T>::isDirected() const
416  {
417  return false;
418  }
419 
420  template <typename T>
421  const std::optional<bool> UndirectedEdge<T>::isWeighted() const
422  {
423  return false;
424  }
425 
426  template <typename T>
427  class DirectedWeightedEdge : public DirectedEdge<T>, public Weighted
428  {
429  public:
430  DirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight);
431  DirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight);
432  DirectedWeightedEdge(const DirectedEdge<T> &edge, const double weight);
433  DirectedWeightedEdge(const Edge<T> &edge, const double weight);
435  DirectedWeightedEdge(const Edge<T> &edge);
437  virtual ~DirectedWeightedEdge() = default;
438  const std::optional<bool> isWeighted() const override;
439  //operator
440  explicit operator UndirectedWeightedEdge<T>() const { return UndirectedWeightedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair(), Weighted::getWeight()); }
441 
442  friend std::ostream &operator<<<>(std::ostream &os, const DirectedWeightedEdge<T> &edge);
443  };
444 
445  template <typename T>
446  DirectedWeightedEdge<T>::DirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight) : DirectedEdge<T>(id, node1, node2), Weighted(weight)
447  {
448  }
449 
450  template <typename T>
451  DirectedWeightedEdge<T>::DirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight) : DirectedEdge<T>(id, nodepair), Weighted(weight)
452  {
453  }
454 
455  template <typename T>
456  DirectedWeightedEdge<T>::DirectedWeightedEdge(const DirectedEdge<T> &edge, const double weight) : DirectedEdge<T>(edge), Weighted(weight)
457  {
458  }
459 
460  template <typename T>
461  DirectedWeightedEdge<T>::DirectedWeightedEdge(const Edge<T> &edge, const double weight) : DirectedEdge<T>(edge), Weighted(weight)
462  {
463  }
464 
465  template <typename T>
466  DirectedWeightedEdge<T>::DirectedWeightedEdge(const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
467  {
468  }
469 
470  template <typename T>
471  DirectedWeightedEdge<T>::DirectedWeightedEdge(const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
472  {
473  }
474 
475  template <typename T>
476  DirectedWeightedEdge<T>::DirectedWeightedEdge(const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
477  {
478  }
479 
480  template <typename T>
481  const std::optional<bool> DirectedWeightedEdge<T>::isWeighted() const
482  {
483  return true;
484  }
485 
486  template <typename T>
488  {
489  public:
490  UndirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight);
491  UndirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight);
492  UndirectedWeightedEdge(const UndirectedEdge<T> &edge, const double weight);
493  UndirectedWeightedEdge(const Edge<T> &edge, const double weight);
495  UndirectedWeightedEdge(const Edge<T> &edge);
497  virtual ~UndirectedWeightedEdge() = default;
498  const std::optional<bool> isWeighted() const override;
499  //operator
500  explicit operator DirectedWeightedEdge<T>() const { return DirectedWeightedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair(), Weighted::getWeight()); }
501 
502  friend std::ostream &operator<<<>(std::ostream &os, const UndirectedWeightedEdge<T> &edge);
503  };
504 
505  template <typename T>
506  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight) : UndirectedEdge<T>(id, node1, node2), Weighted(weight)
507  {
508  }
509 
510  template <typename T>
511  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight) : UndirectedEdge<T>(id, nodepair), Weighted(weight)
512  {
513  }
514 
515  template <typename T>
516  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const UndirectedEdge<T> &edge, const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
517  {
518  }
519 
520  template <typename T>
521  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const Edge<T> &edge, const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
522  {
523  }
524 
525  template <typename T>
526  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
527  {
528  }
529 
530  template <typename T>
531  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
532  {
533  }
534 
535  template <typename T>
536  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
537  {
538  }
539 
540  template <typename T>
541  const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted() const
542  {
543  return true;
544  }
545 
546  template <typename T>
547  class Partition;
548 
550  template <typename T>
551  class Graph
552  {
553  private:
554  std::list<const Edge<T> *> edgeSet;
555  void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const;
556  int writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
557  int readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
558  int writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
559  int readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
560  void recreateGraphFromReadFiles(std::map<unsigned long, std::pair<unsigned long, unsigned long>> &edgeMap, std::map<unsigned long, bool> &edgeDirectedMap, std::map<unsigned long, T> &nodeFeatMap, std::map<unsigned long, double> &edgeWeightMap);
561  void greedyPartition(PartitionMap<T> &partitionMap) const;
562 
563  public:
566  {
569  OUT_1,
570  OUT_2
571  };
572 
573  typedef E_InputOutputFormat InputOutputFormat;
574 
577  {
579  ALG_1,
580  ALG_2
581  };
582  typedef E_PartitionAlgorithm PartitionAlgorithm;
583 
584  Graph() = default;
585  Graph(const std::list<const Edge<T> *> &edgeSet);
586  ~Graph() = default;
595  virtual const std::list<const Edge<T> *> &getEdgeSet() const;
604  virtual void setEdgeSet(std::list<const Edge<T> *> &edgeSet);
613  virtual void addEdge(const Edge<T> *edge);
622  virtual void removeEdge(unsigned long edgeId);
631  virtual const std::list<const Node<T> *> getNodeSet() const;
641  virtual const std::optional<const Edge<T> *> getEdge(unsigned long edgeId) const;
647  virtual const AdjacencyMatrix<T> getAdjMatrix() const;
660  virtual const DijkstraResult dijkstra(const Node<T> &source, const Node<T> &target) const;
671  virtual const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const;
682  virtual const std::vector<Node<T>> depth_first_search(const Node<T> &start) const;
683 
692  virtual bool isCyclicDirectedGraphDFS() const;
693 
702  virtual bool isCyclicDirectedGraphBFS() const;
703 
711  virtual bool isDirectedGraph() const;
712 
739  virtual const DialResult dial(const Node<T> &source, int maxWeight) const;
740 
741  virtual int writeToFile(InputOutputFormat format = InputOutputFormat::STANDARD_CSV, const std::string &workingDir = ".", const std::string &OFileName = "graph", bool compress = false, bool writeNodeFeat = false, bool writeEdgeWeight = false) const;
742 
756  virtual int readFromFile(InputOutputFormat format = InputOutputFormat::STANDARD_CSV, const std::string &workingDir = ".", const std::string &OFileName = "graph", bool compress = false, bool readNodeFeat = false, bool readEdgeWeight = false);
757 
767  virtual PartitionMap<T> partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const;
768 
769  friend std::ostream &operator<<<>(std::ostream &os, const Graph<T> &graph);
770  friend std::ostream &operator<<<>(std::ostream &os, const AdjacencyMatrix<T> &adj);
771  };
772 
773  template <typename T>
774  Graph<T>::Graph(const std::list<const Edge<T> *> &edgeSet)
775  {
776  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
777  {
778  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
779  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
780  {
781  this->edgeSet.push_back(*edgeSetIt);
782  }
783  }
784  }
785 
786  template <typename T>
787  const std::list<const Edge<T> *> &Graph<T>::getEdgeSet() const
788  {
789  return edgeSet;
790  }
791 
792  template <typename T>
793  void Graph<T>::setEdgeSet(std::list<const Edge<T> *> &edgeSet)
794  {
795  this->edgeSet.clear();
796  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
797  {
798  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
799  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
800  {
801  this->edgeSet.push_back(*edgeSetIt);
802  }
803  }
804  }
805 
806  template <typename T>
807  void Graph<T>::addEdge(const Edge<T> *edge)
808  {
809  if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](const Edge<T> *edge_a)
810  { return (*edge == *edge_a); }) == edgeSet.end())
811  {
812  edgeSet.push_back(edge);
813  }
814  }
815 
816  template <typename T>
817  void Graph<T>::removeEdge(unsigned long edgeId)
818  {
819  auto edgeOpt = getEdge(edgeId);
820  if (edgeOpt.has_value())
821  {
822  edgeSet.erase(std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeOpt](const Edge<T> *edge)
823  { return (*(edgeOpt.value()) == *edge); }));
824  }
825  }
826 
827  template <typename T>
828  const std::list<const Node<T> *> Graph<T>::getNodeSet() const
829  {
830  std::list<const Node<T> *> nodeSet;
831  for (auto edge : edgeSet)
832  {
833  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
834  { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
835  {
836  nodeSet.push_back(edge->getNodePair().first);
837  }
838  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
839  { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
840  {
841  nodeSet.push_back(edge->getNodePair().second);
842  }
843  }
844  return nodeSet;
845  }
846 
847  template <typename T>
848  const std::optional<const Edge<T> *> Graph<T>::getEdge(unsigned long edgeId) const
849  {
850 
851  auto it = edgeSet.begin();
852  for (it; it != edgeSet.end(); ++it)
853  {
854  if ((*it)->getId() == edgeId)
855  {
856  return *it;
857  }
858  }
859 
860  return std::nullopt;
861  }
862 
863  template <typename T>
864  void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const
865  {
866  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
867  adjMatrix[nodeFrom].push_back(elem);
868 
869  //adjMatrix[nodeFrom.getId()].push_back(std::make_pair<const Node<T>,const Edge<T>>(nodeTo, edge));
870  }
871 
872  template <typename T>
873  int Graph<T>::writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
874  {
875  std::ofstream ofileGraph;
876  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
877  ofileGraph.open(completePathToFileGraph);
878  if (!ofileGraph.is_open())
879  {
880  // ERROR File Not Open
881  return -1;
882  }
883  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
884  { ofileGraph << e->getId() << "," << e->getNodePair().first->getId() << "," << e->getNodePair().second->getId() << "," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
885  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
886  ofileGraph.close();
887 
888  if (writeNodeFeat)
889  {
890  std::ofstream ofileNodeFeat;
891  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
892  ".csv";
893  ofileNodeFeat.open(completePathToFileNodeFeat);
894  if (!ofileNodeFeat.is_open())
895  {
896  // ERROR File Not Open
897  return -1;
898  }
899  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
900  { ofileNodeFeat << node->getId() << "," << node->getData() << std::endl; };
901  auto nodeSet = getNodeSet();
902  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
903  ofileNodeFeat.close();
904  }
905 
906  if (writeEdgeWeight)
907  {
908  std::ofstream ofileEdgeWeight;
909  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
910  ".csv";
911  ofileEdgeWeight.open(completePathToFileEdgeWeight);
912  if (!ofileEdgeWeight.is_open())
913  {
914  // ERROR File Not Open
915  return -1;
916  }
917  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
918  { ofileEdgeWeight << e->getId() << "," << (e->isWeighted().has_value() && e->isWeighted().value() ? (dynamic_cast<const Weighted *>(e))->getWeight() : 0.0) << "," << (e->isWeighted().has_value() && e->isWeighted().value() ? 1 : 0) << std::endl; };
919 
920  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
921  ofileEdgeWeight.close();
922  }
923  return 0;
924  }
925 
926  template <typename T>
927  int Graph<T>::readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
928  {
929  std::ifstream ifileGraph;
930  std::ifstream ifileNodeFeat;
931  std::ifstream ifileEdgeWeight;
932  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
933  std::map<unsigned long, bool> edgeDirectedMap;
934  std::map<unsigned long, T> nodeFeatMap;
935  std::map<unsigned long, double> edgeWeightMap;
936  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
937  ifileGraph.open(completePathToFileGraph);
938  if (!ifileGraph.is_open())
939  {
940  // ERROR File Not Open
941  return -1;
942  }
943  char comma;
944  for (;;)
945  { /* loop continually */
946  unsigned long edgeId;
947  unsigned long nodeId1;
948  unsigned long nodeId2;
949  bool directed;
950  ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
951  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
952  edgeDirectedMap[edgeId] = directed;
953  if (ifileGraph.fail() || ifileGraph.eof())
954  break;
955  ifileGraph.ignore(128, '\n');
956  }
957  ifileGraph.close();
958 
959  if (readNodeFeat)
960  {
961  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
962  ".csv";
963  ifileNodeFeat.open(completePathToFileNodeFeat);
964  if (!ifileNodeFeat.is_open())
965  {
966  // ERROR File Not Open
967  return -1;
968  }
969  for (;;)
970  { /* loop continually */
971  unsigned long nodeId;
972  T nodeFeat;
973  ifileNodeFeat >> nodeId >> comma >> nodeFeat;
974  nodeFeatMap[nodeId] = nodeFeat;
975  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
976  break;
977  ifileNodeFeat.ignore(128, '\n');
978  }
979  ifileNodeFeat.close();
980  }
981 
982  if (readEdgeWeight)
983  {
984  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
985  ".csv";
986  ifileEdgeWeight.open(completePathToFileEdgeWeight);
987  if (!ifileEdgeWeight.is_open())
988  {
989  // ERROR File Not Open
990  return -1;
991  }
992  for (;;)
993  { /* loop continually */
994  unsigned long edgeId;
995  double weight;
996  bool weighted;
997  ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
998  if (weighted)
999  {
1000  edgeWeightMap[edgeId] = weight;
1001  }
1002  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
1003  break;
1004  ifileEdgeWeight.ignore(128, '\n');
1005  }
1006  ifileEdgeWeight.close();
1007  }
1008  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
1009  return 0;
1010  }
1011 
1012  template <typename T>
1013  int Graph<T>::writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
1014  {
1015  std::ofstream ofileGraph;
1016  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
1017  ofileGraph.open(completePathToFileGraph);
1018  if (!ofileGraph.is_open())
1019  {
1020  // ERROR File Not Open
1021  return -1;
1022  }
1023  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
1024  { ofileGraph << e->getId() << "\t" << e->getNodePair().first->getId() << "\t" << e->getNodePair().second->getId() << "\t" << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
1025  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
1026  ofileGraph.close();
1027 
1028  if (writeNodeFeat)
1029  {
1030  std::ofstream ofileNodeFeat;
1031  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
1032  ".tsv";
1033  ofileNodeFeat.open(completePathToFileNodeFeat);
1034  if (!ofileNodeFeat.is_open())
1035  {
1036  // ERROR File Not Open
1037  return -1;
1038  }
1039  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
1040  { ofileNodeFeat << node->getId() << "\t" << node->getData() << std::endl; };
1041  auto nodeSet = getNodeSet();
1042  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
1043  ofileNodeFeat.close();
1044  }
1045 
1046  if (writeEdgeWeight)
1047  {
1048  std::ofstream ofileEdgeWeight;
1049  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
1050  ".tsv";
1051  ofileEdgeWeight.open(completePathToFileEdgeWeight);
1052  if (!ofileEdgeWeight.is_open())
1053  {
1054  // ERROR File Not Open
1055  return -1;
1056  }
1057  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
1058  { ofileEdgeWeight << e->getId() << "\t" << (e->isWeighted().has_value() && e->isWeighted().value() ? (dynamic_cast<const Weighted *>(e))->getWeight() : 0.0) << "\t" << (e->isWeighted().has_value() && e->isWeighted().value() ? 1 : 0) << std::endl; };
1059 
1060  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
1061  ofileEdgeWeight.close();
1062  }
1063  return 0;
1064  }
1065 
1066  template <typename T>
1067  int Graph<T>::readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
1068  {
1069  std::ifstream ifileGraph;
1070  std::ifstream ifileNodeFeat;
1071  std::ifstream ifileEdgeWeight;
1072  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
1073  std::map<unsigned long, bool> edgeDirectedMap;
1074  std::map<unsigned long, T> nodeFeatMap;
1075  std::map<unsigned long, double> edgeWeightMap;
1076  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
1077  ifileGraph.open(completePathToFileGraph);
1078  if (!ifileGraph.is_open())
1079  {
1080  // ERROR File Not Open
1081  return -1;
1082  }
1083  for (;;)
1084  { /* loop continually */
1085  unsigned long edgeId;
1086  unsigned long nodeId1;
1087  unsigned long nodeId2;
1088  bool directed;
1089  ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
1090  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
1091  edgeDirectedMap[edgeId] = directed;
1092  if (ifileGraph.fail() || ifileGraph.eof())
1093  break;
1094  ifileGraph.ignore(128, '\n');
1095  }
1096  ifileGraph.close();
1097 
1098  if (readNodeFeat)
1099  {
1100  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
1101  ".tsv";
1102  ifileNodeFeat.open(completePathToFileNodeFeat);
1103  if (!ifileNodeFeat.is_open())
1104  {
1105  // ERROR File Not Open
1106  return -1;
1107  }
1108  for (;;)
1109  { /* loop continually */
1110  unsigned long nodeId;
1111  T nodeFeat;
1112  ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
1113  nodeFeatMap[nodeId] = nodeFeat;
1114  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
1115  break;
1116  ifileNodeFeat.ignore(128, '\n');
1117  }
1118  ifileNodeFeat.close();
1119  }
1120 
1121  if (readEdgeWeight)
1122  {
1123  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
1124  ".tsv";
1125  ifileEdgeWeight.open(completePathToFileEdgeWeight);
1126  if (!ifileEdgeWeight.is_open())
1127  {
1128  // ERROR File Not Open
1129  return -1;
1130  }
1131  for (;;)
1132  { /* loop continually */
1133  unsigned long edgeId;
1134  double weight;
1135  bool weighted;
1136  ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
1137  if (weighted)
1138  {
1139  edgeWeightMap[edgeId] = weight;
1140  }
1141  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
1142  break;
1143  ifileEdgeWeight.ignore(128, '\n');
1144  }
1145  ifileEdgeWeight.close();
1146  }
1147  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
1148  return 0;
1149  }
1150 
1151  template <typename T>
1152  void Graph<T>::recreateGraphFromReadFiles(std::map<unsigned long, std::pair<unsigned long, unsigned long>> &edgeMap, std::map<unsigned long, bool> &edgeDirectedMap, std::map<unsigned long, T> &nodeFeatMap, std::map<unsigned long, double> &edgeWeightMap)
1153  {
1154  std::map<unsigned long, Node<T> *> nodeMap;
1155  for (auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
1156  {
1157  Node<T> *node1 = nullptr;
1158  Node<T> *node2 = nullptr;
1159  if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
1160  {
1161  //Create new Node
1162  T feat;
1163  if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
1164  {
1165  feat = nodeFeatMap.at(edgeIt->second.first);
1166  }
1167  node1 = new Node<T>(edgeIt->second.first, feat);
1168  nodeMap[edgeIt->second.first] = node1;
1169  }
1170  else
1171  {
1172  node1 = nodeMap.at(edgeIt->second.first);
1173  }
1174  if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
1175  {
1176  //Create new Node
1177  T feat;
1178  if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
1179  {
1180  feat = nodeFeatMap.at(edgeIt->second.second);
1181  }
1182  node2 = new Node<T>(edgeIt->second.second, feat);
1183  nodeMap[edgeIt->second.second] = node2;
1184  }
1185  else
1186  {
1187  node2 = nodeMap.at(edgeIt->second.second);
1188  }
1189 
1190  if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
1191  {
1192  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1193  {
1194  auto edge = new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1195  addEdge(edge);
1196  }
1197  else
1198  {
1199  auto edge = new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1200  addEdge(edge);
1201  }
1202  }
1203  else
1204  {
1205  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1206  {
1207  auto edge = new DirectedEdge<T>(edgeIt->first, *node1, *node2);
1208  addEdge(edge);
1209  }
1210  else
1211  {
1212  auto edge = new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
1213  addEdge(edge);
1214  }
1215  }
1216  }
1217  }
1218 
1219  template <typename T>
1220  void Graph<T>::greedyPartition(PartitionMap<T> &partitionMap) const
1221  {
1222  unsigned int index = 0;
1223  unsigned int numberOfPartitions = partitionMap.size();
1224  if (index == numberOfPartitions)
1225  {
1226  //ERROR partition map of zero element
1227  return;
1228  }
1229  auto edgeSet = getEdgeSet();
1230  for (auto edge : edgeSet)
1231  {
1232  partitionMap.at(index)->addEdge(edge);
1233  index++;
1234  index = index % numberOfPartitions;
1235  }
1236  }
1237 
1238  template <typename T>
1239  const AdjacencyMatrix<T> Graph<T>::getAdjMatrix() const
1240  {
1241  AdjacencyMatrix<T> adj;
1242  auto edgeSetIt = edgeSet.begin();
1243  for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
1244  {
1245  if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
1246  {
1247  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(*edgeSetIt);
1248  addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
1249  }
1250  else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
1251  {
1252  const UndirectedEdge<T> *ud_edge = dynamic_cast<const UndirectedEdge<T> *>(*edgeSetIt);
1253  ;
1254  addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
1255  addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
1256  }
1257  else
1258  { //is a simple edge we cannot create adj matrix
1259  return adj;
1260  }
1261  }
1262  return adj;
1263  }
1264 
1265  template <typename T>
1266  const DijkstraResult Graph<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
1267  {
1268  DijkstraResult result;
1269  result.success = false;
1270  result.errorMessage = "";
1271  result.result = INF_DOUBLE;
1272  auto nodeSet = getNodeSet();
1273  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1274  {
1275  // check if source node exist in the graph
1276  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1277  return result;
1278  }
1279  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1280  {
1281  // check if target node exist in the graph
1282  result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
1283  return result;
1284  }
1285  const AdjacencyMatrix<T> adj = getAdjMatrix();
1286  // n denotes the number of vertices in graph
1287  int n = adj.size();
1288 
1289  // setting all the distances initially to INF_DOUBLE
1290  std::map<const Node<T> *, double> dist;
1291 
1292  for (auto elem : adj)
1293  {
1294  dist[elem.first] = INF_DOUBLE;
1295  }
1296 
1297  // creating a min heap using priority queue
1298  // first element of pair contains the distance
1299  // second element of pair contains the vertex
1300  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1301  std::greater<std::pair<double, const Node<T> *>>>
1302  pq;
1303 
1304  // pushing the source vertex 's' with 0 distance in min heap
1305  pq.push(std::make_pair(0.0, &source));
1306 
1307  // marking the distance of source as 0
1308  dist[&source] = 0;
1309 
1310  while (!pq.empty())
1311  {
1312  // second element of pair denotes the node / vertex
1313  const Node<T> *currentNode = pq.top().second;
1314 
1315  // first element of pair denotes the distance
1316  double currentDist = pq.top().first;
1317 
1318  pq.pop();
1319 
1320  // for all the reachable vertex from the currently exploring vertex
1321  // we will try to minimize the distance
1322  if (adj.find(currentNode) != adj.end())
1323  {
1324  for (std::pair<const Node<T> *, const Edge<T> *> elem : adj.at(currentNode))
1325  {
1326  // minimizing distances
1327  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1328  {
1329  if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1330  {
1331  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(elem.second);
1332  if (currentDist + dw_edge->getWeight() < dist[elem.first])
1333  {
1334  dist[elem.first] = currentDist + dw_edge->getWeight();
1335  pq.push(std::make_pair(dist[elem.first], elem.first));
1336  }
1337  }
1338  else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1339  {
1340  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
1341  if (currentDist + udw_edge->getWeight() < dist[elem.first])
1342  {
1343  dist[elem.first] = currentDist + udw_edge->getWeight();
1344  pq.push(std::make_pair(dist[elem.first], elem.first));
1345  }
1346  }
1347  else
1348  {
1349  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
1350  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1351  return result;
1352  }
1353  }
1354  else
1355  {
1356  // No Weighted Edge
1357  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1358  return result;
1359  }
1360  }
1361  }
1362  }
1363  if (dist[&target] != INF_DOUBLE)
1364  {
1365  result.success = true;
1366  result.errorMessage = "";
1367  result.result = dist[&target];
1368  return result;
1369  }
1370  result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
1371  result.result = -1;
1372  return result;
1373  }
1374 
1375  template <typename T>
1376  const std::vector<Node<T>> Graph<T>::breadth_first_search(const Node<T> &start) const
1377  {
1378  // vector to keep track of visited nodes
1379  std::vector<Node<T>> visited;
1380  auto nodeSet = getNodeSet();
1381  //check is exist node in the graph
1382  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1383  {
1384  return visited;
1385  }
1386  const AdjacencyMatrix<T> adj = getAdjMatrix();
1387  // queue that stores vertices that need to be further explored
1388  std::queue<const Node<T> *> tracker;
1389 
1390  // mark the starting node as visited
1391  visited.push_back(start);
1392  tracker.push(&start);
1393  while (!tracker.empty())
1394  {
1395  const Node<T> *node = tracker.front();
1396  tracker.pop();
1397  if (adj.find(node) != adj.end())
1398  {
1399  for (auto elem : adj.at(node))
1400  {
1401  // if the node is not visited then mark it as visited
1402  // and push it to the queue
1403  if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1404  {
1405  visited.push_back(*(elem.first));
1406  tracker.push(elem.first);
1407  }
1408  }
1409  }
1410  }
1411 
1412  return visited;
1413  }
1414 
1415  template <typename T>
1416  const std::vector<Node<T>> Graph<T>::depth_first_search(const Node<T> &start) const
1417  {
1418  // vector to keep track of visited nodes
1419  std::vector<Node<T>> visited;
1420  auto nodeSet = getNodeSet();
1421  //check is exist node in the graph
1422  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1423  {
1424  return visited;
1425  }
1426  const AdjacencyMatrix<T> adj = getAdjMatrix();
1427  std::function<void(const AdjacencyMatrix<T> &, const Node<T> &, std::vector<Node<T>> &)> explore;
1428  explore = [&explore](const AdjacencyMatrix<T> &adj, const Node<T> &node, std::vector<Node<T>> &visited) -> void
1429  {
1430  visited.push_back(node);
1431  if (adj.find(&node) != adj.end())
1432  {
1433  for (auto x : adj.at(&node))
1434  {
1435  if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1436  {
1437  explore(adj, *(x.first), visited);
1438  }
1439  }
1440  }
1441  };
1442  explore(adj, start, visited);
1443 
1444  return visited;
1445  }
1446 
1447  template <typename T>
1449  {
1450  if (!isDirectedGraph())
1451  {
1452  return false;
1453  }
1454  enum nodeStates : uint8_t
1455  {
1456  not_visited,
1457  in_stack,
1458  visited
1459  };
1460  auto nodeSet = this->getNodeSet();
1461  auto adjMatrix = this->getAdjMatrix();
1462 
1463  /* State of the node.
1464  *
1465  * It is a vector of "nodeStates" which represents the state node is in.
1466  * It can take only 3 values: "not_visited", "in_stack", and "visited".
1467  *
1468  * Initially, all nodes are in "not_visited" state.
1469  */
1470  std::map<unsigned long, nodeStates> state;
1471  for (auto node : nodeSet)
1472  {
1473  state[node->getId()] = not_visited;
1474  }
1475  int stateCounter = 0;
1476 
1477  // Start visiting each node.
1478  for (auto node : nodeSet)
1479  {
1480  // If a node is not visited, only then check for presence of cycle.
1481  // There is no need to check for presence of cycle for a visited
1482  // node as it has already been checked for presence of cycle.
1483  if (state[node->getId()] == not_visited)
1484  {
1485  // Check for cycle.
1486  std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &, const Node<T> *)> isCyclicDFSHelper;
1487  isCyclicDFSHelper = [this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states, const Node<T> *node)
1488  {
1489  // Add node "in_stack" state.
1490  states[node->getId()] = in_stack;
1491 
1492  // If the node has children, then recursively visit all children of the
1493  // node.
1494  auto const it = adjMatrix.find(node);
1495  if (it != adjMatrix.end())
1496  {
1497  for (auto child : it->second)
1498  {
1499  // If state of child node is "not_visited", evaluate that child
1500  // for presence of cycle.
1501  auto state_of_child = states.at((std::get<0>(child))->getId());
1502  if (state_of_child == not_visited)
1503  {
1504  if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1505  {
1506  return true;
1507  }
1508  }
1509  else if (state_of_child == in_stack)
1510  {
1511  // If child node was "in_stack", then that means that there
1512  // is a cycle in the graph. Return true for presence of the
1513  // cycle.
1514  return true;
1515  }
1516  }
1517  }
1518 
1519  // Current node has been evaluated for the presence of cycle and had no
1520  // cycle. Mark current node as "visited".
1521  states[node->getId()] = visited;
1522  // Return that current node didn't result in any cycles.
1523  return false;
1524  };
1525  if (isCyclicDFSHelper(adjMatrix, state, node))
1526  {
1527  return true;
1528  }
1529  }
1530  }
1531 
1532  // All nodes have been safely traversed, that means there is no cycle in
1533  // the graph. Return false.
1534  return false;
1535  }
1536 
1537  template <typename T>
1539  {
1540  if (!isDirectedGraph())
1541  {
1542  return false;
1543  }
1544  auto adjMatrix = this->getAdjMatrix();
1545  auto nodeSet = this->getNodeSet();
1546 
1547  std::map<unsigned long, unsigned int> indegree;
1548  for (auto node : nodeSet)
1549  {
1550  indegree[node->getId()] = 0;
1551  }
1552  // Calculate the indegree i.e. the number of incident edges to the node.
1553  for (auto const &list : adjMatrix)
1554  {
1555  auto children = list.second;
1556  for (auto const &child : children)
1557  {
1558  indegree[std::get<0>(child)->getId()]++;
1559  }
1560  }
1561 
1562  std::queue<const Node<T> *> can_be_solved;
1563  for (auto node : nodeSet)
1564  {
1565  // If a node doesn't have any input edges, then that node will
1566  // definately not result in a cycle and can be visited safely.
1567  if (!indegree[node->getId()])
1568  {
1569  can_be_solved.emplace(&(*node));
1570  }
1571  }
1572 
1573  // Vertices that need to be traversed.
1574  auto remain = this->getNodeSet().size();
1575  // While there are safe nodes that we can visit.
1576  while (!can_be_solved.empty())
1577  {
1578  auto solved = can_be_solved.front();
1579  // Visit the node.
1580  can_be_solved.pop();
1581  // Decrease number of nodes that need to be traversed.
1582  remain--;
1583 
1584  // Visit all the children of the visited node.
1585  auto it = adjMatrix.find(solved);
1586  if (it != adjMatrix.end())
1587  {
1588  for (auto child : it->second)
1589  {
1590  // Check if we can visited the node safely.
1591  if (--indegree[std::get<0>(child)->getId()] == 0)
1592  {
1593  // if node can be visited safely, then add that node to
1594  // the visit queue.
1595  can_be_solved.emplace(std::get<0>(child));
1596  }
1597  }
1598  }
1599  }
1600 
1601  // If there are still nodes that we can't visit, then it means that
1602  // there is a cycle and return true, else return false.
1603  return !(remain == 0);
1604  }
1605 
1606  template <typename T>
1608  {
1609  auto edgeSet = this->getEdgeSet();
1610  for (auto edge : edgeSet)
1611  {
1612  if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1613  {
1614  //Found Undirected Edge
1615  return false;
1616  }
1617  }
1618  //No Undirected Edge
1619  return true;
1620  }
1621 
1622  template <typename T>
1623  const DialResult Graph<T>::dial(const Node<T> &source, int maxWeight) const
1624  {
1625  DialResult result;
1626  result.success = false;
1627 
1628  auto adj = getAdjMatrix();
1629  auto nodeSet = getNodeSet();
1630 
1631  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1632  {
1633  // check if source node exist in the graph
1634  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1635  return result;
1636  }
1637  /* With each distance, iterator to that vertex in
1638  its bucket is stored so that vertex can be deleted
1639  in O(1) at time of updation. So
1640  dist[i].first = distance of ith vertex from src vertex
1641  dits[i].second = vertex i in bucket number */
1642  unsigned int V = nodeSet.size();
1643  std::map<const Node<T> *, std::pair<long, const Node<T> *>> dist;
1644 
1645  // Initialize all distances as infinite (INF)
1646  for (auto node : nodeSet)
1647  {
1648  dist[&(*node)].first = std::numeric_limits<long>::max();
1649  }
1650 
1651  // Create buckets B[].
1652  // B[i] keep vertex of distance label i
1653  std::list<const Node<T> *> B[maxWeight * V + 1];
1654 
1655  B[0].push_back(&source);
1656  dist[&source].first = 0;
1657 
1658  int idx = 0;
1659  while (1)
1660  {
1661  // Go sequentially through buckets till one non-empty
1662  // bucket is found
1663  while (B[idx].size() == 0 && idx < maxWeight * V)
1664  {
1665  idx++;
1666  }
1667 
1668  // If all buckets are empty, we are done.
1669  if (idx == maxWeight * V)
1670  {
1671  break;
1672  }
1673 
1674  // Take top vertex from bucket and pop it
1675  auto u = B[idx].front();
1676  B[idx].pop_front();
1677 
1678  // Process all adjacents of extracted vertex 'u' and
1679  // update their distanced if required.
1680  for (auto i = adj[u].begin(); i != adj[u].end(); ++i)
1681  {
1682  auto v = (*i).first;
1683  int weight = 0;
1684  if ((*i).second->isWeighted().has_value() && (*i).second->isWeighted().value())
1685  {
1686  if ((*i).second->isDirected().has_value() && (*i).second->isDirected().value())
1687  {
1688  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>((*i).second);
1689  weight = dw_edge->getWeight();
1690  }
1691  else if ((*i).second->isDirected().has_value() && !(*i).second->isDirected().value())
1692  {
1693  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>((*i).second);
1694  weight = udw_edge->getWeight();
1695  }
1696  else
1697  {
1698  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
1699  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1700  return result;
1701  }
1702  }
1703  else
1704  {
1705  // No Weighted Edge
1706  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1707  return result;
1708  }
1709  auto u_i = std::find_if(dist.begin(), dist.end(), [u](std::pair<const Node<T> *, std::pair<long, const Node<T> *>> const &it)
1710  { return (*u == *(it.first)); });
1711 
1712  auto v_i = std::find_if(dist.begin(), dist.end(), [v](std::pair<const Node<T> *, std::pair<long, const Node<T> *>> const &it)
1713  { return (*v == *(it.first)); });
1714  long du = u_i->second.first;
1715  long dv = v_i->second.first;
1716 
1717  // If there is shorted path to v through u.
1718  if (dv > du + weight)
1719  {
1720  // If dv is not INF then it must be in B[dv]
1721  // bucket, so erase its entry using iterator
1722  // in O(1)
1723  if (dv != std::numeric_limits<long>::max())
1724  {
1725  auto findIter = std::find(B[dv].begin(), B[dv].end(), dist[v].second);
1726  B[dv].erase(findIter);
1727  }
1728 
1729  // updating the distance
1730  dist[v].first = du + weight;
1731  dv = dist[v].first;
1732 
1733  // pushing vertex v into updated distance's bucket
1734  B[dv].push_front(v);
1735 
1736  // storing updated iterator in dist[v].second
1737  dist[v].second = *(B[dv].begin());
1738  }
1739  }
1740  }
1741  for (auto dist_i : dist)
1742  {
1743  result.minDistanceMap[dist_i.first->getId()] = dist_i.second.first;
1744  }
1745  result.success = true;
1746 
1747  return result;
1748  }
1749 
1750  template <typename T>
1751  int Graph<T>::writeToFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
1752  {
1753  if (format == InputOutputFormat::STANDARD_CSV)
1754  {
1755  return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1756  }
1757  else if (format == InputOutputFormat::STANDARD_TSV)
1758  {
1759  return writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1760  }
1761  else
1762  {
1763  //OUTPUT FORMAT NOT RECOGNIZED
1764  return -1;
1765  }
1766  }
1767 
1768  template <typename T>
1769  int Graph<T>::readFromFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
1770  {
1771  if (format == InputOutputFormat::STANDARD_CSV)
1772  {
1773  return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1774  }
1775  else if (format == InputOutputFormat::STANDARD_TSV)
1776  {
1777  return readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1778  }
1779  else
1780  {
1781  //OUTPUT FORMAT NOT RECOGNIZED
1782  return -1;
1783  }
1784  }
1785 
1786  template <typename T>
1787  PartitionMap<T> Graph<T>::partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
1788  {
1789  PartitionMap<T> partitionMap;
1790  for (unsigned int i = 0; i < numberOfPartitions; ++i)
1791  {
1792  partitionMap[i] = new Partition<T>(i);
1793  }
1794  if (algorithm == PartitionAlgorithm::GREEDY_VC)
1795  {
1796  greedyPartition(partitionMap);
1797  }
1798  else
1799  {
1800  //Error not recognized algorithm
1801  partitionMap.clear();
1802  }
1803  return partitionMap;
1804  }
1805 
1807  template <typename T>
1808  class Graph_TS : public Graph<T>, public ThreadSafe
1809  {
1810  public:
1811  Graph_TS() = default;
1812  Graph_TS(const std::list<const Edge<T> *> &edgeSet);
1813  Graph_TS(const Graph<T> &graph);
1814  ~Graph_TS() = default;
1823  const std::list<const Edge<T> *> &getEdgeSet() const override;
1832  void setEdgeSet(std::list<const Edge<T> *> &edgeSet) override;
1841  void addEdge(const Edge<T> *edge) override;
1850  void removeEdge(unsigned long edgeId) override;
1859  const std::list<const Node<T> *> getNodeSet() const override;
1869  const std::optional<const Edge<T> *> getEdge(unsigned long edgeId) const override;
1875  const AdjacencyMatrix<T> getAdjMatrix() const override;
1888  const DijkstraResult dijkstra(const Node<T> &source, const Node<T> &target) const override;
1899  const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const override;
1910  const std::vector<Node<T>> depth_first_search(const Node<T> &start) const override;
1911 
1920  bool isCyclicDirectedGraphDFS() const override;
1921 
1930  bool isCyclicDirectedGraphBFS() const override;
1931 
1939  bool isDirectedGraph() const override;
1940 
1967  const DialResult dial(const Node<T> &source, int maxWeight) const override;
1968 
1969  int writeToFile(typename Graph<T>::InputOutputFormat format = Graph<T>::InputOutputFormat::STANDARD_CSV, const std::string &workingDir = ".", const std::string &OFileName = "graph", bool compress = false, bool writeNodeFeat = false, bool writeEdgeWeight = false) const override;
1970 
1984  int readFromFile(typename Graph<T>::InputOutputFormat format = Graph<T>::InputOutputFormat::STANDARD_CSV, const std::string &workingDir = ".", const std::string &OFileName = "graph", bool compress = false, bool readNodeFeat = false, bool readEdgeWeight = false) override;
1985 
1995  PartitionMap<T> partitionGraph(typename Graph<T>::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const override;
1996  };
1997 
1998  template <typename T>
1999  Graph_TS<T>::Graph_TS(const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet), ThreadSafe() {}
2000 
2001  template <typename T>
2002  Graph_TS<T>::Graph_TS(const Graph<T> &graph) : Graph<T>(graph), ThreadSafe() {}
2003 
2004  template <typename T>
2005  const std::list<const Edge<T> *> &Graph_TS<T>::getEdgeSet() const
2006  {
2007  std::lock_guard<std::mutex> lock(mutex);
2008  return Graph<T>::getEdgeSet();
2009  }
2010 
2011  template <typename T>
2012  void Graph_TS<T>::setEdgeSet(std::list<const Edge<T> *> &edgeSet)
2013  {
2014  getLock();
2015  Graph<T>::setEdgeSet(edgeSet);
2016  releaseLock();
2017  }
2018 
2019  template <typename T>
2020  void Graph_TS<T>::addEdge(const Edge<T> *edge)
2021  {
2022  getLock();
2023  Graph<T>::addEdge(edge);
2024  releaseLock();
2025  }
2026 
2027  template <typename T>
2028  void Graph_TS<T>::removeEdge(unsigned long edgeId)
2029  {
2030  getLock();
2031  Graph<T>::removeEdge(edgeId);
2032  releaseLock();
2033  }
2034 
2035  template <typename T>
2036  const std::list<const Node<T> *> Graph_TS<T>::getNodeSet() const
2037  {
2038  getLock();
2039  auto ns = Graph<T>::getNodeSet();
2040  releaseLock();
2041  return ns;
2042  }
2043 
2044  template <typename T>
2045  const std::optional<const Edge<T> *> Graph_TS<T>::getEdge(unsigned long edgeId) const
2046  {
2047  getLock();
2048  auto e = Graph<T>::getEdge(edgeId);
2049  releaseLock();
2050  return e;
2051  }
2052 
2053  template <typename T>
2054  const AdjacencyMatrix<T> Graph_TS<T>::getAdjMatrix() const
2055  {
2056  getLock();
2057  auto adjm = Graph<T>::getAdjMatrix();
2058  releaseLock();
2059  return adjm;
2060  }
2061 
2062  template <typename T>
2063  const DijkstraResult Graph_TS<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
2064  {
2065  getLock();
2066  auto dij = Graph<T>::dijkstra(source, target);
2067  releaseLock();
2068  return dij;
2069  }
2070 
2071  template <typename T>
2072  const std::vector<Node<T>> Graph_TS<T>::breadth_first_search(const Node<T> &start) const
2073  {
2074  getLock();
2075  auto bfs = Graph<T>::breadth_first_search(start);
2076  releaseLock();
2077  return bfs;
2078  }
2079 
2080  template <typename T>
2081  const std::vector<Node<T>> Graph_TS<T>::depth_first_search(const Node<T> &start) const
2082  {
2083  getLock();
2084  auto dfs = Graph<T>::depth_first_search(start);
2085  releaseLock();
2086  return dfs;
2087  }
2088 
2089  template <typename T>
2091  {
2092  getLock();
2093  auto result = Graph<T>::isCyclicDirectedGraphDFS();
2094  releaseLock();
2095  return result;
2096  }
2097 
2098  template <typename T>
2100  {
2101  getLock();
2102  auto result = Graph<T>::isCyclicDirectedGraphBFS();
2103  releaseLock();
2104  return result;
2105  }
2106 
2107  template <typename T>
2109  {
2110  getLock();
2111  auto result = Graph<T>::isDirectedGraph();
2112  releaseLock();
2113  return result;
2114  }
2115 
2116  template <typename T>
2117  const DialResult Graph_TS<T>::dial(const Node<T> &source, int maxWeight) const
2118  {
2119  getLock();
2120  auto dial = Graph<T>::dial(source, maxWeight);
2121  releaseLock();
2122  return dial;
2123  }
2124 
2125  template <typename T>
2126  int Graph_TS<T>::writeToFile(typename Graph<T>::InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
2127  {
2128  getLock();
2129  auto result = Graph<T>::writeToFile(format, workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
2130  releaseLock();
2131  return result;
2132  }
2133 
2134  template <typename T>
2135  int Graph_TS<T>::readFromFile(typename Graph<T>::InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
2136  {
2137  getLock();
2138  auto result = Graph<T>::readFromFile(format, workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
2139  releaseLock();
2140  return result;
2141  }
2142 
2143  template <typename T>
2144  PartitionMap<T> Graph_TS<T>::partitionGraph(typename Graph<T>::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
2145  {
2146  getLock();
2147  auto partitions = Graph<T>::partitionGraph(algorithm, numberOfPartitions);
2148  releaseLock();
2149  return partitions;
2150  }
2151 
2152  template <typename T>
2153  class Partition : public Graph<T>
2154  {
2155  public:
2156  Partition();
2157  Partition(unsigned int partitionId);
2158  Partition(const std::list<const Edge<T> *> &edgeSet);
2159  Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet);
2160  ~Partition() = default;
2166  unsigned int getPartitionId() const;
2172  void setPartitionId(unsigned int partitionId);
2173 
2174  private:
2175  unsigned int partitionId;
2176  };
2177 
2185  template <typename T>
2186  static PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap);
2187 
2195  template <typename T>
2196  static unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap);
2197 
2205  template <typename T>
2206  static unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap);
2207 
2215  template <typename T>
2216  static unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap);
2217 
2225  template <typename T>
2226  static unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap);
2227 
2235  template <typename T>
2236  static unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap);
2237 
2245  template <typename T>
2246  static unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap);
2247 
2255  template <typename T>
2256  static unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap);
2257 
2265  template <typename T>
2266  static unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap);
2267 
2268  template <typename T>
2270  {
2271  partitionId = 0;
2272  }
2273 
2274  template <typename T>
2275  Partition<T>::Partition(unsigned int partitionId) : Graph<T>()
2276  {
2277  this->partitionId = partitionId;
2278  }
2279 
2280  template <typename T>
2281  Partition<T>::Partition(const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
2282  {
2283  partitionId = 0;
2284  }
2285 
2286  template <typename T>
2287  Partition<T>::Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
2288  {
2289  this->partitionId = partitionId;
2290  }
2291 
2292  template <typename T>
2293  unsigned int Partition<T>::getPartitionId() const
2294  {
2295  return partitionId;
2296  }
2297 
2298  template <typename T>
2299  void Partition<T>::setPartitionId(unsigned int partitionId)
2300  {
2301  this->partitionId = partitionId;
2302  }
2303 
2304  template <typename T>
2305  PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap)
2306  {
2307  PartitioningStats result;
2308  result.numberOfPartitions = partitionMap.size();
2309  result.numberOfNodes = getNumberOfNodes(partitionMap);
2310  result.numberOfEdges = getNumberOfEdges(partitionMap);
2311  result.replicatedNodesCount = getNumberOfReplicatedNodes(partitionMap);
2312  result.replicatedEdgesCount = getNumberOfReplicatedEdges(partitionMap);
2313  result.maxEdgesLoad = getMaxEdgesLoad(partitionMap);
2314  result.minEdgesLoad = getMinEdgesLoad(partitionMap);
2315  result.maxNodesLoad = getMaxNodesLoad(partitionMap);
2316  result.minNodesLoad = getMinNodesLoad(partitionMap);
2317  result.edgesReplicationFactor = (double)result.replicatedEdgesCount / result.numberOfEdges;
2318  result.nodesReplicationFactor = (double)result.replicatedNodesCount / result.numberOfNodes;
2319  result.balanceEdgesFactor = (double)(result.maxEdgesLoad - result.minEdgesLoad) / (result.maxEdgesLoad);
2320  result.balanceNodesFactor = (double)(result.maxNodesLoad - result.minNodesLoad) / (result.maxNodesLoad);
2321  return result;
2322  }
2323 
2324  template <typename T>
2325  unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap)
2326  {
2327  unsigned int maxLoad = 0;
2328  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2329  {
2330  if (it->second->getEdgeSet().size() > maxLoad)
2331  {
2332  maxLoad = it->second->getEdgeSet().size();
2333  }
2334  }
2335  return maxLoad;
2336  }
2337 
2338  template <typename T>
2339  unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap)
2340  {
2341  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
2342  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2343  {
2344  if (it->second->getEdgeSet().size() < minLoad)
2345  {
2346  minLoad = it->second->getEdgeSet().size();
2347  }
2348  }
2349  return minLoad;
2350  }
2351 
2352  template <typename T>
2353  unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap)
2354  {
2355  unsigned int maxLoad = 0;
2356  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2357  {
2358  if (it->second->getNodeSet().size() > maxLoad)
2359  {
2360  maxLoad = it->second->getNodeSet().size();
2361  }
2362  }
2363  return maxLoad;
2364  }
2365 
2366  template <typename T>
2367  unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap)
2368  {
2369  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
2370  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2371  {
2372  if (it->second->getNodeSet().size() < minLoad)
2373  {
2374  minLoad = it->second->getNodeSet().size();
2375  }
2376  }
2377  return minLoad;
2378  }
2379 
2380  template <typename T>
2381  unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap)
2382  {
2383  unsigned int numberOfEdges = 0;
2384  std::list<const Edge<T> *> edgeSet;
2385 
2386  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2387  {
2388  const std::list<const Edge<T> *> partitionEdgeSet = it->second->getEdgeSet();
2389  for (auto it2 = partitionEdgeSet.begin(); it2 != partitionEdgeSet.end(); ++it2)
2390  {
2391  if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](const Edge<T> *edge)
2392  { return (*(*it2) == *edge); }) == edgeSet.end())
2393  {
2394  edgeSet.push_back(*it2);
2395  }
2396  }
2397  }
2398 
2399  return edgeSet.size();
2400  }
2401 
2402  template <typename T>
2403  unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap)
2404  {
2405  unsigned int numberOfNodes = 0;
2406  std::list<const Node<T> *> nodeSet;
2407 
2408  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2409  {
2410  const std::list<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
2411  for (auto it2 = partitionNodeSet.begin(); it2 != partitionNodeSet.end(); ++it2)
2412  {
2413  if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](const Node<T> *node)
2414  { return (*(*it2) == *node); }) == nodeSet.end())
2415  {
2416  nodeSet.push_back(*it2);
2417  }
2418  }
2419  }
2420 
2421  return nodeSet.size();
2422  }
2423 
2424  template <typename T>
2425  unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap)
2426  {
2427 
2428  unsigned int numberOfEdges = 0;
2429  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2430  {
2431  numberOfEdges += it->second->getEdgeSet().size();
2432  }
2433  return numberOfEdges;
2434  }
2435 
2436  template <typename T>
2437  unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap)
2438  {
2439  unsigned int numberOfNodes = 0;
2440  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2441  {
2442  numberOfNodes += it->second->getNodeSet().size();
2443  }
2444  return numberOfNodes;
2445  }
2446 
2451  template <typename T>
2452  class Writer
2453  {
2454  public:
2464  virtual int writeGraph(const Graph<T> &graph, std::ofstream &file) = 0;
2465  };
2466 
2470  template <typename T>
2471  class Reader
2472  {
2482  virtual int ReadGraph(Graph<T> &graph, std::ifstream &file) = 0;
2483  };
2484 
2485  //ostream overload
2486  template <typename T>
2487  std::ostream &
2488  operator<<(std::ostream &os, const Node<T> &node)
2489  {
2490  os << "Node: {\n"
2491  << " Id:\t" << node.id << "\n Data:\t" << node.data << "\n}";
2492  return os;
2493  }
2494 
2495  template <typename T>
2496  std::ostream &operator<<(std::ostream &os, const Edge<T> &edge)
2497  {
2498  os << "((Node: " << edge.nodePair.first->getId() << ")) ?----- |Edge: " << edge.id << "|-----? ((Node: " << edge.nodePair.second->getId() << "))";
2499  return os;
2500  }
2501 
2502  template <typename T>
2503  std::ostream &operator<<(std::ostream &os, const DirectedEdge<T> &edge)
2504  {
2505  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getTo().getId() << "))";
2506  return os;
2507  }
2508 
2509  template <typename T>
2510  std::ostream &operator<<(std::ostream &os, const UndirectedEdge<T> &edge)
2511  {
2512  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
2513  return os;
2514  }
2515 
2516  template <typename T>
2517  std::ostream &operator<<(std::ostream &os, const DirectedWeightedEdge<T> &edge)
2518  {
2519  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getTo().getId() << "))";
2520  return os;
2521  }
2522 
2523  template <typename T>
2524  std::ostream &operator<<(std::ostream &os, const UndirectedWeightedEdge<T> &edge)
2525  {
2526  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
2527  return os;
2528  }
2529 
2530  template <typename T>
2531  std::ostream &operator<<(std::ostream &os, const AdjacencyMatrix<T> &adj)
2532  {
2533  os << "Adjacency Matrix:\n";
2534  auto it = adj.begin();
2535  unsigned long max_column = 0;
2536  for (it; it != adj.end(); ++it)
2537  {
2538  if (it->second.size() > max_column)
2539  {
2540  max_column = it->second.size();
2541  }
2542  }
2543  if (max_column == 0)
2544  {
2545  os << "ERROR in Print\n";
2546  return os;
2547  }
2548  else
2549  {
2550  it = adj.begin();
2551  os << "|--|";
2552  for (int i = 0; i < max_column; i++)
2553  {
2554  os << "-----|";
2555  }
2556  os << "\n";
2557  for (it; it != adj.end(); ++it)
2558  {
2559  os << "|N" << it->first->getId() << "|";
2560  auto it2 = it->second.begin();
2561  for (it2; it2 != it->second.end(); ++it2)
2562  {
2563  os << "N" << it2->first->getId() << ",E" << it2->second->getId() << "|";
2564  }
2565  os << "\n|--|";
2566  for (int i = 0; i < max_column; i++)
2567  {
2568  os << "-----|";
2569  }
2570  os << "\n";
2571  }
2572  }
2573  return os;
2574  }
2575 
2576 } // namespace CXXGRAPH
2577 #endif // __CXXGRAPH_H__
Definition: Graph.hpp:314
Definition: Graph.hpp:428
Definition: Graph.hpp:242
Class that implement the Thread Safe Graph.
Definition: Graph.hpp:1809
const std::optional< const Edge< T > * > getEdge(unsigned long edgeId) const override
Function that return an Edge with specific ID if Exist in the Graph Note: Thread Safe.
Definition: Graph.hpp:2045
const std::list< const Node< T > * > getNodeSet() const override
Function that return the Node Set of the Graph Note: Thread Safe.
Definition: Graph.hpp:2036
void setEdgeSet(std::list< const Edge< T > * > &edgeSet) override
Function set the Edge Set of the Graph Note: Thread Safe.
Definition: Graph.hpp:2012
bool isDirectedGraph() const override
This function checks if a graph is directed Note: Thread Safe.
Definition: Graph.hpp:2108
const DijkstraResult dijkstra(const Node< T > &source, const Node< T > &target) const override
Function runs the dijkstra algorithm for some source node and target node in the graph and returns th...
Definition: Graph.hpp:2063
void addEdge(const Edge< T > *edge) override
Function add an Edge to the Graph Edge Set Note: Thread Safe.
Definition: Graph.hpp:2020
PartitionMap< T > partitionGraph(typename Graph< T >::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const override
This function partition a graph in a set of partitions Note: Thread Safe.
Definition: Graph.hpp:2144
bool isCyclicDirectedGraphBFS() const override
This function uses BFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:2099
const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const override
Function performs the breadth first search algorithm over the graph Note: Thread Safe.
Definition: Graph.hpp:2072
void removeEdge(unsigned long edgeId) override
Function remove an Edge from the Graph Edge Set Note: Thread Safe.
Definition: Graph.hpp:2028
const std::list< const Edge< T > * > & getEdgeSet() const override
Function that return the Edge set of the Graph Note: Thread Safe.
Definition: Graph.hpp:2005
const std::vector< Node< T > > depth_first_search(const Node< T > &start) const override
Function performs the depth first search algorithm over the graph Note: Thread Safe.
Definition: Graph.hpp:2081
int readFromFile(typename Graph< T >::InputOutputFormat format=Graph< T >::InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool readNodeFeat=false, bool readEdgeWeight=false) override
This function write the graph in an output file Note: Thread Safe.
Definition: Graph.hpp:2135
const DialResult dial(const Node< T > &source, int maxWeight) const override
This function write the graph in an output file Note: Thread Safe.
Definition: Graph.hpp:2117
bool isCyclicDirectedGraphDFS() const override
This function uses DFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:2090
const AdjacencyMatrix< T > getAdjMatrix() const override
This function generate a list of adjacency matrix with every element of the matrix contain the node w...
Definition: Graph.hpp:2054
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:552
virtual const std::vector< Node< T > > depth_first_search(const Node< T > &start) const
Function performs the depth first search algorithm over the graph Note: No Thread Safe.
Definition: Graph.hpp:1416
E_PartitionAlgorithm
Specify the Partition Algorithm.
Definition: Graph.hpp:577
@ GREEDY_VC
A Greedy Vertex-Cut Algorithm.
Definition: Graph.hpp:578
virtual const std::list< const Edge< T > * > & getEdgeSet() const
Function that return the Edge set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:787
virtual const std::optional< const Edge< T > * > getEdge(unsigned long edgeId) const
Function that return an Edge with specific ID if Exist in the Graph Note: No Thread Safe.
Definition: Graph.hpp:848
virtual bool isCyclicDirectedGraphBFS() const
This function uses BFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:1538
virtual void removeEdge(unsigned long edgeId)
Function remove an Edge from the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:817
virtual bool isDirectedGraph() const
This function checks if a graph is directed Note: No Thread Safe.
Definition: Graph.hpp:1607
virtual const DialResult dial(const Node< T > &source, int maxWeight) const
This function write the graph in an output file Note: No Thread Safe.
Definition: Graph.hpp:1623
virtual const DijkstraResult dijkstra(const Node< T > &source, const Node< T > &target) const
Function runs the dijkstra algorithm for some source node and target node in the graph and returns th...
Definition: Graph.hpp:1266
virtual bool isCyclicDirectedGraphDFS() const
This function uses DFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:1448
virtual void addEdge(const Edge< T > *edge)
Function add an Edge to the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:807
virtual PartitionMap< T > partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
This function partition a graph in a set of partitions Note: No Thread Safe.
Definition: Graph.hpp:1787
virtual int readFromFile(InputOutputFormat format=InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool readNodeFeat=false, bool readEdgeWeight=false)
This function write the graph in an output file Note: No Thread Safe.
Definition: Graph.hpp:1769
virtual const AdjacencyMatrix< T > getAdjMatrix() const
This function generate a list of adjacency matrix with every element of the matrix contain the node w...
Definition: Graph.hpp:1239
virtual const std::list< const Node< T > * > getNodeSet() const
Function that return the Node Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:828
virtual const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const
Function performs the breadth first search algorithm over the graph Note: No Thread Safe.
Definition: Graph.hpp:1376
virtual void setEdgeSet(std::list< const Edge< T > * > &edgeSet)
Function set the Edge Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:793
E_InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
Definition: Graph.hpp:566
@ STANDARD_CSV
A standard csv format.
Definition: Graph.hpp:567
@ STANDARD_TSV
A standard tsv format.
Definition: Graph.hpp:568
Definition: Graph.hpp:136
Definition: Graph.hpp:2154
void setPartitionId(unsigned int partitionId)
Set the Partition ID.
Definition: Graph.hpp:2299
unsigned int getPartitionId() const
Get the Partition ID.
Definition: Graph.hpp:2293
Definition: Graph.hpp:2472
Definition: Graph.hpp:221
Definition: Graph.hpp:371
Definition: Graph.hpp:488
Definition: Graph.hpp:184
Definition: Graph.hpp:2453
virtual int writeGraph(const Graph< T > &graph, std::ofstream &file)=0
Function performs the writing of the Graph to the file.
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Graph.hpp:67
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Graph.hpp:58
Struct that contains the information about the partitioning statistics.
Definition: Graph.hpp:76