CXXGraph  0.1.3
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 
19 namespace CXXGRAPH
20 {
21  //STRING ERROR CONST EXPRESSION
22  constexpr char ERR_NO_DIR_OR_UNDIR_EDGE[] = "Edge are neither Directed neither Undirected";
23  constexpr char ERR_NO_WEIGHTED_EDGE[] = "Edge are not Weighted";
24  constexpr char ERR_DIJ_TARGET_NODE_NOT_REACHABLE[] = "Target Node not Reachable";
25  constexpr char ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH[] = "Target Node not inside Graph";
26  constexpr char ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH[] = "Source Node not inside Graph";
28  constexpr double INF_DOUBLE = std::numeric_limits<double>::max();
29  template <typename T>
30  class Node;
31  template <typename T>
32  class Edge;
33  template <typename T>
34  class DirectedEdge;
35  template <typename T>
36  class UndirectedEdge;
37  template <typename T>
38  class DirectedWeightedEdge;
39  template <typename T>
40  class UndirectedWeightedEdge;
41  template <typename T>
42  class Graph;
43  template <typename T>
44  class Partition;
45 
46  class Weighted;
47 
50  {
51  bool success; // TRUE if the function does not return error, FALSE otherwise
52  std::string errorMessage; //message of error
53  double result; //result (valid only if success is TRUE)
54  };
56 
59  {
60  unsigned int numberOfPartitions; // The number of Partitions
61  unsigned int numberOfNodes; // The number of Nodes
62  unsigned int replicatedNodesCount; // The number of Nodes that are replicated
63  unsigned int numberOfEdges; // The number of edges
64  unsigned int replicatedEdgesCount; // The number of edges that are replicated
65  unsigned int maxEdgesLoad; // Maximum edges load of the partitions
66  unsigned int minEdgesLoad; // Minimun edges load of the partitions
67  unsigned int maxNodesLoad; // Maximum nodes load of the partitions
68  unsigned int minNodesLoad; // Minimun nodes load of the partitions
69  double balanceEdgesFactor; // The balance edges factor of the partitions (maxEdgesLoad - minEdgesLoad) / (maxEdgesLoad), 0 is the optimal partitioning
70  double balanceNodesFactor; // The balance edges factor of the partitions (maxNodesLoad - minNodesLoad) / (maxNodesLoad), 0 is the optimal partitioning
71  double nodesReplicationFactor; // The replication factor of the Nodes (replicatedNodesCount / numberOfNodes), 1 is the optimal partitioning
72  double edgesReplicationFactor; // The replication factor of the edges (replicatedEdgesCount / numberOfEdges), 1 is the optimal partitioning
73 
74  friend std::ostream &operator<<(std::ostream &os, const PartitioningStats_struct &partitionStats)
75  {
76  os << "Partitioning Stats:\n";
77  os << "\tNumber of Partitions: " << partitionStats.numberOfPartitions << "\n";
78  os << "\tNumber of Nodes: " << partitionStats.numberOfNodes << "\n";
79  os << "\tNumber of Edges: " << partitionStats.numberOfEdges << "\n";
80  os << "\tNumber of Nodes Replica: " << partitionStats.replicatedNodesCount << "\n";
81  os << "\tNumber of Edges Replica: " << partitionStats.replicatedEdgesCount << "\n";
82  os << "\tNodes Replication Factor: " << partitionStats.nodesReplicationFactor << "\n";
83  os << "\tEdges Replication Factor: " << partitionStats.edgesReplicationFactor << "\n";
84  os << "\tMax Edges Load: " << partitionStats.maxEdgesLoad << "\n";
85  os << "\tMin Edges Load: " << partitionStats.minEdgesLoad << "\n";
86  os << "\tBalance Edges Factor: " << partitionStats.balanceEdgesFactor << "\n";
87  os << "\tMax Nodes Load: " << partitionStats.maxNodesLoad << "\n";
88  os << "\tMin Nodes Load: " << partitionStats.minNodesLoad << "\n";
89  os << "\tBalance Nodes Factor: " << partitionStats.balanceNodesFactor << "\n";
90  return os;
91  }
92  };
94 
95  template <typename T>
96  using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *, const Edge<T> *>>>;
97 
98  template <typename T>
99  std::ostream &operator<<(std::ostream &o, const Node<T> &node);
100  template <typename T>
101  std::ostream &operator<<(std::ostream &o, const Edge<T> &edge);
102  template <typename T>
103  std::ostream &operator<<(std::ostream &o, const DirectedEdge<T> &edge);
104  template <typename T>
105  std::ostream &operator<<(std::ostream &o, const UndirectedEdge<T> &edge);
106  template <typename T>
107  std::ostream &operator<<(std::ostream &o, const DirectedWeightedEdge<T> &edge);
108  template <typename T>
109  std::ostream &operator<<(std::ostream &o, const UndirectedWeightedEdge<T> &edge);
110  template <typename T>
111  std::ostream &operator<<(std::ostream &o, const Graph<T> &graph);
112  template <typename T>
113  std::ostream &operator<<(std::ostream &o, const AdjacencyMatrix<T> &adj);
114  template <typename T>
115  using PartitionMap = std::map<unsigned int, Partition<T> *>;
116 
117  template <typename T>
118  class Node
119  {
120  private:
121  unsigned long id;
122  T data;
123 
124  public:
125  Node(const unsigned long id, const T &data);
126  ~Node() = default;
127  const unsigned long &getId() const;
128  const T &getData() const;
129  //operator
130  bool operator==(const Node<T> &b) const;
131  bool operator<(const Node<T> &b) const;
132  friend std::ostream &operator<<<>(std::ostream &os, const Node<T> &node);
133  };
134 
135  template <typename T>
136  Node<T>::Node(const unsigned long id, const T &data)
137  {
138  this->id = id;
139  this->data = data;
140  }
141 
142  template <typename T>
143  const unsigned long &Node<T>::getId() const
144  {
145  return id;
146  }
147 
148  template <typename T>
149  const T &Node<T>::getData() const
150  {
151  return data;
152  }
153 
154  template <typename T>
155  bool Node<T>::operator==(const Node<T> &b) const
156  {
157  return (this->id == b.id && this->data == b.data);
158  }
159 
160  template <typename T>
161  bool Node<T>::operator<(const Node<T> &b) const
162  {
163  return (this->id < b.id);
164  }
165 
166  class Weighted
167  {
168  private:
169  double weight;
170 
171  public:
172  Weighted();
173  Weighted(const double weight);
174  virtual ~Weighted() = default;
175  double getWeight() const;
176  void setWeight(const double weight);
177  };
178 
179  //inline because the implementation of non-template function in header file
180  inline Weighted::Weighted()
181  {
182  weight = 0.0;
183  }
184 
185  //inline because the implementation of non-template function in header file
186  inline Weighted::Weighted(const double weight)
187  {
188  this->weight = weight;
189  }
190 
191  //inline because the implementation of non-template function in header file
192  inline double Weighted::getWeight() const
193  {
194  return weight;
195  }
196 
197  //inline because the implementation of non-template function in header file
198  inline void Weighted::setWeight(const double weight)
199  {
200  this->weight = weight;
201  }
202 
203  template <typename T>
204  class Edge
205  {
206  private:
207  unsigned long id;
208  std::pair<const Node<T> *, const Node<T> *> nodePair;
209 
210  public:
211  Edge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
212  Edge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
213  virtual ~Edge() = default;
214  const unsigned long &getId() const;
215  const std::pair<const Node<T> *, const Node<T> *> &getNodePair() const;
216  virtual const std::optional<bool> isDirected() const;
217  virtual const std::optional<bool> isWeighted() const;
218  //operator
219  virtual bool operator==(const Edge<T> &b) const;
220  bool operator<(const Edge<T> &b) const;
221  //operator DirectedEdge<T>() const { return DirectedEdge<T>(id, nodePair); }
222  //operator UndirectedEdge<T>() const { return UndirectedEdge<T>(id, nodePair); }
223 
224  friend std::ostream &operator<<<>(std::ostream &os, const Edge<T> &edge);
225  };
226 
227  template <typename T>
228  Edge<T>::Edge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : nodePair(&node1, &node2)
229  {
230  this->id = id;
231  }
232 
233  template <typename T>
234  Edge<T>::Edge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : nodePair(nodepair)
235  {
236  this->id = id;
237  }
238 
239  template <typename T>
240  const unsigned long &Edge<T>::getId() const
241  {
242  return id;
243  }
244 
245  template <typename T>
246  const std::pair<const Node<T> *, const Node<T> *> &Edge<T>::getNodePair() const
247  {
248  return nodePair;
249  }
250 
251  template <typename T>
252  const std::optional<bool> Edge<T>::isDirected() const
253  {
254  return std::nullopt;
255  }
256 
257  template <typename T>
258  const std::optional<bool> Edge<T>::isWeighted() const
259  {
260  return std::nullopt;
261  }
262 
263  template <typename T>
264  bool Edge<T>::operator==(const Edge<T> &b) const
265  {
266  return (this->id == b.id && this->nodePair == b.nodePair);
267  }
268 
269  template <typename T>
270  bool Edge<T>::operator<(const Edge<T> &b) const
271  {
272  return (this->id < b.id);
273  }
274 
275  template <typename T>
276  class DirectedEdge : public Edge<T>
277  {
278  public:
279  DirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
280  DirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
281  DirectedEdge(const Edge<T> &edge);
282  virtual ~DirectedEdge() = default;
283  const Node<T> &getFrom() const;
284  const Node<T> &getTo() const;
285  const std::optional<bool> isDirected() const override;
286  virtual const std::optional<bool> isWeighted() const override;
287  //operator
288  explicit operator UndirectedEdge<T>() const { return UndirectedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair()); }
289 
290  friend std::ostream &operator<<<>(std::ostream &os, const DirectedEdge<T> &edge);
291  };
292 
293  template <typename T>
294  DirectedEdge<T>::DirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : Edge<T>(id, node1, node2)
295  {
296  }
297 
298  template <typename T>
299  DirectedEdge<T>::DirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
300  {
301  }
302 
303  template <typename T>
304  DirectedEdge<T>::DirectedEdge(const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
305  {
306  }
307 
308  template <typename T>
309  const Node<T> &DirectedEdge<T>::getFrom() const
310  {
311  return *(Edge<T>::getNodePair().first);
312  }
313 
314  template <typename T>
315  const Node<T> &DirectedEdge<T>::getTo() const
316  {
317  return *(Edge<T>::getNodePair().second);
318  }
319 
320  template <typename T>
321  const std::optional<bool> DirectedEdge<T>::isDirected() const
322  {
323  return true;
324  }
325 
326  template <typename T>
327  const std::optional<bool> DirectedEdge<T>::isWeighted() const
328  {
329  return false;
330  }
331 
332  template <typename T>
333  class UndirectedEdge : public Edge<T>
334  {
335  public:
336  UndirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
337  UndirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
338  UndirectedEdge(const Edge<T> &edge);
339  virtual ~UndirectedEdge() = default;
340  const Node<T> &getNode1() const;
341  const Node<T> &getNode2() const;
342  const std::optional<bool> isDirected() const override;
343  const std::optional<bool> isWeighted() const override;
344  //operator
345  explicit operator DirectedEdge<T>() const { return DirectedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair()); }
346 
347  friend std::ostream &operator<<<>(std::ostream &os, const UndirectedEdge<T> &edge);
348  };
349 
350  template <typename T>
351  UndirectedEdge<T>::UndirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : Edge<T>(id, node1, node2)
352  {
353  }
354 
355  template <typename T>
356  UndirectedEdge<T>::UndirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
357  {
358  }
359 
360  template <typename T>
361  UndirectedEdge<T>::UndirectedEdge(const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
362  {
363  }
364 
365  template <typename T>
366  const Node<T> &UndirectedEdge<T>::getNode1() const
367  {
368  return *(Edge<T>::getNodePair().first);
369  }
370 
371  template <typename T>
372  const Node<T> &UndirectedEdge<T>::getNode2() const
373  {
374  return *(Edge<T>::getNodePair().second);
375  }
376 
377  template <typename T>
378  const std::optional<bool> UndirectedEdge<T>::isDirected() const
379  {
380  return false;
381  }
382 
383  template <typename T>
384  const std::optional<bool> UndirectedEdge<T>::isWeighted() const
385  {
386  return false;
387  }
388 
389  template <typename T>
390  class DirectedWeightedEdge : public DirectedEdge<T>, public Weighted
391  {
392  public:
393  DirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight);
394  DirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight);
395  DirectedWeightedEdge(const DirectedEdge<T> &edge, const double weight);
396  DirectedWeightedEdge(const Edge<T> &edge, const double weight);
398  DirectedWeightedEdge(const Edge<T> &edge);
400  virtual ~DirectedWeightedEdge() = default;
401  const std::optional<bool> isWeighted() const override;
402  //operator
403  explicit operator UndirectedWeightedEdge<T>() const { return UndirectedWeightedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair(), Weighted::getWeight()); }
404 
405  friend std::ostream &operator<<<>(std::ostream &os, const DirectedWeightedEdge<T> &edge);
406  };
407 
408  template <typename T>
409  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)
410  {
411  }
412 
413  template <typename T>
414  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)
415  {
416  }
417 
418  template <typename T>
419  DirectedWeightedEdge<T>::DirectedWeightedEdge(const DirectedEdge<T> &edge, const double weight) : DirectedEdge<T>(edge), Weighted(weight)
420  {
421  }
422 
423  template <typename T>
424  DirectedWeightedEdge<T>::DirectedWeightedEdge(const Edge<T> &edge, const double weight) : DirectedEdge<T>(edge), Weighted(weight)
425  {
426  }
427 
428  template <typename T>
429  DirectedWeightedEdge<T>::DirectedWeightedEdge(const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
430  {
431  }
432 
433  template <typename T>
434  DirectedWeightedEdge<T>::DirectedWeightedEdge(const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
435  {
436  }
437 
438  template <typename T>
439  DirectedWeightedEdge<T>::DirectedWeightedEdge(const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
440  {
441  }
442 
443  template <typename T>
444  const std::optional<bool> DirectedWeightedEdge<T>::isWeighted() const
445  {
446  return true;
447  }
448 
449  template <typename T>
451  {
452  public:
453  UndirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight);
454  UndirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight);
455  UndirectedWeightedEdge(const UndirectedEdge<T> &edge, const double weight);
456  UndirectedWeightedEdge(const Edge<T> &edge, const double weight);
458  UndirectedWeightedEdge(const Edge<T> &edge);
460  virtual ~UndirectedWeightedEdge() = default;
461  const std::optional<bool> isWeighted() const override;
462  //operator
463  explicit operator DirectedWeightedEdge<T>() const { return DirectedWeightedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair(), Weighted::getWeight()); }
464 
465  friend std::ostream &operator<<<>(std::ostream &os, const UndirectedWeightedEdge<T> &edge);
466  };
467 
468  template <typename T>
469  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)
470  {
471  }
472 
473  template <typename T>
474  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)
475  {
476  }
477 
478  template <typename T>
479  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const UndirectedEdge<T> &edge, const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
480  {
481  }
482 
483  template <typename T>
484  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const Edge<T> &edge, const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
485  {
486  }
487 
488  template <typename T>
489  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
490  {
491  }
492 
493  template <typename T>
494  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
495  {
496  }
497 
498  template <typename T>
499  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
500  {
501  }
502 
503  template <typename T>
504  const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted() const
505  {
506  return true;
507  }
508 
509  template <typename T>
510  class Partition;
511  template <typename T>
512  class Graph
513  {
514  private:
515  std::list<const Edge<T> *> edgeSet;
516  void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const;
517  int writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
518  int readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
519  int writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
520  int readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
521  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);
522  void greedyPartition(PartitionMap<T> &partitionMap) const;
523 
524  public:
526  typedef enum E_InputOutputFormat
527  {
530  OUT_1,
531  OUT_2
533 
535  typedef enum E_PartitionAlgorithm
536  {
538  ALG_1,
539  ALG_2
541 
542  Graph() = default;
543  Graph(const std::list<const Edge<T> *> &edgeSet);
544  ~Graph() = default;
545  const std::list<const Edge<T> *> &getEdgeSet() const;
546  void setEdgeSet(std::list<const Edge<T> *> &edgeSet);
547  void addEdge(const Edge<T> *edge);
548  void removeEdge(unsigned long edgeId);
549  const std::list<const Node<T> *> getNodeSet() const;
550  const std::optional<const Edge<T> *> getEdge(unsigned long edgeId) const;
555  const AdjacencyMatrix<T> getAdjMatrix() const;
567  const DijkstraResult dijkstra(const Node<T> &source, const Node<T> &target) const;
577  const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const;
587  const std::vector<Node<T>> depth_first_search(const Node<T> &start) const;
588 
596  bool isCyclicDirectedGraphDFS() const;
597 
605  bool isCyclicDirectedGraphBFS() const;
606 
613  bool isDirectedGraph() const;
614 
627  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;
628 
641  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);
642 
651  PartitionMap<T> partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const;
652 
653  friend std::ostream &operator<<<>(std::ostream &os, const Graph<T> &graph);
654  friend std::ostream &operator<<<>(std::ostream &os, const AdjacencyMatrix<T> &adj);
655  };
656 
657  template <typename T>
658  Graph<T>::Graph(const std::list<const Edge<T> *> &edgeSet)
659  {
660  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
661  {
662  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
663  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
664  {
665  this->edgeSet.push_back(*edgeSetIt);
666  }
667  }
668  }
669 
670  template <typename T>
671  const std::list<const Edge<T> *> &Graph<T>::getEdgeSet() const
672  {
673  return edgeSet;
674  }
675 
676  template <typename T>
677  void Graph<T>::setEdgeSet(std::list<const Edge<T> *> &edgeSet)
678  {
679  this->edgeSet.clear();
680  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
681  {
682  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
683  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
684  {
685  this->edgeSet.push_back(*edgeSetIt);
686  }
687  }
688  }
689 
690  template <typename T>
691  void Graph<T>::addEdge(const Edge<T> *edge)
692  {
693  if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](const Edge<T> *edge_a)
694  { return (*edge == *edge_a); }) == edgeSet.end())
695  {
696  edgeSet.push_back(edge);
697  }
698  }
699 
700  template <typename T>
701  void Graph<T>::removeEdge(unsigned long edgeId)
702  {
703  auto edgeOpt = getEdge(edgeId);
704  if (edgeOpt.has_value())
705  {
706  edgeSet.erase(edgeSet.find(edgeOpt.value()));
707  }
708  }
709 
710  template <typename T>
711  const std::list<const Node<T> *> Graph<T>::getNodeSet() const
712  {
713  std::list<const Node<T> *> nodeSet;
714  for (auto edge : edgeSet)
715  {
716  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
717  { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
718  {
719  nodeSet.push_back(edge->getNodePair().first);
720  }
721  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
722  { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
723  {
724  nodeSet.push_back(edge->getNodePair().second);
725  }
726  }
727  return nodeSet;
728  }
729 
730  template <typename T>
731  const std::optional<const Edge<T> *> Graph<T>::getEdge(unsigned long edgeId) const
732  {
733 
734  auto it = edgeSet.begin();
735  for (it; it != edgeSet.end(); ++it)
736  {
737  if ((*it)->getId() == edgeId)
738  {
739  return *it;
740  }
741  }
742 
743  return std::nullopt;
744  }
745 
746  template <typename T>
747  void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const
748  {
749  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
750  adjMatrix[nodeFrom].push_back(elem);
751 
752  //adjMatrix[nodeFrom.getId()].push_back(std::make_pair<const Node<T>,const Edge<T>>(nodeTo, edge));
753  }
754 
755  template <typename T>
756  int Graph<T>::writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
757  {
758  std::ofstream ofileGraph;
759  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
760  ofileGraph.open(completePathToFileGraph);
761  if (!ofileGraph.is_open())
762  {
763  // ERROR File Not Open
764  return -1;
765  }
766  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
767  { ofileGraph << e->getId() << "," << e->getNodePair().first->getId() << "," << e->getNodePair().second->getId() << "," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
768  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
769  ofileGraph.close();
770 
771  if (writeNodeFeat)
772  {
773  std::ofstream ofileNodeFeat;
774  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
775  ".csv";
776  ofileNodeFeat.open(completePathToFileNodeFeat);
777  if (!ofileNodeFeat.is_open())
778  {
779  // ERROR File Not Open
780  return -1;
781  }
782  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
783  { ofileNodeFeat << node->getId() << "," << node->getData() << std::endl; };
784  auto nodeSet = getNodeSet();
785  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
786  ofileNodeFeat.close();
787  }
788 
789  if (writeEdgeWeight)
790  {
791  std::ofstream ofileEdgeWeight;
792  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
793  ".csv";
794  ofileEdgeWeight.open(completePathToFileEdgeWeight);
795  if (!ofileEdgeWeight.is_open())
796  {
797  // ERROR File Not Open
798  return -1;
799  }
800  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
801  { 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; };
802 
803  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
804  ofileEdgeWeight.close();
805  }
806  return 0;
807  }
808 
809  template <typename T>
810  int Graph<T>::readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
811  {
812  std::ifstream ifileGraph;
813  std::ifstream ifileNodeFeat;
814  std::ifstream ifileEdgeWeight;
815  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
816  std::map<unsigned long, bool> edgeDirectedMap;
817  std::map<unsigned long, T> nodeFeatMap;
818  std::map<unsigned long, double> edgeWeightMap;
819  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
820  ifileGraph.open(completePathToFileGraph);
821  if (!ifileGraph.is_open())
822  {
823  // ERROR File Not Open
824  return -1;
825  }
826  char comma;
827  for (;;)
828  { /* loop continually */
829  unsigned long edgeId;
830  unsigned long nodeId1;
831  unsigned long nodeId2;
832  bool directed;
833  ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
834  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
835  edgeDirectedMap[edgeId] = directed;
836  if (ifileGraph.fail() || ifileGraph.eof())
837  break;
838  ifileGraph.ignore(128, '\n');
839  }
840  ifileGraph.close();
841 
842  if (readNodeFeat)
843  {
844  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
845  ".csv";
846  ifileNodeFeat.open(completePathToFileNodeFeat);
847  if (!ifileNodeFeat.is_open())
848  {
849  // ERROR File Not Open
850  return -1;
851  }
852  for (;;)
853  { /* loop continually */
854  unsigned long nodeId;
855  T nodeFeat;
856  ifileNodeFeat >> nodeId >> comma >> nodeFeat;
857  nodeFeatMap[nodeId] = nodeFeat;
858  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
859  break;
860  ifileNodeFeat.ignore(128, '\n');
861  }
862  ifileNodeFeat.close();
863  }
864 
865  if (readEdgeWeight)
866  {
867 
868  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
869  ".csv";
870  ifileEdgeWeight.open(completePathToFileEdgeWeight);
871  if (!ifileEdgeWeight.is_open())
872  {
873  // ERROR File Not Open
874  return -1;
875  }
876  for (;;)
877  { /* loop continually */
878  unsigned long edgeId;
879  double weight;
880  bool weighted;
881  ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
882  if (weighted)
883  {
884  edgeWeightMap[edgeId] = weight;
885  }
886  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
887  break;
888  ifileEdgeWeight.ignore(128, '\n');
889  }
890  ifileEdgeWeight.close();
891  }
892  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
893  return 0;
894  }
895 
896  template <typename T>
897  int Graph<T>::writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
898  {
899  std::ofstream ofileGraph;
900  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
901  ofileGraph.open(completePathToFileGraph);
902  if (!ofileGraph.is_open())
903  {
904  // ERROR File Not Open
905  return -1;
906  }
907  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
908  { 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; };
909  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
910  ofileGraph.close();
911 
912  if (writeNodeFeat)
913  {
914  std::ofstream ofileNodeFeat;
915  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
916  ".tsv";
917  ofileNodeFeat.open(completePathToFileNodeFeat);
918  if (!ofileNodeFeat.is_open())
919  {
920  // ERROR File Not Open
921  return -1;
922  }
923  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
924  { ofileNodeFeat << node->getId() << "\t" << node->getData() << std::endl; };
925  auto nodeSet = getNodeSet();
926  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
927  ofileNodeFeat.close();
928  }
929 
930  if (writeEdgeWeight)
931  {
932  std::ofstream ofileEdgeWeight;
933  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
934  ".tsv";
935  ofileEdgeWeight.open(completePathToFileEdgeWeight);
936  if (!ofileEdgeWeight.is_open())
937  {
938  // ERROR File Not Open
939  return -1;
940  }
941  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
942  { 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; };
943 
944  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
945  ofileEdgeWeight.close();
946  }
947  return 0;
948  }
949 
950  template <typename T>
951  int Graph<T>::readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
952  {
953  std::ifstream ifileGraph;
954  std::ifstream ifileNodeFeat;
955  std::ifstream ifileEdgeWeight;
956  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
957  std::map<unsigned long, bool> edgeDirectedMap;
958  std::map<unsigned long, T> nodeFeatMap;
959  std::map<unsigned long, double> edgeWeightMap;
960  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
961  ifileGraph.open(completePathToFileGraph);
962  if (!ifileGraph.is_open())
963  {
964  // ERROR File Not Open
965  return -1;
966  }
967  for (;;)
968  { /* loop continually */
969  unsigned long edgeId;
970  unsigned long nodeId1;
971  unsigned long nodeId2;
972  bool directed;
973  ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
974  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
975  edgeDirectedMap[edgeId] = directed;
976  if (ifileGraph.fail() || ifileGraph.eof())
977  break;
978  ifileGraph.ignore(128, '\n');
979  }
980  ifileGraph.close();
981 
982  if (readNodeFeat)
983  {
984  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
985  ".tsv";
986  ifileNodeFeat.open(completePathToFileNodeFeat);
987  if (!ifileNodeFeat.is_open())
988  {
989  // ERROR File Not Open
990  return -1;
991  }
992  for (;;)
993  { /* loop continually */
994  unsigned long nodeId;
995  T nodeFeat;
996  ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
997  nodeFeatMap[nodeId] = nodeFeat;
998  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
999  break;
1000  ifileNodeFeat.ignore(128, '\n');
1001  }
1002  ifileNodeFeat.close();
1003  }
1004 
1005  if (readEdgeWeight)
1006  {
1007 
1008  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
1009  ".tsv";
1010  ifileEdgeWeight.open(completePathToFileEdgeWeight);
1011  if (!ifileEdgeWeight.is_open())
1012  {
1013  // ERROR File Not Open
1014  return -1;
1015  }
1016  for (;;)
1017  { /* loop continually */
1018  unsigned long edgeId;
1019  double weight;
1020  bool weighted;
1021  ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
1022  if (weighted)
1023  {
1024  edgeWeightMap[edgeId] = weight;
1025  }
1026  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
1027  break;
1028  ifileEdgeWeight.ignore(128, '\n');
1029  }
1030  ifileEdgeWeight.close();
1031  }
1032  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
1033  return 0;
1034  }
1035 
1036  template <typename T>
1037  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)
1038  {
1039  std::map<unsigned long, Node<T> *> nodeMap;
1040  for (auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
1041  {
1042  Node<T> *node1 = nullptr;
1043  Node<T> *node2 = nullptr;
1044  if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
1045  {
1046  //Create new Node
1047  T feat;
1048  if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
1049  {
1050  feat = nodeFeatMap.at(edgeIt->second.first);
1051  }
1052  node1 = new Node<T>(edgeIt->second.first, feat);
1053  nodeMap[edgeIt->second.first] = node1;
1054  }
1055  else
1056  {
1057  node1 = nodeMap.at(edgeIt->second.first);
1058  }
1059  if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
1060  {
1061  //Create new Node
1062  T feat;
1063  if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
1064  {
1065  feat = nodeFeatMap.at(edgeIt->second.second);
1066  }
1067  node2 = new Node<T>(edgeIt->second.second, feat);
1068  nodeMap[edgeIt->second.second] = node2;
1069  }
1070  else
1071  {
1072  node2 = nodeMap.at(edgeIt->second.second);
1073  }
1074 
1075  if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
1076  {
1077  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1078  {
1079  auto edge = new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1080  addEdge(edge);
1081  }
1082  else
1083  {
1084  auto edge = new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1085  addEdge(edge);
1086  }
1087  }
1088  else
1089  {
1090  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1091  {
1092  auto edge = new DirectedEdge<T>(edgeIt->first, *node1, *node2);
1093  addEdge(edge);
1094  }
1095  else
1096  {
1097  auto edge = new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
1098  addEdge(edge);
1099  }
1100  }
1101  }
1102  }
1103 
1104  template <typename T>
1105  void Graph<T>::greedyPartition(PartitionMap<T> &partitionMap) const
1106  {
1107  unsigned int index = 0;
1108  unsigned int numberOfPartitions = partitionMap.size();
1109  if (index == numberOfPartitions)
1110  {
1111  //ERROR partition map of zero element
1112  return;
1113  }
1114  auto edgeSet = getEdgeSet();
1115  for (auto edge : edgeSet)
1116  {
1117  partitionMap.at(index)->addEdge(edge);
1118  index++;
1119  index = index % numberOfPartitions;
1120  }
1121  }
1122 
1123  template <typename T>
1124  const AdjacencyMatrix<T> Graph<T>::getAdjMatrix() const
1125  {
1126  AdjacencyMatrix<T> adj;
1127  auto edgeSetIt = edgeSet.begin();
1128  for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
1129  {
1130  if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
1131  {
1132  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(*edgeSetIt);
1133  addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
1134  }
1135  else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
1136  {
1137  const UndirectedEdge<T> *ud_edge = dynamic_cast<const UndirectedEdge<T> *>(*edgeSetIt);
1138  ;
1139  addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
1140  addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
1141  }
1142  else
1143  { //is a simple edge we cannot create adj matrix
1144  return adj;
1145  }
1146  }
1147  return adj;
1148  }
1149 
1150  template <typename T>
1151  const DijkstraResult Graph<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
1152  {
1153  DijkstraResult result;
1154  result.success = false;
1155  result.errorMessage = "";
1156  result.result = INF_DOUBLE;
1157  auto nodeSet = getNodeSet();
1158  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1159  {
1160  // check if source node exist in the graph
1161  result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
1162  return result;
1163  }
1164  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1165  {
1166  // check if target node exist in the graph
1167  result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
1168  return result;
1169  }
1170  const AdjacencyMatrix<T> adj = getAdjMatrix();
1171  // n denotes the number of vertices in graph
1172  int n = adj.size();
1173 
1174  // setting all the distances initially to INF_DOUBLE
1175  std::map<const Node<T> *, double> dist;
1176 
1177  for (auto elem : adj)
1178  {
1179  dist[elem.first] = INF_DOUBLE;
1180  }
1181 
1182  // creating a min heap using priority queue
1183  // first element of pair contains the distance
1184  // second element of pair contains the vertex
1185  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1186  std::greater<std::pair<double, const Node<T> *>>>
1187  pq;
1188 
1189  // pushing the source vertex 's' with 0 distance in min heap
1190  pq.push(std::make_pair(0.0, &source));
1191 
1192  // marking the distance of source as 0
1193  dist[&source] = 0;
1194 
1195  while (!pq.empty())
1196  {
1197  // second element of pair denotes the node / vertex
1198  const Node<T> *currentNode = pq.top().second;
1199 
1200  // first element of pair denotes the distance
1201  double currentDist = pq.top().first;
1202 
1203  pq.pop();
1204 
1205  // for all the reachable vertex from the currently exploring vertex
1206  // we will try to minimize the distance
1207  if (adj.find(currentNode) != adj.end())
1208  {
1209  for (std::pair<const Node<T> *, const Edge<T> *> elem : adj.at(currentNode))
1210  {
1211  // minimizing distances
1212  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1213  {
1214  if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1215  {
1216  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(elem.second);
1217  if (currentDist + dw_edge->getWeight() < dist[elem.first])
1218  {
1219  dist[elem.first] = currentDist + dw_edge->getWeight();
1220  pq.push(std::make_pair(dist[elem.first], elem.first));
1221  }
1222  }
1223  else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1224  {
1225  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
1226  if (currentDist + udw_edge->getWeight() < dist[elem.first])
1227  {
1228  dist[elem.first] = currentDist + udw_edge->getWeight();
1229  pq.push(std::make_pair(dist[elem.first], elem.first));
1230  }
1231  }
1232  else
1233  {
1234  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
1235  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1236  return result;
1237  }
1238  }
1239  else
1240  {
1241  // No Weighted Edge
1242  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1243  return result;
1244  }
1245  }
1246  }
1247  }
1248  if (dist[&target] != INF_DOUBLE)
1249  {
1250  result.success = true;
1251  result.errorMessage = "";
1252  result.result = dist[&target];
1253  return result;
1254  }
1255  result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
1256  result.result = -1;
1257  return result;
1258  }
1259 
1260  template <typename T>
1261  const std::vector<Node<T>> Graph<T>::breadth_first_search(const Node<T> &start) const
1262  {
1263  // vector to keep track of visited nodes
1264  std::vector<Node<T>> visited;
1265  auto nodeSet = getNodeSet();
1266  //check is exist node in the graph
1267  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1268  {
1269  return visited;
1270  }
1271  const AdjacencyMatrix<T> adj = getAdjMatrix();
1272  // queue that stores vertices that need to be further explored
1273  std::queue<const Node<T> *> tracker;
1274 
1275  // mark the starting node as visited
1276  visited.push_back(start);
1277  tracker.push(&start);
1278  while (!tracker.empty())
1279  {
1280  const Node<T> *node = tracker.front();
1281  tracker.pop();
1282  if (adj.find(node) != adj.end())
1283  {
1284  for (auto elem : adj.at(node))
1285  {
1286  // if the node is not visited then mark it as visited
1287  // and push it to the queue
1288  if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1289  {
1290  visited.push_back(*(elem.first));
1291  tracker.push(elem.first);
1292  }
1293  }
1294  }
1295  }
1296 
1297  return visited;
1298  }
1299 
1300  template <typename T>
1301  const std::vector<Node<T>> Graph<T>::depth_first_search(const Node<T> &start) const
1302  {
1303  // vector to keep track of visited nodes
1304  std::vector<Node<T>> visited;
1305  auto nodeSet = getNodeSet();
1306  //check is exist node in the graph
1307  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1308  {
1309  return visited;
1310  }
1311  const AdjacencyMatrix<T> adj = getAdjMatrix();
1312  std::function<void(const AdjacencyMatrix<T> &, const Node<T> &, std::vector<Node<T>> &)> explore;
1313  explore = [&explore](const AdjacencyMatrix<T> &adj, const Node<T> &node, std::vector<Node<T>> &visited) -> void
1314  {
1315  visited.push_back(node);
1316  if (adj.find(&node) != adj.end())
1317  {
1318  for (auto x : adj.at(&node))
1319  {
1320  if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1321  {
1322  explore(adj, *(x.first), visited);
1323  }
1324  }
1325  }
1326  };
1327  explore(adj, start, visited);
1328 
1329  return visited;
1330  }
1331 
1332  template <typename T>
1334  {
1335  if (!isDirectedGraph())
1336  {
1337  return false;
1338  }
1339  enum nodeStates : uint8_t
1340  {
1341  not_visited,
1342  in_stack,
1343  visited
1344  };
1345  auto nodeSet = this->getNodeSet();
1346  auto adjMatrix = this->getAdjMatrix();
1347 
1348  /* State of the node.
1349  *
1350  * It is a vector of "nodeStates" which represents the state node is in.
1351  * It can take only 3 values: "not_visited", "in_stack", and "visited".
1352  *
1353  * Initially, all nodes are in "not_visited" state.
1354  */
1355  std::map<unsigned long, nodeStates> state;
1356  for (auto node : nodeSet)
1357  {
1358  state[node->getId()] = not_visited;
1359  }
1360  int stateCounter = 0;
1361 
1362  // Start visiting each node.
1363  for (auto node : nodeSet)
1364  {
1365  // If a node is not visited, only then check for presence of cycle.
1366  // There is no need to check for presence of cycle for a visited
1367  // node as it has already been checked for presence of cycle.
1368  if (state[node->getId()] == not_visited)
1369  {
1370  // Check for cycle.
1371  std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &, const Node<T> *)> isCyclicDFSHelper;
1372  isCyclicDFSHelper = [this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states, const Node<T> *node)
1373  {
1374  // Add node "in_stack" state.
1375  states[node->getId()] = in_stack;
1376 
1377  // If the node has children, then recursively visit all children of the
1378  // node.
1379  auto const it = adjMatrix.find(node);
1380  if (it != adjMatrix.end())
1381  {
1382  for (auto child : it->second)
1383  {
1384  // If state of child node is "not_visited", evaluate that child
1385  // for presence of cycle.
1386  auto state_of_child = states.at((std::get<0>(child))->getId());
1387  if (state_of_child == not_visited)
1388  {
1389  if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1390  {
1391  return true;
1392  }
1393  }
1394  else if (state_of_child == in_stack)
1395  {
1396  // If child node was "in_stack", then that means that there
1397  // is a cycle in the graph. Return true for presence of the
1398  // cycle.
1399  return true;
1400  }
1401  }
1402  }
1403 
1404  // Current node has been evaluated for the presence of cycle and had no
1405  // cycle. Mark current node as "visited".
1406  states[node->getId()] = visited;
1407  // Return that current node didn't result in any cycles.
1408  return false;
1409  };
1410  if (isCyclicDFSHelper(adjMatrix, state, node))
1411  {
1412  return true;
1413  }
1414  }
1415  }
1416 
1417  // All nodes have been safely traversed, that means there is no cycle in
1418  // the graph. Return false.
1419  return false;
1420  }
1421 
1422  template <typename T>
1424  {
1425  if (!isDirectedGraph())
1426  {
1427  return false;
1428  }
1429  auto adjMatrix = this->getAdjMatrix();
1430  auto nodeSet = this->getNodeSet();
1431 
1432  std::map<unsigned long, unsigned int> indegree;
1433  for (auto node : nodeSet)
1434  {
1435  indegree[node->getId()] = 0;
1436  }
1437  // Calculate the indegree i.e. the number of incident edges to the node.
1438  for (auto const &list : adjMatrix)
1439  {
1440  auto children = list.second;
1441  for (auto const &child : children)
1442  {
1443  indegree[std::get<0>(child)->getId()]++;
1444  }
1445  }
1446 
1447  std::queue<const Node<T> *> can_be_solved;
1448  for (auto node : nodeSet)
1449  {
1450  // If a node doesn't have any input edges, then that node will
1451  // definately not result in a cycle and can be visited safely.
1452  if (!indegree[node->getId()])
1453  {
1454  can_be_solved.emplace(&(*node));
1455  }
1456  }
1457 
1458  // Vertices that need to be traversed.
1459  auto remain = this->getNodeSet().size();
1460  // While there are safe nodes that we can visit.
1461  while (!can_be_solved.empty())
1462  {
1463  auto solved = can_be_solved.front();
1464  // Visit the node.
1465  can_be_solved.pop();
1466  // Decrease number of nodes that need to be traversed.
1467  remain--;
1468 
1469  // Visit all the children of the visited node.
1470  auto it = adjMatrix.find(solved);
1471  if (it != adjMatrix.end())
1472  {
1473  for (auto child : it->second)
1474  {
1475  // Check if we can visited the node safely.
1476  if (--indegree[std::get<0>(child)->getId()] == 0)
1477  {
1478  // if node can be visited safely, then add that node to
1479  // the visit queue.
1480  can_be_solved.emplace(std::get<0>(child));
1481  }
1482  }
1483  }
1484  }
1485 
1486  // If there are still nodes that we can't visit, then it means that
1487  // there is a cycle and return true, else return false.
1488  return !(remain == 0);
1489  }
1490 
1491  template <typename T>
1493  {
1494  auto edgeSet = this->getEdgeSet();
1495  for (auto edge : edgeSet)
1496  {
1497  if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1498  {
1499  //Found Undirected Edge
1500  return false;
1501  }
1502  }
1503  //No Undirected Edge
1504  return true;
1505  }
1506 
1507  template <typename T>
1508  int Graph<T>::writeToFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
1509  {
1510  if (format == InputOutputFormat::STANDARD_CSV)
1511  {
1512  return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1513  }
1514  else if (format == InputOutputFormat::STANDARD_TSV)
1515  {
1516  return writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1517  }
1518  else
1519  {
1520  //OUTPUT FORMAT NOT RECOGNIZED
1521  return -1;
1522  }
1523  }
1524 
1525  template <typename T>
1526  int Graph<T>::readFromFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
1527  {
1528  if (format == InputOutputFormat::STANDARD_CSV)
1529  {
1530  return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1531  }
1532  else if (format == InputOutputFormat::STANDARD_TSV)
1533  {
1534  return readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1535  }
1536  else
1537  {
1538  //OUTPUT FORMAT NOT RECOGNIZED
1539  return -1;
1540  }
1541  }
1542 
1543  template <typename T>
1544  PartitionMap<T> Graph<T>::partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
1545  {
1546  PartitionMap<T> partitionMap;
1547  for (unsigned int i = 0; i < numberOfPartitions; ++i)
1548  {
1549  partitionMap[i] = new Partition<T>(i);
1550  }
1551  if (algorithm == PartitionAlgorithm::GREEDY_VC)
1552  {
1553  greedyPartition(partitionMap);
1554  }
1555  else
1556  {
1557  //Error not recognized algorithm
1558  partitionMap.clear();
1559  }
1560  return partitionMap;
1561  }
1562 
1563  template <typename T>
1564  class Partition : public Graph<T>
1565  {
1566  public:
1567  Partition();
1568  Partition(unsigned int partitionId);
1569  Partition(const std::list<const Edge<T> *> &edgeSet);
1570  Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet);
1571  ~Partition() = default;
1577  unsigned int getPartitionId() const;
1583  void setPartitionId(unsigned int partitionId);
1584 
1585  private:
1586  unsigned int partitionId;
1587  };
1588 
1596  template <typename T>
1597  static PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap);
1598 
1606  template <typename T>
1607  static unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap);
1608 
1616  template <typename T>
1617  static unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap);
1618 
1626  template <typename T>
1627  static unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap);
1628 
1636  template <typename T>
1637  static unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap);
1638 
1646  template <typename T>
1647  static unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap);
1648 
1656  template <typename T>
1657  static unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap);
1658 
1666  template <typename T>
1667  static unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap);
1668 
1676  template <typename T>
1677  static unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap);
1678 
1679  template <typename T>
1681  {
1682  partitionId = 0;
1683  }
1684 
1685  template <typename T>
1686  Partition<T>::Partition(unsigned int partitionId) : Graph<T>()
1687  {
1688  this->partitionId = partitionId;
1689  }
1690 
1691  template <typename T>
1692  Partition<T>::Partition(const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
1693  {
1694  partitionId = 0;
1695  }
1696 
1697  template <typename T>
1698  Partition<T>::Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
1699  {
1700  this->partitionId = partitionId;
1701  }
1702 
1703  template <typename T>
1704  unsigned int Partition<T>::getPartitionId() const
1705  {
1706  return partitionId;
1707  }
1708 
1709  template <typename T>
1710  void Partition<T>::setPartitionId(unsigned int partitionId)
1711  {
1712  this->partitionId = partitionId;
1713  }
1714 
1715  template <typename T>
1716  PartitioningStats getPartitionStats(const PartitionMap<T> &partitionMap)
1717  {
1718  PartitioningStats result;
1719  result.numberOfPartitions = partitionMap.size();
1720  result.numberOfNodes = getNumberOfNodes(partitionMap);
1721  result.numberOfEdges = getNumberOfEdges(partitionMap);
1722  result.replicatedNodesCount = getNumberOfReplicatedNodes(partitionMap);
1723  result.replicatedEdgesCount = getNumberOfReplicatedEdges(partitionMap);
1724  result.maxEdgesLoad = getMaxEdgesLoad(partitionMap);
1725  result.minEdgesLoad = getMinEdgesLoad(partitionMap);
1726  result.maxNodesLoad = getMaxNodesLoad(partitionMap);
1727  result.minNodesLoad = getMinNodesLoad(partitionMap);
1728  result.edgesReplicationFactor = (double)result.replicatedEdgesCount / result.numberOfEdges;
1729  result.nodesReplicationFactor = (double)result.replicatedNodesCount / result.numberOfNodes;
1730  result.balanceEdgesFactor = (double)(result.maxEdgesLoad - result.minEdgesLoad) / (result.maxEdgesLoad);
1731  result.balanceNodesFactor = (double)(result.maxNodesLoad - result.minNodesLoad) / (result.maxNodesLoad);
1732  return result;
1733  }
1734 
1735  template <typename T>
1736  unsigned int getMaxEdgesLoad(const PartitionMap<T> &partitionMap)
1737  {
1738  unsigned int maxLoad = 0;
1739  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1740  {
1741  if (it->second->getEdgeSet().size() > maxLoad)
1742  {
1743  maxLoad = it->second->getEdgeSet().size();
1744  }
1745  }
1746  return maxLoad;
1747  }
1748 
1749  template <typename T>
1750  unsigned int getMinEdgesLoad(const PartitionMap<T> &partitionMap)
1751  {
1752  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
1753  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1754  {
1755  if (it->second->getEdgeSet().size() < minLoad)
1756  {
1757  minLoad = it->second->getEdgeSet().size();
1758  }
1759  }
1760  return minLoad;
1761  }
1762 
1763  template <typename T>
1764  unsigned int getMaxNodesLoad(const PartitionMap<T> &partitionMap)
1765  {
1766  unsigned int maxLoad = 0;
1767  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1768  {
1769  if (it->second->getNodeSet().size() > maxLoad)
1770  {
1771  maxLoad = it->second->getNodeSet().size();
1772  }
1773  }
1774  return maxLoad;
1775  }
1776 
1777  template <typename T>
1778  unsigned int getMinNodesLoad(const PartitionMap<T> &partitionMap)
1779  {
1780  unsigned int minLoad = std::numeric_limits<unsigned int>::max();
1781  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1782  {
1783  if (it->second->getNodeSet().size() < minLoad)
1784  {
1785  minLoad = it->second->getNodeSet().size();
1786  }
1787  }
1788  return minLoad;
1789  }
1790 
1791  template <typename T>
1792  unsigned int getNumberOfEdges(const PartitionMap<T> &partitionMap)
1793  {
1794  unsigned int numberOfEdges = 0;
1795  std::list<const Edge<T> *> edgeSet;
1796 
1797  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1798  {
1799  const std::list<const Edge<T> *> partitionEdgeSet = it->second->getEdgeSet();
1800  for (auto it2 = partitionEdgeSet.begin(); it2 != partitionEdgeSet.end(); ++it2)
1801  {
1802  if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](const Edge<T> *edge)
1803  { return (*(*it2) == *edge); }) == edgeSet.end())
1804  {
1805  edgeSet.push_back(*it2);
1806  }
1807  }
1808  }
1809 
1810  return edgeSet.size();
1811  }
1812 
1813  template <typename T>
1814  unsigned int getNumberOfNodes(const PartitionMap<T> &partitionMap)
1815  {
1816 
1817  unsigned int numberOfNodes = 0;
1818  std::list<const Node<T> *> nodeSet;
1819 
1820  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1821  {
1822  const std::list<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
1823  for (auto it2 = partitionNodeSet.begin(); it2 != partitionNodeSet.end(); ++it2)
1824  {
1825  if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](const Node<T> *node)
1826  { return (*(*it2) == *node); }) == nodeSet.end())
1827  {
1828  nodeSet.push_back(*it2);
1829  }
1830  }
1831  }
1832 
1833  return nodeSet.size();
1834  }
1835 
1836  template <typename T>
1837  unsigned int getNumberOfReplicatedEdges(const PartitionMap<T> &partitionMap)
1838  {
1839 
1840  unsigned int numberOfEdges = 0;
1841  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1842  {
1843  numberOfEdges += it->second->getEdgeSet().size();
1844  }
1845  return numberOfEdges;
1846  }
1847 
1848  template <typename T>
1849  unsigned int getNumberOfReplicatedNodes(const PartitionMap<T> &partitionMap)
1850  {
1851  unsigned int numberOfNodes = 0;
1852  for (auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1853  {
1854  numberOfNodes += it->second->getNodeSet().size();
1855  }
1856  return numberOfNodes;
1857  }
1858 
1859  //ostream overload
1860  template <typename T>
1861  std::ostream &operator<<(std::ostream &os, const Node<T> &node)
1862  {
1863  os << "Node: {\n"
1864  << " Id:\t" << node.id << "\n Data:\t" << node.data << "\n}";
1865  return os;
1866  }
1867 
1868  template <typename T>
1869  std::ostream &operator<<(std::ostream &os, const Edge<T> &edge)
1870  {
1871  os << "((Node: " << edge.nodePair.first->getId() << ")) ?----- |Edge: " << edge.id << "|-----? ((Node: " << edge.nodePair.second->getId() << "))";
1872  return os;
1873  }
1874 
1875  template <typename T>
1876  std::ostream &operator<<(std::ostream &os, const DirectedEdge<T> &edge)
1877  {
1878  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getTo().getId() << "))";
1879  return os;
1880  }
1881 
1882  template <typename T>
1883  std::ostream &operator<<(std::ostream &os, const UndirectedEdge<T> &edge)
1884  {
1885  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
1886  return os;
1887  }
1888 
1889  template <typename T>
1890  std::ostream &operator<<(std::ostream &os, const DirectedWeightedEdge<T> &edge)
1891  {
1892  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getTo().getId() << "))";
1893  return os;
1894  }
1895 
1896  template <typename T>
1897  std::ostream &operator<<(std::ostream &os, const UndirectedWeightedEdge<T> &edge)
1898  {
1899  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
1900  return os;
1901  }
1902 
1903  template <typename T>
1904  std::ostream &operator<<(std::ostream &os, const AdjacencyMatrix<T> &adj)
1905  {
1906  os << "Adjacency Matrix:\n";
1907  auto it = adj.begin();
1908  unsigned long max_column = 0;
1909  for (it; it != adj.end(); ++it)
1910  {
1911  if (it->second.size() > max_column)
1912  {
1913  max_column = it->second.size();
1914  }
1915  }
1916  if (max_column == 0)
1917  {
1918  os << "ERROR in Print\n";
1919  return os;
1920  }
1921  else
1922  {
1923  it = adj.begin();
1924  os << "|--|";
1925  for (int i = 0; i < max_column; i++)
1926  {
1927  os << "-----|";
1928  }
1929  os << "\n";
1930  for (it; it != adj.end(); ++it)
1931  {
1932  os << "|N" << it->first->getId() << "|";
1933  auto it2 = it->second.begin();
1934  for (it2; it2 != it->second.end(); ++it2)
1935  {
1936  os << "N" << it2->first->getId() << ",E" << it2->second->getId() << "|";
1937  }
1938  os << "\n|--|";
1939  for (int i = 0; i < max_column; i++)
1940  {
1941  os << "-----|";
1942  }
1943  os << "\n";
1944  }
1945  }
1946  return os;
1947  }
1948 
1949 } // namespace CXXGRAPH
1950 #endif // __CXXGRAPH_H__
Definition: Graph.hpp:277
Definition: Graph.hpp:391
Definition: Graph.hpp:205
Definition: Graph.hpp:513
const std::vector< Node< T > > depth_first_search(const Node< T > &start) const
Function performs the depth first search algorithm over the graph.
Definition: Graph.hpp:1301
E_PartitionAlgorithm
Specify the Partition Algorithm.
Definition: Graph.hpp:536
@ GREEDY_VC
A Greedy Vertex-Cut Algorithm.
Definition: Graph.hpp:537
enum CXXGRAPH::Graph::E_PartitionAlgorithm PartitionAlgorithm
Specify the Partition Algorithm.
enum CXXGRAPH::Graph::E_InputOutputFormat InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
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:1423
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
This function write the graph in an output file.
Definition: Graph.hpp:1508
bool isDirectedGraph() const
This function checks if a graph is directed.
Definition: Graph.hpp:1492
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:1151
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:1333
PartitionMap< T > partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
This function partition a graph in a set of partitions.
Definition: Graph.hpp:1544
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.
Definition: Graph.hpp:1526
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:1124
const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const
Function performs the breadth first search algorithm over the graph.
Definition: Graph.hpp:1261
E_InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
Definition: Graph.hpp:527
@ STANDARD_CSV
A standard csv format.
Definition: Graph.hpp:528
@ STANDARD_TSV
A standard tsv format.
Definition: Graph.hpp:529
Definition: Graph.hpp:119
Definition: Graph.hpp:1565
void setPartitionId(unsigned int partitionId)
Set the Partition ID.
Definition: Graph.hpp:1710
unsigned int getPartitionId() const
Get the Partition ID.
Definition: Graph.hpp:1704
Definition: Graph.hpp:334
Definition: Graph.hpp:451
Definition: Graph.hpp:167
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Graph.hpp:50
Struct that contains the information about the partitioning statistics.
Definition: Graph.hpp:59