CXXGraph  0.1.2
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 
18 namespace CXXGRAPH
19 {
20  //STRING ERROR CONST EXPRESSION
21  constexpr char ERR_NO_DIR_OR_UNDIR_EDGE[] = "Edge are neither Directed neither Undirected";
22  constexpr char ERR_NO_WEIGHTED_EDGE[] = "Edge are not Weighted";
23  constexpr char ERR_DIJ_TARGET_NODE_NOT_REACHABLE[] = "Target Node not Reachable";
24  constexpr char ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH[] = "Target Node not inside Graph";
25  constexpr char ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH[] = "Source Node not inside Graph";
27  constexpr double INF_DOUBLE = std::numeric_limits<double>::max();
28  template <typename T>
29  class Node;
30  template <typename T>
31  class Edge;
32  template <typename T>
33  class DirectedEdge;
34  template <typename T>
35  class UndirectedEdge;
36  template <typename T>
37  class DirectedWeightedEdge;
38  template <typename T>
39  class UndirectedWeightedEdge;
40  template <typename T>
41  class Graph;
42 
43  class Weighted;
44 
45  template <typename T>
46  using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *, const Edge<T> *>>>;
47 
48  template <typename T>
49  std::ostream &operator<<(std::ostream &o, const Node<T> &node);
50  template <typename T>
51  std::ostream &operator<<(std::ostream &o, const Edge<T> &edge);
52  template <typename T>
53  std::ostream &operator<<(std::ostream &o, const DirectedEdge<T> &edge);
54  template <typename T>
55  std::ostream &operator<<(std::ostream &o, const UndirectedEdge<T> &edge);
56  template <typename T>
57  std::ostream &operator<<(std::ostream &o, const DirectedWeightedEdge<T> &edge);
58  template <typename T>
59  std::ostream &operator<<(std::ostream &o, const UndirectedWeightedEdge<T> &edge);
60  template <typename T>
61  std::ostream &operator<<(std::ostream &o, const Graph<T> &graph);
62  template <typename T>
63  std::ostream &operator<<(std::ostream &o, const AdjacencyMatrix<T> &adj);
64 
65  typedef struct DijkstraResult_struct
66  {
67  bool success; // TRUE if the function does not return error, FALSE otherwise
68  std::string errorMessage; //message of error
69  double result; //result (valid only if success is TRUE)
71 
72  template <typename T>
73  class Node
74  {
75  private:
76  unsigned long id;
77  T data;
78 
79  public:
80  Node(const unsigned long id, const T &data);
81  ~Node() = default;
82  const unsigned long &getId() const;
83  const T &getData() const;
84  //operator
85  bool operator==(const Node<T> &b) const;
86  bool operator<(const Node<T> &b) const;
87  friend std::ostream &operator<<<>(std::ostream &os, const Node<T> &node);
88  };
89 
90  template <typename T>
91  Node<T>::Node(const unsigned long id, const T &data)
92  {
93  this->id = id;
94  this->data = data;
95  }
96 
97  template <typename T>
98  const unsigned long &Node<T>::getId() const
99  {
100  return id;
101  }
102 
103  template <typename T>
104  const T &Node<T>::getData() const
105  {
106  return data;
107  }
108 
109  template <typename T>
110  bool Node<T>::operator==(const Node<T> &b) const
111  {
112  return (this->id == b.id && this->data == b.data);
113  }
114 
115  template <typename T>
116  bool Node<T>::operator<(const Node<T> &b) const
117  {
118  return (this->id < b.id);
119  }
120 
121  class Weighted
122  {
123  private:
124  double weight;
125 
126  public:
127  Weighted();
128  Weighted(const double weight);
129  virtual ~Weighted() = default;
130  double getWeight() const;
131  void setWeight(const double weight);
132  };
133 
134  //inline because the implementation of non-template function in header file
135  inline Weighted::Weighted()
136  {
137  weight = 0.0;
138  }
139 
140  //inline because the implementation of non-template function in header file
141  inline Weighted::Weighted(const double weight)
142  {
143  this->weight = weight;
144  }
145 
146  //inline because the implementation of non-template function in header file
147  inline double Weighted::getWeight() const
148  {
149  return weight;
150  }
151 
152  //inline because the implementation of non-template function in header file
153  inline void Weighted::setWeight(const double weight)
154  {
155  this->weight = weight;
156  }
157 
158  template <typename T>
159  class Edge
160  {
161  private:
162  unsigned long id;
163  std::pair<const Node<T> *, const Node<T> *> nodePair;
164 
165  public:
166  Edge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
167  Edge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
168  virtual ~Edge() = default;
169  const unsigned long &getId() const;
170  const std::pair<const Node<T> *, const Node<T> *> &getNodePair() const;
171  virtual const std::optional<bool> isDirected() const;
172  virtual const std::optional<bool> isWeighted() const;
173  //operator
174  virtual bool operator==(const Edge<T> &b) const;
175  bool operator<(const Edge<T> &b) const;
176  //operator DirectedEdge<T>() const { return DirectedEdge<T>(id, nodePair); }
177  //operator UndirectedEdge<T>() const { return UndirectedEdge<T>(id, nodePair); }
178 
179  friend std::ostream &operator<<<>(std::ostream &os, const Edge<T> &edge);
180  };
181 
182  template <typename T>
183  Edge<T>::Edge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : nodePair(&node1, &node2)
184  {
185  this->id = id;
186  }
187 
188  template <typename T>
189  Edge<T>::Edge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : nodePair(nodepair)
190  {
191  this->id = id;
192  }
193 
194  template <typename T>
195  const unsigned long &Edge<T>::getId() const
196  {
197  return id;
198  }
199 
200  template <typename T>
201  const std::pair<const Node<T> *, const Node<T> *> &Edge<T>::getNodePair() const
202  {
203  return nodePair;
204  }
205 
206  template <typename T>
207  const std::optional<bool> Edge<T>::isDirected() const
208  {
209  return std::nullopt;
210  }
211 
212  template <typename T>
213  const std::optional<bool> Edge<T>::isWeighted() const
214  {
215  return std::nullopt;
216  }
217 
218  template <typename T>
219  bool Edge<T>::operator==(const Edge<T> &b) const
220  {
221  return (this->id == b.id && this->nodePair == b.nodePair);
222  }
223 
224  template <typename T>
225  bool Edge<T>::operator<(const Edge<T> &b) const
226  {
227  return (this->id < b.id);
228  }
229 
230  template <typename T>
231  class DirectedEdge : public Edge<T>
232  {
233  public:
234  DirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
235  DirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
236  DirectedEdge(const Edge<T> &edge);
237  virtual ~DirectedEdge() = default;
238  const Node<T> &getFrom() const;
239  const Node<T> &getTo() const;
240  const std::optional<bool> isDirected() const override;
241  virtual const std::optional<bool> isWeighted() const override;
242  //operator
243  explicit operator UndirectedEdge<T>() const { return UndirectedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair()); }
244 
245  friend std::ostream &operator<<<>(std::ostream &os, const DirectedEdge<T> &edge);
246  };
247 
248  template <typename T>
249  DirectedEdge<T>::DirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : Edge<T>(id, node1, node2)
250  {
251  }
252 
253  template <typename T>
254  DirectedEdge<T>::DirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
255  {
256  }
257 
258  template <typename T>
259  DirectedEdge<T>::DirectedEdge(const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
260  {
261  }
262 
263  template <typename T>
264  const Node<T> &DirectedEdge<T>::getFrom() const
265  {
266  return *(Edge<T>::getNodePair().first);
267  }
268 
269  template <typename T>
270  const Node<T> &DirectedEdge<T>::getTo() const
271  {
272  return *(Edge<T>::getNodePair().second);
273  }
274 
275  template <typename T>
276  const std::optional<bool> DirectedEdge<T>::isDirected() const
277  {
278  return true;
279  }
280 
281  template <typename T>
282  const std::optional<bool> DirectedEdge<T>::isWeighted() const
283  {
284  return false;
285  }
286 
287  template <typename T>
288  class UndirectedEdge : public Edge<T>
289  {
290  public:
291  UndirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
292  UndirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
293  UndirectedEdge(const Edge<T> &edge);
294  virtual ~UndirectedEdge() = default;
295  const Node<T> &getNode1() const;
296  const Node<T> &getNode2() const;
297  const std::optional<bool> isDirected() const override;
298  const std::optional<bool> isWeighted() const override;
299  //operator
300  explicit operator DirectedEdge<T>() const { return DirectedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair()); }
301 
302  friend std::ostream &operator<<<>(std::ostream &os, const UndirectedEdge<T> &edge);
303  };
304 
305  template <typename T>
306  UndirectedEdge<T>::UndirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : Edge<T>(id, node1, node2)
307  {
308  }
309 
310  template <typename T>
311  UndirectedEdge<T>::UndirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
312  {
313  }
314 
315  template <typename T>
316  UndirectedEdge<T>::UndirectedEdge(const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
317  {
318  }
319 
320  template <typename T>
321  const Node<T> &UndirectedEdge<T>::getNode1() const
322  {
323  return *(Edge<T>::getNodePair().first);
324  }
325 
326  template <typename T>
327  const Node<T> &UndirectedEdge<T>::getNode2() const
328  {
329  return *(Edge<T>::getNodePair().second);
330  }
331 
332  template <typename T>
333  const std::optional<bool> UndirectedEdge<T>::isDirected() const
334  {
335  return false;
336  }
337 
338  template <typename T>
339  const std::optional<bool> UndirectedEdge<T>::isWeighted() const
340  {
341  return false;
342  }
343 
344  template <typename T>
345  class DirectedWeightedEdge : public DirectedEdge<T>, public Weighted
346  {
347  public:
348  DirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight);
349  DirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight);
350  DirectedWeightedEdge(const DirectedEdge<T> &edge, const double weight);
351  DirectedWeightedEdge(const Edge<T> &edge, const double weight);
353  DirectedWeightedEdge(const Edge<T> &edge);
355  virtual ~DirectedWeightedEdge() = default;
356  const std::optional<bool> isWeighted() const override;
357  //operator
358  explicit operator UndirectedWeightedEdge<T>() const { return UndirectedWeightedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair(), Weighted::getWeight()); }
359 
360  friend std::ostream &operator<<<>(std::ostream &os, const DirectedWeightedEdge<T> &edge);
361  };
362 
363  template <typename T>
364  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)
365  {
366  }
367 
368  template <typename T>
369  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)
370  {
371  }
372 
373  template <typename T>
374  DirectedWeightedEdge<T>::DirectedWeightedEdge(const DirectedEdge<T> &edge, const double weight) : DirectedEdge<T>(edge), Weighted(weight)
375  {
376  }
377 
378  template <typename T>
379  DirectedWeightedEdge<T>::DirectedWeightedEdge(const Edge<T> &edge, const double weight) : DirectedEdge<T>(edge), Weighted(weight)
380  {
381  }
382 
383  template <typename T>
384  DirectedWeightedEdge<T>::DirectedWeightedEdge(const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
385  {
386  }
387 
388  template <typename T>
389  DirectedWeightedEdge<T>::DirectedWeightedEdge(const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
390  {
391  }
392 
393  template <typename T>
394  DirectedWeightedEdge<T>::DirectedWeightedEdge(const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
395  {
396  }
397 
398  template <typename T>
399  const std::optional<bool> DirectedWeightedEdge<T>::isWeighted() const
400  {
401  return true;
402  }
403 
404  template <typename T>
406  {
407  public:
408  UndirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight);
409  UndirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight);
410  UndirectedWeightedEdge(const UndirectedEdge<T> &edge, const double weight);
411  UndirectedWeightedEdge(const Edge<T> &edge, const double weight);
413  UndirectedWeightedEdge(const Edge<T> &edge);
415  virtual ~UndirectedWeightedEdge() = default;
416  const std::optional<bool> isWeighted() const override;
417  //operator
418  explicit operator DirectedWeightedEdge<T>() const { return DirectedWeightedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair(), Weighted::getWeight()); }
419 
420  friend std::ostream &operator<<<>(std::ostream &os, const UndirectedWeightedEdge<T> &edge);
421  };
422 
423  template <typename T>
424  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)
425  {
426  }
427 
428  template <typename T>
429  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)
430  {
431  }
432 
433  template <typename T>
434  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const UndirectedEdge<T> &edge, const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
435  {
436  }
437 
438  template <typename T>
439  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const Edge<T> &edge, const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
440  {
441  }
442 
443  template <typename T>
444  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
445  {
446  }
447 
448  template <typename T>
449  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
450  {
451  }
452 
453  template <typename T>
454  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
455  {
456  }
457 
458  template <typename T>
459  const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted() const
460  {
461  return true;
462  }
463 
464  template <typename T>
465  class Partition;
466  template <typename T>
467  class Graph
468  {
469  private:
470  std::list<const Edge<T> *> edgeSet;
471  void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const;
472  int writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
473  int readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
474  int writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
475  int readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
476  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);
477  void greedyPartition(std::map<unsigned int, Partition<T> *> &partitionMap) const;
478 
479  public:
481  typedef enum E_InputOutputFormat
482  {
485  OUT_1,
486  OUT_2
488 
489  typedef enum E_PartitionAlgorithm
490  {
492  ALG_1,
493  ALG_2
494  } PartitionAlgorithm;
495 
496  Graph() = default;
497  Graph(const std::list<const Edge<T> *> &edgeSet);
498  ~Graph() = default;
499  const std::list<const Edge<T> *> &getEdgeSet() const;
500  void setEdgeSet(std::list<const Edge<T> *> &edgeSet);
501  void addEdge(const Edge<T> *edge);
502  void removeEdge(unsigned long edgeId);
503  const std::list<const Node<T> *> getNodeSet() const;
504  const std::optional<const Edge<T> *> getEdge(unsigned long edgeId) const;
505  /*This function generate a list of adjacency matrix with every element of the matrix
506  * contain the node where is directed the link and the Edge corrispondent to the link
507  */
508  const AdjacencyMatrix<T> getAdjMatrix() const;
520  const DijkstraResult dijkstra(const Node<T> &source, const Node<T> &target) const;
530  const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const;
540  const std::vector<Node<T>> depth_first_search(const Node<T> &start) const;
541 
549  bool isCyclicDirectedGraphDFS() const;
550 
558  bool isCyclicDirectedGraphBFS() const;
559 
566  bool isDirectedGraph() const;
567 
580  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;
581 
594  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);
595 
604  std::map<unsigned int, Partition<T> *> partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const;
605 
606  friend std::ostream &operator<<<>(std::ostream &os, const Graph<T> &graph);
607  friend std::ostream &operator<<<>(std::ostream &os, const AdjacencyMatrix<T> &adj);
608  };
609 
610  template <typename T>
611  Graph<T>::Graph(const std::list<const Edge<T> *> &edgeSet)
612  {
613  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
614  {
615  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
616  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
617  {
618  this->edgeSet.push_back(*edgeSetIt);
619  }
620  }
621  }
622 
623  template <typename T>
624  const std::list<const Edge<T> *> &Graph<T>::getEdgeSet() const
625  {
626  return edgeSet;
627  }
628 
629  template <typename T>
630  void Graph<T>::setEdgeSet(std::list<const Edge<T> *> &edgeSet)
631  {
632  this->edgeSet.clear();
633  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
634  {
635  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
636  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
637  {
638  this->edgeSet.push_back(*edgeSetIt);
639  }
640  }
641  }
642 
643  template <typename T>
644  void Graph<T>::addEdge(const Edge<T> *edge)
645  {
646  if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](const Edge<T> *edge_a)
647  { return (*edge == *edge_a); }) == edgeSet.end())
648  {
649  edgeSet.push_back(edge);
650  }
651  }
652 
653  template <typename T>
654  void Graph<T>::removeEdge(unsigned long edgeId)
655  {
656  auto edgeOpt = getEdge(edgeId);
657  if (edgeOpt.has_value())
658  {
659  edgeSet.erase(edgeSet.find(edgeOpt.value()));
660  }
661  }
662 
663  template <typename T>
664  const std::list<const Node<T> *> Graph<T>::getNodeSet() const
665  {
666  std::list<const Node<T> *> nodeSet;
667  for (auto edge : edgeSet)
668  {
669  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
670  { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
671  {
672  nodeSet.push_back(edge->getNodePair().first);
673  }
674  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
675  { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
676  {
677  nodeSet.push_back(edge->getNodePair().second);
678  }
679  }
680  return nodeSet;
681  }
682 
683  template <typename T>
684  const std::optional<const Edge<T> *> Graph<T>::getEdge(unsigned long edgeId) const
685  {
686 
687  auto it = edgeSet.begin();
688  for (it; it != edgeSet.end(); ++it)
689  {
690  if ((*it)->getId() == edgeId)
691  {
692  return *it;
693  }
694  }
695 
696  return std::nullopt;
697  }
698 
699  template <typename T>
700  void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const
701  {
702  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
703  adjMatrix[nodeFrom].push_back(elem);
704 
705  //adjMatrix[nodeFrom.getId()].push_back(std::make_pair<const Node<T>,const Edge<T>>(nodeTo, edge));
706  }
707 
708  template <typename T>
709  int Graph<T>::writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
710  {
711  std::ofstream ofileGraph;
712  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
713  ofileGraph.open(completePathToFileGraph);
714  if (!ofileGraph.is_open())
715  {
716  // ERROR File Not Open
717  return -1;
718  }
719  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
720  { ofileGraph << e->getId() << "," << e->getNodePair().first->getId() << "," << e->getNodePair().second->getId() << "," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
721  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
722  ofileGraph.close();
723 
724  if (writeNodeFeat)
725  {
726  std::ofstream ofileNodeFeat;
727  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
728  ".csv";
729  ofileNodeFeat.open(completePathToFileNodeFeat);
730  if (!ofileNodeFeat.is_open())
731  {
732  // ERROR File Not Open
733  return -1;
734  }
735  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
736  { ofileNodeFeat << node->getId() << "," << node->getData() << std::endl; };
737  auto nodeSet = getNodeSet();
738  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
739  ofileNodeFeat.close();
740  }
741 
742  if (writeEdgeWeight)
743  {
744  std::ofstream ofileEdgeWeight;
745  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
746  ".csv";
747  ofileEdgeWeight.open(completePathToFileEdgeWeight);
748  if (!ofileEdgeWeight.is_open())
749  {
750  // ERROR File Not Open
751  return -1;
752  }
753  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
754  { 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; };
755 
756  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
757  ofileEdgeWeight.close();
758  }
759  return 0;
760  }
761 
762  template <typename T>
763  int Graph<T>::readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
764  {
765  std::ifstream ifileGraph;
766  std::ifstream ifileNodeFeat;
767  std::ifstream ifileEdgeWeight;
768  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
769  std::map<unsigned long, bool> edgeDirectedMap;
770  std::map<unsigned long, T> nodeFeatMap;
771  std::map<unsigned long, double> edgeWeightMap;
772  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
773  ifileGraph.open(completePathToFileGraph);
774  if (!ifileGraph.is_open())
775  {
776  // ERROR File Not Open
777  return -1;
778  }
779  char comma;
780  for (;;)
781  { /* loop continually */
782  unsigned long edgeId;
783  unsigned long nodeId1;
784  unsigned long nodeId2;
785  bool directed;
786  ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
787  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
788  edgeDirectedMap[edgeId] = directed;
789  if (ifileGraph.fail() || ifileGraph.eof())
790  break;
791  ifileGraph.ignore(128, '\n');
792  }
793  ifileGraph.close();
794 
795  if (readNodeFeat)
796  {
797  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
798  ".csv";
799  ifileNodeFeat.open(completePathToFileNodeFeat);
800  if (!ifileNodeFeat.is_open())
801  {
802  // ERROR File Not Open
803  return -1;
804  }
805  for (;;)
806  { /* loop continually */
807  unsigned long nodeId;
808  T nodeFeat;
809  ifileNodeFeat >> nodeId >> comma >> nodeFeat;
810  nodeFeatMap[nodeId] = nodeFeat;
811  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
812  break;
813  ifileNodeFeat.ignore(128, '\n');
814  }
815  ifileNodeFeat.close();
816  }
817 
818  if (readEdgeWeight)
819  {
820 
821  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
822  ".csv";
823  ifileEdgeWeight.open(completePathToFileEdgeWeight);
824  if (!ifileEdgeWeight.is_open())
825  {
826  // ERROR File Not Open
827  return -1;
828  }
829  for (;;)
830  { /* loop continually */
831  unsigned long edgeId;
832  double weight;
833  bool weighted;
834  ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
835  if (weighted)
836  {
837  edgeWeightMap[edgeId] = weight;
838  }
839  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
840  break;
841  ifileEdgeWeight.ignore(128, '\n');
842  }
843  ifileEdgeWeight.close();
844  }
845  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
846  return 0;
847  }
848 
849  template <typename T>
850  int Graph<T>::writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
851  {
852  std::ofstream ofileGraph;
853  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
854  ofileGraph.open(completePathToFileGraph);
855  if (!ofileGraph.is_open())
856  {
857  // ERROR File Not Open
858  return -1;
859  }
860  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
861  { 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; };
862  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
863  ofileGraph.close();
864 
865  if (writeNodeFeat)
866  {
867  std::ofstream ofileNodeFeat;
868  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
869  ".tsv";
870  ofileNodeFeat.open(completePathToFileNodeFeat);
871  if (!ofileNodeFeat.is_open())
872  {
873  // ERROR File Not Open
874  return -1;
875  }
876  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
877  { ofileNodeFeat << node->getId() << "\t" << node->getData() << std::endl; };
878  auto nodeSet = getNodeSet();
879  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
880  ofileNodeFeat.close();
881  }
882 
883  if (writeEdgeWeight)
884  {
885  std::ofstream ofileEdgeWeight;
886  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
887  ".tsv";
888  ofileEdgeWeight.open(completePathToFileEdgeWeight);
889  if (!ofileEdgeWeight.is_open())
890  {
891  // ERROR File Not Open
892  return -1;
893  }
894  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
895  { 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; };
896 
897  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
898  ofileEdgeWeight.close();
899  }
900  return 0;
901  }
902 
903  template <typename T>
904  int Graph<T>::readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
905  {
906  std::ifstream ifileGraph;
907  std::ifstream ifileNodeFeat;
908  std::ifstream ifileEdgeWeight;
909  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
910  std::map<unsigned long, bool> edgeDirectedMap;
911  std::map<unsigned long, T> nodeFeatMap;
912  std::map<unsigned long, double> edgeWeightMap;
913  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
914  ifileGraph.open(completePathToFileGraph);
915  if (!ifileGraph.is_open())
916  {
917  // ERROR File Not Open
918  return -1;
919  }
920  for (;;)
921  { /* loop continually */
922  unsigned long edgeId;
923  unsigned long nodeId1;
924  unsigned long nodeId2;
925  bool directed;
926  ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
927  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
928  edgeDirectedMap[edgeId] = directed;
929  if (ifileGraph.fail() || ifileGraph.eof())
930  break;
931  ifileGraph.ignore(128, '\n');
932  }
933  ifileGraph.close();
934 
935  if (readNodeFeat)
936  {
937  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
938  ".tsv";
939  ifileNodeFeat.open(completePathToFileNodeFeat);
940  if (!ifileNodeFeat.is_open())
941  {
942  // ERROR File Not Open
943  return -1;
944  }
945  for (;;)
946  { /* loop continually */
947  unsigned long nodeId;
948  T nodeFeat;
949  ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
950  nodeFeatMap[nodeId] = nodeFeat;
951  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
952  break;
953  ifileNodeFeat.ignore(128, '\n');
954  }
955  ifileNodeFeat.close();
956  }
957 
958  if (readEdgeWeight)
959  {
960 
961  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
962  ".tsv";
963  ifileEdgeWeight.open(completePathToFileEdgeWeight);
964  if (!ifileEdgeWeight.is_open())
965  {
966  // ERROR File Not Open
967  return -1;
968  }
969  for (;;)
970  { /* loop continually */
971  unsigned long edgeId;
972  double weight;
973  bool weighted;
974  ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
975  if (weighted)
976  {
977  edgeWeightMap[edgeId] = weight;
978  }
979  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
980  break;
981  ifileEdgeWeight.ignore(128, '\n');
982  }
983  ifileEdgeWeight.close();
984  }
985  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
986  return 0;
987  }
988 
989  template <typename T>
990  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)
991  {
992  std::map<unsigned long, Node<T> *> nodeMap;
993  for (auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
994  {
995  Node<T> *node1 = nullptr;
996  Node<T> *node2 = nullptr;
997  if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
998  {
999  //Create new Node
1000  T feat;
1001  if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
1002  {
1003  feat = nodeFeatMap.at(edgeIt->second.first);
1004  }
1005  node1 = new Node<T>(edgeIt->second.first, feat);
1006  nodeMap[edgeIt->second.first] = node1;
1007  }
1008  else
1009  {
1010  node1 = nodeMap.at(edgeIt->second.first);
1011  }
1012  if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
1013  {
1014  //Create new Node
1015  T feat;
1016  if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
1017  {
1018  feat = nodeFeatMap.at(edgeIt->second.second);
1019  }
1020  node2 = new Node<T>(edgeIt->second.second, feat);
1021  nodeMap[edgeIt->second.second] = node2;
1022  }
1023  else
1024  {
1025  node2 = nodeMap.at(edgeIt->second.second);
1026  }
1027 
1028  if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
1029  {
1030  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1031  {
1032  auto edge = new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1033  addEdge(edge);
1034  }
1035  else
1036  {
1037  auto edge = new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1038  addEdge(edge);
1039  }
1040  }
1041  else
1042  {
1043  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1044  {
1045  auto edge = new DirectedEdge<T>(edgeIt->first, *node1, *node2);
1046  addEdge(edge);
1047  }
1048  else
1049  {
1050  auto edge = new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
1051  addEdge(edge);
1052  }
1053  }
1054  }
1055  }
1056 
1057  template <typename T>
1058  void Graph<T>::greedyPartition(std::map<unsigned int, Partition<T> *> &partitionMap) const
1059  {
1060  unsigned int index = 0;
1061  unsigned int numberOfPartitions = partitionMap.size();
1062  if (index == numberOfPartitions)
1063  {
1064  //ERROR partion map of zero element
1065  return;
1066  }
1067  auto edgeSet = getEdgeSet();
1068  for (auto edge : edgeSet)
1069  {
1070  partitionMap.at(index)->addEdge(edge);
1071  index++;
1072  index = index % numberOfPartitions;
1073  }
1074  }
1075 
1076  template <typename T>
1077  const AdjacencyMatrix<T> Graph<T>::getAdjMatrix() const
1078  {
1079  AdjacencyMatrix<T> adj;
1080  auto edgeSetIt = edgeSet.begin();
1081  for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
1082  {
1083  if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
1084  {
1085  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(*edgeSetIt);
1086  addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
1087  }
1088  else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
1089  {
1090  const UndirectedEdge<T> *ud_edge = dynamic_cast<const UndirectedEdge<T> *>(*edgeSetIt);
1091  ;
1092  addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
1093  addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
1094  }
1095  else
1096  { //is a simple edge we cannot create adj matrix
1097  return adj;
1098  }
1099  }
1100  return adj;
1101  }
1102 
1103  template <typename T>
1104  const DijkstraResult Graph<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
1105  {
1106  DijkstraResult result;
1107  result.success = false;
1108  result.errorMessage = "";
1109  result.result = INF_DOUBLE;
1110  auto nodeSet = getNodeSet();
1111  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1112  {
1113  // check if source node exist in the graph
1114  result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
1115  return result;
1116  }
1117  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1118  {
1119  // check if target node exist in the graph
1120  result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
1121  return result;
1122  }
1123  const AdjacencyMatrix<T> adj = getAdjMatrix();
1124  // n denotes the number of vertices in graph
1125  int n = adj.size();
1126 
1127  // setting all the distances initially to INF_DOUBLE
1128  std::map<const Node<T> *, double> dist;
1129 
1130  for (auto elem : adj)
1131  {
1132  dist[elem.first] = INF_DOUBLE;
1133  }
1134 
1135  // creating a min heap using priority queue
1136  // first element of pair contains the distance
1137  // second element of pair contains the vertex
1138  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1139  std::greater<std::pair<double, const Node<T> *>>>
1140  pq;
1141 
1142  // pushing the source vertex 's' with 0 distance in min heap
1143  pq.push(std::make_pair(0.0, &source));
1144 
1145  // marking the distance of source as 0
1146  dist[&source] = 0;
1147 
1148  while (!pq.empty())
1149  {
1150  // second element of pair denotes the node / vertex
1151  const Node<T> *currentNode = pq.top().second;
1152 
1153  // first element of pair denotes the distance
1154  double currentDist = pq.top().first;
1155 
1156  pq.pop();
1157 
1158  // for all the reachable vertex from the currently exploring vertex
1159  // we will try to minimize the distance
1160  if (adj.find(currentNode) != adj.end())
1161  {
1162  for (std::pair<const Node<T> *, const Edge<T> *> elem : adj.at(currentNode))
1163  {
1164  // minimizing distances
1165  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1166  {
1167  if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1168  {
1169  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(elem.second);
1170  if (currentDist + dw_edge->getWeight() < dist[elem.first])
1171  {
1172  dist[elem.first] = currentDist + dw_edge->getWeight();
1173  pq.push(std::make_pair(dist[elem.first], elem.first));
1174  }
1175  }
1176  else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1177  {
1178  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
1179  if (currentDist + udw_edge->getWeight() < dist[elem.first])
1180  {
1181  dist[elem.first] = currentDist + udw_edge->getWeight();
1182  pq.push(std::make_pair(dist[elem.first], elem.first));
1183  }
1184  }
1185  else
1186  {
1187  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
1188  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1189  return result;
1190  }
1191  }
1192  else
1193  {
1194  // No Weighted Edge
1195  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1196  return result;
1197  }
1198  }
1199  }
1200  }
1201  if (dist[&target] != INF_DOUBLE)
1202  {
1203  result.success = true;
1204  result.errorMessage = "";
1205  result.result = dist[&target];
1206  return result;
1207  }
1208  result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
1209  result.result = -1;
1210  return result;
1211  }
1212 
1213  template <typename T>
1214  const std::vector<Node<T>> Graph<T>::breadth_first_search(const Node<T> &start) const
1215  {
1216  // vector to keep track of visited nodes
1217  std::vector<Node<T>> visited;
1218  auto nodeSet = getNodeSet();
1219  //check is exist node in the graph
1220  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1221  {
1222  return visited;
1223  }
1224  const AdjacencyMatrix<T> adj = getAdjMatrix();
1225  // queue that stores vertices that need to be further explored
1226  std::queue<const Node<T> *> tracker;
1227 
1228  // mark the starting node as visited
1229  visited.push_back(start);
1230  tracker.push(&start);
1231  while (!tracker.empty())
1232  {
1233  const Node<T> *node = tracker.front();
1234  tracker.pop();
1235  if (adj.find(node) != adj.end())
1236  {
1237  for (auto elem : adj.at(node))
1238  {
1239  // if the node is not visited then mark it as visited
1240  // and push it to the queue
1241  if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1242  {
1243  visited.push_back(*(elem.first));
1244  tracker.push(elem.first);
1245  }
1246  }
1247  }
1248  }
1249 
1250  return visited;
1251  }
1252 
1253  template <typename T>
1254  const std::vector<Node<T>> Graph<T>::depth_first_search(const Node<T> &start) const
1255  {
1256  // vector to keep track of visited nodes
1257  std::vector<Node<T>> visited;
1258  auto nodeSet = getNodeSet();
1259  //check is exist node in the graph
1260  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1261  {
1262  return visited;
1263  }
1264  const AdjacencyMatrix<T> adj = getAdjMatrix();
1265  std::function<void(const AdjacencyMatrix<T> &, const Node<T> &, std::vector<Node<T>> &)> explore;
1266  explore = [&explore](const AdjacencyMatrix<T> &adj, const Node<T> &node, std::vector<Node<T>> &visited) -> void
1267  {
1268  visited.push_back(node);
1269  if (adj.find(&node) != adj.end())
1270  {
1271  for (auto x : adj.at(&node))
1272  {
1273  if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1274  {
1275  explore(adj, *(x.first), visited);
1276  }
1277  }
1278  }
1279  };
1280  explore(adj, start, visited);
1281 
1282  return visited;
1283  }
1284 
1285  template <typename T>
1287  {
1288  if (!isDirectedGraph())
1289  {
1290  return false;
1291  }
1292  enum nodeStates : uint8_t
1293  {
1294  not_visited,
1295  in_stack,
1296  visited
1297  };
1298  auto nodeSet = this->getNodeSet();
1299  auto adjMatrix = this->getAdjMatrix();
1300 
1301  /* State of the node.
1302  *
1303  * It is a vector of "nodeStates" which represents the state node is in.
1304  * It can take only 3 values: "not_visited", "in_stack", and "visited".
1305  *
1306  * Initially, all nodes are in "not_visited" state.
1307  */
1308  std::map<unsigned long, nodeStates> state;
1309  for (auto node : nodeSet)
1310  {
1311  state[node->getId()] = not_visited;
1312  }
1313  int stateCounter = 0;
1314 
1315  // Start visiting each node.
1316  for (auto node : nodeSet)
1317  {
1318  // If a node is not visited, only then check for presence of cycle.
1319  // There is no need to check for presence of cycle for a visited
1320  // node as it has already been checked for presence of cycle.
1321  if (state[node->getId()] == not_visited)
1322  {
1323  // Check for cycle.
1324  std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &, const Node<T> *)> isCyclicDFSHelper;
1325  isCyclicDFSHelper = [this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states, const Node<T> *node)
1326  {
1327  // Add node "in_stack" state.
1328  states[node->getId()] = in_stack;
1329 
1330  // If the node has children, then recursively visit all children of the
1331  // node.
1332  auto const it = adjMatrix.find(node);
1333  if (it != adjMatrix.end())
1334  {
1335  for (auto child : it->second)
1336  {
1337  // If state of child node is "not_visited", evaluate that child
1338  // for presence of cycle.
1339  auto state_of_child = states.at((std::get<0>(child))->getId());
1340  if (state_of_child == not_visited)
1341  {
1342  if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1343  {
1344  return true;
1345  }
1346  }
1347  else if (state_of_child == in_stack)
1348  {
1349  // If child node was "in_stack", then that means that there
1350  // is a cycle in the graph. Return true for presence of the
1351  // cycle.
1352  return true;
1353  }
1354  }
1355  }
1356 
1357  // Current node has been evaluated for the presence of cycle and had no
1358  // cycle. Mark current node as "visited".
1359  states[node->getId()] = visited;
1360  // Return that current node didn't result in any cycles.
1361  return false;
1362  };
1363  if (isCyclicDFSHelper(adjMatrix, state, node))
1364  {
1365  return true;
1366  }
1367  }
1368  }
1369 
1370  // All nodes have been safely traversed, that means there is no cycle in
1371  // the graph. Return false.
1372  return false;
1373  }
1374 
1375  template <typename T>
1377  {
1378  if (!isDirectedGraph())
1379  {
1380  return false;
1381  }
1382  auto adjMatrix = this->getAdjMatrix();
1383  auto nodeSet = this->getNodeSet();
1384 
1385  std::map<unsigned long, unsigned int> indegree;
1386  for (auto node : nodeSet)
1387  {
1388  indegree[node->getId()] = 0;
1389  }
1390  // Calculate the indegree i.e. the number of incident edges to the node.
1391  for (auto const &list : adjMatrix)
1392  {
1393  auto children = list.second;
1394  for (auto const &child : children)
1395  {
1396  indegree[std::get<0>(child)->getId()]++;
1397  }
1398  }
1399 
1400  std::queue<const Node<T> *> can_be_solved;
1401  for (auto node : nodeSet)
1402  {
1403  // If a node doesn't have any input edges, then that node will
1404  // definately not result in a cycle and can be visited safely.
1405  if (!indegree[node->getId()])
1406  {
1407  can_be_solved.emplace(&(*node));
1408  }
1409  }
1410 
1411  // Vertices that need to be traversed.
1412  auto remain = this->getNodeSet().size();
1413  // While there are safe nodes that we can visit.
1414  while (!can_be_solved.empty())
1415  {
1416  auto solved = can_be_solved.front();
1417  // Visit the node.
1418  can_be_solved.pop();
1419  // Decrease number of nodes that need to be traversed.
1420  remain--;
1421 
1422  // Visit all the children of the visited node.
1423  auto it = adjMatrix.find(solved);
1424  if (it != adjMatrix.end())
1425  {
1426  for (auto child : it->second)
1427  {
1428  // Check if we can visited the node safely.
1429  if (--indegree[std::get<0>(child)->getId()] == 0)
1430  {
1431  // if node can be visited safely, then add that node to
1432  // the visit queue.
1433  can_be_solved.emplace(std::get<0>(child));
1434  }
1435  }
1436  }
1437  }
1438 
1439  // If there are still nodes that we can't visit, then it means that
1440  // there is a cycle and return true, else return false.
1441  return !(remain == 0);
1442  }
1443 
1444  template <typename T>
1446  {
1447  auto edgeSet = this->getEdgeSet();
1448  for (auto edge : edgeSet)
1449  {
1450  if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1451  {
1452  //Found Undirected Edge
1453  return false;
1454  }
1455  }
1456  //No Undirected Edge
1457  return true;
1458  }
1459 
1460  template <typename T>
1461  int Graph<T>::writeToFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
1462  {
1463  if (format == InputOutputFormat::STANDARD_CSV)
1464  {
1465  return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1466  }
1467  else if (format == InputOutputFormat::STANDARD_TSV)
1468  {
1469  return writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1470  }
1471  else
1472  {
1473  //OUTPUT FORMAT NOT RECOGNIZED
1474  return -1;
1475  }
1476  }
1477 
1478  template <typename T>
1479  int Graph<T>::readFromFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
1480  {
1481  if (format == InputOutputFormat::STANDARD_CSV)
1482  {
1483  return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1484  }
1485  else if (format == InputOutputFormat::STANDARD_TSV)
1486  {
1487  return readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1488  }
1489  else
1490  {
1491  //OUTPUT FORMAT NOT RECOGNIZED
1492  return -1;
1493  }
1494  }
1495 
1496  template <typename T>
1497  std::map<unsigned int, Partition<T> *> Graph<T>::partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
1498  {
1499  std::map<unsigned int, Partition<T> *> partitionMap;
1500  for (unsigned int i = 0; i < numberOfPartitions; ++i)
1501  {
1502  partitionMap[i] = new Partition<T>(i);
1503  }
1504  if (algorithm == PartitionAlgorithm::GREEDY_VC)
1505  {
1506  greedyPartition(partitionMap);
1507  }
1508  else
1509  {
1510  //Error not recognized algorithm
1511  partitionMap.clear();
1512  }
1513  return partitionMap;
1514  }
1515 
1516  template <typename T>
1517  class Partition : public Graph<T>
1518  {
1519  public:
1520  Partition();
1521  Partition(unsigned int partitionId);
1522  Partition(const std::list<const Edge<T> *> &edgeSet);
1523  Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet);
1524  ~Partition() = default;
1525 
1526  unsigned int getPartitionId() const;
1527  void setPartitionId(unsigned int partitionId);
1528 
1529  private:
1530  unsigned int partitionId;
1531  };
1532 
1533  template <typename T>
1535  {
1536  partitionId = 0;
1537  }
1538 
1539  template <typename T>
1540  Partition<T>::Partition(unsigned int partitionId) : Graph<T>()
1541  {
1542  this->partitionId = partitionId;
1543  }
1544 
1545  template <typename T>
1546  Partition<T>::Partition(const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
1547  {
1548  partitionId = 0;
1549  }
1550 
1551  template <typename T>
1552  Partition<T>::Partition(unsigned int partitionId, const std::list<const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
1553  {
1554  this->partitionId = partitionId;
1555  }
1556 
1557  template <typename T>
1558  unsigned int Partition<T>::getPartitionId() const
1559  {
1560  return partitionId;
1561  }
1562 
1563  template <typename T>
1564  void Partition<T>::setPartitionId(unsigned int partitionId)
1565  {
1566  this->partitionId = partitionId;
1567  }
1568 
1569  //ostream overload
1570  template <typename T>
1571  std::ostream &operator<<(std::ostream &os, const Node<T> &node)
1572  {
1573  os << "Node: {\n"
1574  << " Id:\t" << node.id << "\n Data:\t" << node.data << "\n}";
1575  return os;
1576  }
1577 
1578  template <typename T>
1579  std::ostream &operator<<(std::ostream &os, const Edge<T> &edge)
1580  {
1581  os << "((Node: " << edge.nodePair.first->getId() << ")) ?----- |Edge: " << edge.id << "|-----? ((Node: " << edge.nodePair.second->getId() << "))";
1582  return os;
1583  }
1584 
1585  template <typename T>
1586  std::ostream &operator<<(std::ostream &os, const DirectedEdge<T> &edge)
1587  {
1588  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getTo().getId() << "))";
1589  return os;
1590  }
1591 
1592  template <typename T>
1593  std::ostream &operator<<(std::ostream &os, const UndirectedEdge<T> &edge)
1594  {
1595  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
1596  return os;
1597  }
1598 
1599  template <typename T>
1600  std::ostream &operator<<(std::ostream &os, const DirectedWeightedEdge<T> &edge)
1601  {
1602  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getTo().getId() << "))";
1603  return os;
1604  }
1605 
1606  template <typename T>
1607  std::ostream &operator<<(std::ostream &os, const UndirectedWeightedEdge<T> &edge)
1608  {
1609  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
1610  return os;
1611  }
1612 
1613  template <typename T>
1614  std::ostream &operator<<(std::ostream &os, const AdjacencyMatrix<T> &adj)
1615  {
1616  os << "Adjacency Matrix:\n";
1617  auto it = adj.begin();
1618  unsigned long max_column = 0;
1619  for (it; it != adj.end(); ++it)
1620  {
1621  if (it->second.size() > max_column)
1622  {
1623  max_column = it->second.size();
1624  }
1625  }
1626  if (max_column == 0)
1627  {
1628  os << "ERROR in Print\n";
1629  return os;
1630  }
1631  else
1632  {
1633  it = adj.begin();
1634  os << "|--|";
1635  for (int i = 0; i < max_column; i++)
1636  {
1637  os << "-----|";
1638  }
1639  os << "\n";
1640  for (it; it != adj.end(); ++it)
1641  {
1642  os << "|N" << it->first->getId() << "|";
1643  auto it2 = it->second.begin();
1644  for (it2; it2 != it->second.end(); ++it2)
1645  {
1646  os << "N" << it2->first->getId() << ",E" << it2->second->getId() << "|";
1647  }
1648  os << "\n|--|";
1649  for (int i = 0; i < max_column; i++)
1650  {
1651  os << "-----|";
1652  }
1653  os << "\n";
1654  }
1655  }
1656  return os;
1657  }
1658 
1659 } // namespace CXXGRAPH
1660 #endif // __CXXGRAPH_H__
Definition: Graph.hpp:232
Definition: Graph.hpp:346
Definition: Graph.hpp:160
Definition: Graph.hpp:468
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:1254
E_PartitionAlgorithm
Definition: Graph.hpp:490
@ GREEDY_VC
A Greedy Vertex-Cut Algorithm.
Definition: Graph.hpp:491
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:1376
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:1461
bool isDirectedGraph() const
This function checks if a graph is directed.
Definition: Graph.hpp:1445
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:1104
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:1286
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:1479
std::map< unsigned int, Partition< T > * > partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
This function partition a graph in a set of partitions.
Definition: Graph.hpp:1497
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:1214
E_InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
Definition: Graph.hpp:482
@ STANDARD_CSV
A standard csv format.
Definition: Graph.hpp:483
@ STANDARD_TSV
A standard tsv format.
Definition: Graph.hpp:484
Definition: Graph.hpp:74
Definition: Graph.hpp:1518
Definition: Graph.hpp:289
Definition: Graph.hpp:406
Definition: Graph.hpp:122
Definition: Graph.hpp:66