CXXGraph  0.1.1
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 Graph
466  {
467  private:
468  std::list<const Edge<T> *> edgeSet;
469  void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const;
470  int writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
471  int readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
472  int writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
473  int readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
474 
475  public:
477  typedef enum E_InputOutputFormat
478  {
481  OUT_1,
482  OUT_2
484 
485  Graph() = default;
486  Graph(const std::list<const Edge<T> *> &edgeSet);
487  ~Graph() = default;
488  const std::list<const Edge<T> *> &getEdgeSet() const;
489  void setEdgeSet(std::list<const Edge<T> *> &edgeSet);
490  void addEdge(const Edge<T> *edge);
491  void removeEdge(unsigned long edgeId);
492  const std::list<const Node<T> *> getNodeSet() const;
493  const std::optional<const Edge<T> *> getEdge(unsigned long edgeId) const;
494  /*This function generate a list of adjacency matrix with every element of the matrix
495  * contain the node where is directed the link and the Edge corrispondent to the link
496  */
497  const AdjacencyMatrix<T> getAdjMatrix() const;
509  const DijkstraResult dijkstra(const Node<T> &source, const Node<T> &target) const;
519  const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const;
529  const std::vector<Node<T>> depth_first_search(const Node<T> &start) const;
530 
538  bool isCyclicDirectedGraphDFS() const;
539 
547  bool isCyclicDirectedGraphBFS() const;
548 
555  bool isDirectedGraph() const;
556 
569  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;
582  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);
583 
584  friend std::ostream &operator<<<>(std::ostream &os, const Graph<T> &graph);
585  friend std::ostream &operator<<<>(std::ostream &os, const AdjacencyMatrix<T> &adj);
586  };
587 
588  template <typename T>
589  Graph<T>::Graph(const std::list<const Edge<T> *> &edgeSet)
590  {
591  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
592  {
593  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
594  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
595  {
596  this->edgeSet.push_back(*edgeSetIt);
597  }
598  }
599  }
600 
601  template <typename T>
602  const std::list<const Edge<T> *> &Graph<T>::getEdgeSet() const
603  {
604  return edgeSet;
605  }
606 
607  template <typename T>
608  void Graph<T>::setEdgeSet(std::list<const Edge<T> *> &edgeSet)
609  {
610  this->edgeSet.clear();
611  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
612  {
613  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
614  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
615  {
616  this->edgeSet.push_back(*edgeSetIt);
617  }
618  }
619  }
620 
621  template <typename T>
622  void Graph<T>::addEdge(const Edge<T> *edge)
623  {
624  if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](const Edge<T> *edge_a)
625  { return (*edge == *edge_a); }) == edgeSet.end())
626  {
627  edgeSet.push_back(edge);
628  }
629  }
630 
631  template <typename T>
632  void Graph<T>::removeEdge(unsigned long edgeId)
633  {
634  auto edgeOpt = getEdge(edgeId);
635  if (edgeOpt.has_value())
636  {
637  edgeSet.erase(edgeSet.find(edgeOpt.value()));
638  }
639  }
640 
641  template <typename T>
642  const std::list<const Node<T> *> Graph<T>::getNodeSet() const
643  {
644  std::list<const Node<T> *> nodeSet;
645  for (auto edge : edgeSet)
646  {
647  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
648  { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
649  {
650  nodeSet.push_back(edge->getNodePair().first);
651  }
652  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
653  { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
654  {
655  nodeSet.push_back(edge->getNodePair().second);
656  }
657  }
658  return nodeSet;
659  }
660 
661  template <typename T>
662  const std::optional<const Edge<T> *> Graph<T>::getEdge(unsigned long edgeId) const
663  {
664 
665  auto it = edgeSet.begin();
666  for (it; it != edgeSet.end(); ++it)
667  {
668  if ((*it)->getId() == edgeId)
669  {
670  return *it;
671  }
672  }
673 
674  return std::nullopt;
675  }
676 
677  template <typename T>
678  void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const
679  {
680  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
681  adjMatrix[nodeFrom].push_back(elem);
682 
683  //adjMatrix[nodeFrom.getId()].push_back(std::make_pair<const Node<T>,const Edge<T>>(nodeTo, edge));
684  }
685 
686  template <typename T>
687  int Graph<T>::writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
688  {
689  std::ofstream ofileGraph;
690  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
691  ofileGraph.open(completePathToFileGraph);
692  if (!ofileGraph.is_open())
693  {
694  // ERROR File Not Open
695  return -1;
696  }
697  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
698  { ofileGraph << e->getId() << "," << e->getNodePair().first->getId() << "," << e->getNodePair().second->getId() << "," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
699  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
700  ofileGraph.close();
701 
702  if (writeNodeFeat)
703  {
704  std::ofstream ofileNodeFeat;
705  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
706  ".csv";
707  ofileNodeFeat.open(completePathToFileNodeFeat);
708  if (!ofileNodeFeat.is_open())
709  {
710  // ERROR File Not Open
711  return -1;
712  }
713  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
714  { ofileNodeFeat << node->getId() << "," << node->getData() << std::endl; };
715  auto nodeSet = getNodeSet();
716  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
717  ofileNodeFeat.close();
718  }
719 
720  if (writeEdgeWeight)
721  {
722  std::ofstream ofileEdgeWeight;
723  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
724  ".csv";
725  ofileEdgeWeight.open(completePathToFileEdgeWeight);
726  if (!ofileEdgeWeight.is_open())
727  {
728  // ERROR File Not Open
729  return -1;
730  }
731  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
732  { 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; };
733 
734  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
735  ofileEdgeWeight.close();
736  }
737  return 0;
738  }
739 
740  template <typename T>
741  int Graph<T>::readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
742  {
743  std::ifstream ifileGraph;
744  std::ifstream ifileNodeFeat;
745  std::ifstream ifileEdgeWeight;
746  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
747  std::map<unsigned long, bool> edgeDirectedMap;
748  std::map<unsigned long, T> nodeFeatMap;
749  std::map<unsigned long, double> edgeWeightMap;
750  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
751  ifileGraph.open(completePathToFileGraph);
752  if (!ifileGraph.is_open())
753  {
754  // ERROR File Not Open
755  return -1;
756  }
757  char comma;
758  for (;;)
759  { /* loop continually */
760  unsigned long edgeId;
761  unsigned long nodeId1;
762  unsigned long nodeId2;
763  bool directed;
764  ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
765  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
766  edgeDirectedMap[edgeId] = directed;
767  if (ifileGraph.fail() || ifileGraph.eof())
768  break;
769  ifileGraph.ignore(128, '\n');
770  }
771  ifileGraph.close();
772 
773  if (readNodeFeat)
774  {
775  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
776  ".csv";
777  ifileNodeFeat.open(completePathToFileNodeFeat);
778  if (!ifileNodeFeat.is_open())
779  {
780  // ERROR File Not Open
781  return -1;
782  }
783  for (;;)
784  { /* loop continually */
785  unsigned long nodeId;
786  T nodeFeat;
787  ifileNodeFeat >> nodeId >> comma >> nodeFeat;
788  nodeFeatMap[nodeId] = nodeFeat;
789  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
790  break;
791  ifileNodeFeat.ignore(128, '\n');
792  }
793  ifileNodeFeat.close();
794  }
795 
796  if (readEdgeWeight)
797  {
798 
799  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
800  ".csv";
801  ifileEdgeWeight.open(completePathToFileEdgeWeight);
802  if (!ifileEdgeWeight.is_open())
803  {
804  // ERROR File Not Open
805  return -1;
806  }
807  for (;;)
808  { /* loop continually */
809  unsigned long edgeId;
810  double weight;
811  bool weighted;
812  ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
813  if (weighted)
814  {
815  edgeWeightMap[edgeId] = weight;
816  }
817  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
818  break;
819  ifileEdgeWeight.ignore(128, '\n');
820  }
821  ifileEdgeWeight.close();
822  }
823  std::map<unsigned long, Node<T> *> nodeMap;
824  for (auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
825  {
826  Node<T> *node1 = nullptr;
827  Node<T> *node2 = nullptr;
828  if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
829  {
830  //Create new Node
831  T feat;
832  if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
833  {
834  feat = nodeFeatMap.at(edgeIt->second.first);
835  }
836  node1 = new Node<T>(edgeIt->second.first, feat);
837  nodeMap[edgeIt->second.first] = node1;
838  }
839  else
840  {
841  node1 = nodeMap.at(edgeIt->second.first);
842  }
843  if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
844  {
845  //Create new Node
846  T feat;
847  if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
848  {
849  feat = nodeFeatMap.at(edgeIt->second.second);
850  }
851  node2 = new Node<T>(edgeIt->second.second, feat);
852  nodeMap[edgeIt->second.second] = node2;
853  }
854  else
855  {
856  node2 = nodeMap.at(edgeIt->second.second);
857  }
858 
859  if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
860  {
861  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
862  {
863  auto edge = new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
864  addEdge(edge);
865  }
866  else
867  {
868  auto edge = new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
869  addEdge(edge);
870  }
871  }
872  else
873  {
874  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
875  {
876  auto edge = new DirectedEdge<T>(edgeIt->first, *node1, *node2);
877  addEdge(edge);
878  }
879  else
880  {
881  auto edge = new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
882  addEdge(edge);
883  }
884  }
885  }
886 
887  return 0;
888  }
889 
890  template <typename T>
891  int Graph<T>::writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
892  {
893  std::ofstream ofileGraph;
894  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
895  ofileGraph.open(completePathToFileGraph);
896  if (!ofileGraph.is_open())
897  {
898  // ERROR File Not Open
899  return -1;
900  }
901  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
902  { 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; };
903  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
904  ofileGraph.close();
905 
906  if (writeNodeFeat)
907  {
908  std::ofstream ofileNodeFeat;
909  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
910  ".tsv";
911  ofileNodeFeat.open(completePathToFileNodeFeat);
912  if (!ofileNodeFeat.is_open())
913  {
914  // ERROR File Not Open
915  return -1;
916  }
917  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
918  { ofileNodeFeat << node->getId() << "\t" << node->getData() << std::endl; };
919  auto nodeSet = getNodeSet();
920  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
921  ofileNodeFeat.close();
922  }
923 
924  if (writeEdgeWeight)
925  {
926  std::ofstream ofileEdgeWeight;
927  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
928  ".tsv";
929  ofileEdgeWeight.open(completePathToFileEdgeWeight);
930  if (!ofileEdgeWeight.is_open())
931  {
932  // ERROR File Not Open
933  return -1;
934  }
935  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
936  { 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; };
937 
938  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
939  ofileEdgeWeight.close();
940  }
941  return 0;
942  }
943 
944  template <typename T>
945  int Graph<T>::readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
946  {
947  std::ifstream ifileGraph;
948  std::ifstream ifileNodeFeat;
949  std::ifstream ifileEdgeWeight;
950  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
951  std::map<unsigned long, bool> edgeDirectedMap;
952  std::map<unsigned long, T> nodeFeatMap;
953  std::map<unsigned long, double> edgeWeightMap;
954  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
955  ifileGraph.open(completePathToFileGraph);
956  if (!ifileGraph.is_open())
957  {
958  // ERROR File Not Open
959  return -1;
960  }
961  char tab;
962  for (;;)
963  { /* loop continually */
964  unsigned long edgeId;
965  unsigned long nodeId1;
966  unsigned long nodeId2;
967  bool directed;
968  ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
969  std::cout << edgeId << nodeId1 << nodeId2 << directed << std::endl;
970  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
971  edgeDirectedMap[edgeId] = directed;
972  if (ifileGraph.fail() || ifileGraph.eof())
973  break;
974  ifileGraph.ignore(128, '\n');
975  }
976  ifileGraph.close();
977 
978  if (readNodeFeat)
979  {
980  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
981  ".tsv";
982  ifileNodeFeat.open(completePathToFileNodeFeat);
983  if (!ifileNodeFeat.is_open())
984  {
985  // ERROR File Not Open
986  return -1;
987  }
988  for (;;)
989  { /* loop continually */
990  unsigned long nodeId;
991  T nodeFeat;
992  ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
993  nodeFeatMap[nodeId] = nodeFeat;
994  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
995  break;
996  ifileNodeFeat.ignore(128, '\n');
997  }
998  ifileNodeFeat.close();
999  }
1000 
1001  if (readEdgeWeight)
1002  {
1003 
1004  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
1005  ".tsv";
1006  ifileEdgeWeight.open(completePathToFileEdgeWeight);
1007  if (!ifileEdgeWeight.is_open())
1008  {
1009  // ERROR File Not Open
1010  return -1;
1011  }
1012  for (;;)
1013  { /* loop continually */
1014  unsigned long edgeId;
1015  double weight;
1016  bool weighted;
1017  ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
1018  if (weighted)
1019  {
1020  edgeWeightMap[edgeId] = weight;
1021  }
1022  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
1023  break;
1024  ifileEdgeWeight.ignore(128, '\n');
1025  }
1026  ifileEdgeWeight.close();
1027  }
1028  std::map<unsigned long, Node<T> *> nodeMap;
1029  for (auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
1030  {
1031  Node<T> *node1 = nullptr;
1032  Node<T> *node2 = nullptr;
1033  if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
1034  {
1035  //Create new Node
1036  T feat;
1037  if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
1038  {
1039  feat = nodeFeatMap.at(edgeIt->second.first);
1040  }
1041  node1 = new Node<T>(edgeIt->second.first, feat);
1042  nodeMap[edgeIt->second.first] = node1;
1043  }
1044  else
1045  {
1046  node1 = nodeMap.at(edgeIt->second.first);
1047  }
1048  if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
1049  {
1050  //Create new Node
1051  T feat;
1052  if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
1053  {
1054  feat = nodeFeatMap.at(edgeIt->second.second);
1055  }
1056  node2 = new Node<T>(edgeIt->second.second, feat);
1057  nodeMap[edgeIt->second.second] = node2;
1058  }
1059  else
1060  {
1061  node2 = nodeMap.at(edgeIt->second.second);
1062  }
1063 
1064  if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
1065  {
1066  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1067  {
1068  auto edge = new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1069  addEdge(edge);
1070  }
1071  else
1072  {
1073  auto edge = new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1074  addEdge(edge);
1075  }
1076  }
1077  else
1078  {
1079  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1080  {
1081  auto edge = new DirectedEdge<T>(edgeIt->first, *node1, *node2);
1082  addEdge(edge);
1083  }
1084  else
1085  {
1086  auto edge = new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
1087  addEdge(edge);
1088  }
1089  }
1090  }
1091 
1092  return 0;
1093  }
1094 
1095  template <typename T>
1096  const AdjacencyMatrix<T> Graph<T>::getAdjMatrix() const
1097  {
1098  AdjacencyMatrix<T> adj;
1099  auto edgeSetIt = edgeSet.begin();
1100  for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
1101  {
1102  if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
1103  {
1104  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(*edgeSetIt);
1105  addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
1106  }
1107  else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
1108  {
1109  const UndirectedEdge<T> *ud_edge = dynamic_cast<const UndirectedEdge<T> *>(*edgeSetIt);
1110  ;
1111  addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
1112  addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
1113  }
1114  else
1115  { //is a simple edge we cannot create adj matrix
1116  return adj;
1117  }
1118  }
1119  return adj;
1120  }
1121 
1122  template <typename T>
1123  const DijkstraResult Graph<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
1124  {
1125  DijkstraResult result;
1126  result.success = false;
1127  result.errorMessage = "";
1128  result.result = INF_DOUBLE;
1129  auto nodeSet = getNodeSet();
1130  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1131  {
1132  // check if source node exist in the graph
1133  result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
1134  return result;
1135  }
1136  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1137  {
1138  // check if target node exist in the graph
1139  result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
1140  return result;
1141  }
1142  const AdjacencyMatrix<T> adj = getAdjMatrix();
1143  // n denotes the number of vertices in graph
1144  int n = adj.size();
1145 
1146  // setting all the distances initially to INF_DOUBLE
1147  std::map<const Node<T> *, double> dist;
1148 
1149  for (auto elem : adj)
1150  {
1151  dist[elem.first] = INF_DOUBLE;
1152  }
1153 
1154  // creating a min heap using priority queue
1155  // first element of pair contains the distance
1156  // second element of pair contains the vertex
1157  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1158  std::greater<std::pair<double, const Node<T> *>>>
1159  pq;
1160 
1161  // pushing the source vertex 's' with 0 distance in min heap
1162  pq.push(std::make_pair(0.0, &source));
1163 
1164  // marking the distance of source as 0
1165  dist[&source] = 0;
1166 
1167  while (!pq.empty())
1168  {
1169  // second element of pair denotes the node / vertex
1170  const Node<T> *currentNode = pq.top().second;
1171 
1172  // first element of pair denotes the distance
1173  double currentDist = pq.top().first;
1174 
1175  pq.pop();
1176 
1177  // for all the reachable vertex from the currently exploring vertex
1178  // we will try to minimize the distance
1179  if (adj.find(currentNode) != adj.end())
1180  {
1181  for (std::pair<const Node<T> *, const Edge<T> *> elem : adj.at(currentNode))
1182  {
1183  // minimizing distances
1184  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1185  {
1186  if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1187  {
1188  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(elem.second);
1189  if (currentDist + dw_edge->getWeight() < dist[elem.first])
1190  {
1191  dist[elem.first] = currentDist + dw_edge->getWeight();
1192  pq.push(std::make_pair(dist[elem.first], elem.first));
1193  }
1194  }
1195  else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1196  {
1197  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
1198  if (currentDist + udw_edge->getWeight() < dist[elem.first])
1199  {
1200  dist[elem.first] = currentDist + udw_edge->getWeight();
1201  pq.push(std::make_pair(dist[elem.first], elem.first));
1202  }
1203  }
1204  else
1205  {
1206  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
1207  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1208  return result;
1209  }
1210  }
1211  else
1212  {
1213  // No Weighted Edge
1214  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1215  return result;
1216  }
1217  }
1218  }
1219  }
1220  if (dist[&target] != INF_DOUBLE)
1221  {
1222  result.success = true;
1223  result.errorMessage = "";
1224  result.result = dist[&target];
1225  return result;
1226  }
1227  result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
1228  result.result = -1;
1229  return result;
1230  }
1231 
1232  template <typename T>
1233  const std::vector<Node<T>> Graph<T>::breadth_first_search(const Node<T> &start) const
1234  {
1235  // vector to keep track of visited nodes
1236  std::vector<Node<T>> visited;
1237  auto nodeSet = getNodeSet();
1238  //check is exist node in the graph
1239  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1240  {
1241  return visited;
1242  }
1243  const AdjacencyMatrix<T> adj = getAdjMatrix();
1244  // queue that stores vertices that need to be further explored
1245  std::queue<const Node<T> *> tracker;
1246 
1247  // mark the starting node as visited
1248  visited.push_back(start);
1249  tracker.push(&start);
1250  while (!tracker.empty())
1251  {
1252  const Node<T> *node = tracker.front();
1253  tracker.pop();
1254  if (adj.find(node) != adj.end())
1255  {
1256  for (auto elem : adj.at(node))
1257  {
1258  // if the node is not visited then mark it as visited
1259  // and push it to the queue
1260  if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1261  {
1262  visited.push_back(*(elem.first));
1263  tracker.push(elem.first);
1264  }
1265  }
1266  }
1267  }
1268 
1269  return visited;
1270  }
1271 
1272  template <typename T>
1273  const std::vector<Node<T>> Graph<T>::depth_first_search(const Node<T> &start) const
1274  {
1275  // vector to keep track of visited nodes
1276  std::vector<Node<T>> visited;
1277  auto nodeSet = getNodeSet();
1278  //check is exist node in the graph
1279  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1280  {
1281  return visited;
1282  }
1283  const AdjacencyMatrix<T> adj = getAdjMatrix();
1284  std::function<void(const AdjacencyMatrix<T> &, const Node<T> &, std::vector<Node<T>> &)> explore;
1285  explore = [&explore](const AdjacencyMatrix<T> &adj, const Node<T> &node, std::vector<Node<T>> &visited) -> void
1286  {
1287  visited.push_back(node);
1288  if (adj.find(&node) != adj.end())
1289  {
1290  for (auto x : adj.at(&node))
1291  {
1292  if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1293  {
1294  explore(adj, *(x.first), visited);
1295  }
1296  }
1297  }
1298  };
1299  explore(adj, start, visited);
1300 
1301  return visited;
1302  }
1303 
1304  template <typename T>
1306  {
1307  if (!isDirectedGraph())
1308  {
1309  return false;
1310  }
1311  enum nodeStates : uint8_t
1312  {
1313  not_visited,
1314  in_stack,
1315  visited
1316  };
1317  auto nodeSet = this->getNodeSet();
1318  auto adjMatrix = this->getAdjMatrix();
1319 
1320  /* State of the node.
1321  *
1322  * It is a vector of "nodeStates" which represents the state node is in.
1323  * It can take only 3 values: "not_visited", "in_stack", and "visited".
1324  *
1325  * Initially, all nodes are in "not_visited" state.
1326  */
1327  std::map<unsigned long, nodeStates> state;
1328  for (auto node : nodeSet)
1329  {
1330  state[node->getId()] = not_visited;
1331  }
1332  int stateCounter = 0;
1333 
1334  // Start visiting each node.
1335  for (auto node : nodeSet)
1336  {
1337  // If a node is not visited, only then check for presence of cycle.
1338  // There is no need to check for presence of cycle for a visited
1339  // node as it has already been checked for presence of cycle.
1340  if (state[node->getId()] == not_visited)
1341  {
1342  // Check for cycle.
1343  std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &, const Node<T> *)> isCyclicDFSHelper;
1344  isCyclicDFSHelper = [this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states, const Node<T> *node)
1345  {
1346  // Add node "in_stack" state.
1347  states[node->getId()] = in_stack;
1348 
1349  // If the node has children, then recursively visit all children of the
1350  // node.
1351  auto const it = adjMatrix.find(node);
1352  if (it != adjMatrix.end())
1353  {
1354  for (auto child : it->second)
1355  {
1356  // If state of child node is "not_visited", evaluate that child
1357  // for presence of cycle.
1358  auto state_of_child = states.at((std::get<0>(child))->getId());
1359  if (state_of_child == not_visited)
1360  {
1361  if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1362  {
1363  return true;
1364  }
1365  }
1366  else if (state_of_child == in_stack)
1367  {
1368  // If child node was "in_stack", then that means that there
1369  // is a cycle in the graph. Return true for presence of the
1370  // cycle.
1371  return true;
1372  }
1373  }
1374  }
1375 
1376  // Current node has been evaluated for the presence of cycle and had no
1377  // cycle. Mark current node as "visited".
1378  states[node->getId()] = visited;
1379  // Return that current node didn't result in any cycles.
1380  return false;
1381  };
1382  if (isCyclicDFSHelper(adjMatrix, state, node))
1383  {
1384  return true;
1385  }
1386  }
1387  }
1388 
1389  // All nodes have been safely traversed, that means there is no cycle in
1390  // the graph. Return false.
1391  return false;
1392  }
1393 
1394  template <typename T>
1396  {
1397  if (!isDirectedGraph())
1398  {
1399  return false;
1400  }
1401  auto adjMatrix = this->getAdjMatrix();
1402  auto nodeSet = this->getNodeSet();
1403 
1404  std::map<unsigned long, unsigned int> indegree;
1405  for (auto node : nodeSet)
1406  {
1407  indegree[node->getId()] = 0;
1408  }
1409  // Calculate the indegree i.e. the number of incident edges to the node.
1410  for (auto const &list : adjMatrix)
1411  {
1412  auto children = list.second;
1413  for (auto const &child : children)
1414  {
1415  indegree[std::get<0>(child)->getId()]++;
1416  }
1417  }
1418 
1419  std::queue<const Node<T> *> can_be_solved;
1420  for (auto node : nodeSet)
1421  {
1422  // If a node doesn't have any input edges, then that node will
1423  // definately not result in a cycle and can be visited safely.
1424  if (!indegree[node->getId()])
1425  {
1426  can_be_solved.emplace(&(*node));
1427  }
1428  }
1429 
1430  // Vertices that need to be traversed.
1431  auto remain = this->getNodeSet().size();
1432  // While there are safe nodes that we can visit.
1433  while (!can_be_solved.empty())
1434  {
1435  auto solved = can_be_solved.front();
1436  // Visit the node.
1437  can_be_solved.pop();
1438  // Decrease number of nodes that need to be traversed.
1439  remain--;
1440 
1441  // Visit all the children of the visited node.
1442  auto it = adjMatrix.find(solved);
1443  if (it != adjMatrix.end())
1444  {
1445  for (auto child : it->second)
1446  {
1447  // Check if we can visited the node safely.
1448  if (--indegree[std::get<0>(child)->getId()] == 0)
1449  {
1450  // if node can be visited safely, then add that node to
1451  // the visit queue.
1452  can_be_solved.emplace(std::get<0>(child));
1453  }
1454  }
1455  }
1456  }
1457 
1458  // If there are still nodes that we can't visit, then it means that
1459  // there is a cycle and return true, else return false.
1460  return !(remain == 0);
1461  }
1462 
1463  template <typename T>
1465  {
1466  auto edgeSet = this->getEdgeSet();
1467  for (auto edge : edgeSet)
1468  {
1469  if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1470  {
1471  //Found Undirected Edge
1472  return false;
1473  }
1474  }
1475  //No Undirected Edge
1476  return true;
1477  }
1478 
1479  template <typename T>
1480  int Graph<T>::writeToFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
1481  {
1482  if (format == InputOutputFormat::STANDARD_CSV)
1483  {
1484  return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1485  }
1486  else if (format == InputOutputFormat::STANDARD_TSV)
1487  {
1488  return writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1489  }
1490  else
1491  {
1492  //OUTPUT FORMAT NOT RECOGNIZED
1493  return -1;
1494  }
1495  }
1496 
1497  template <typename T>
1498  int Graph<T>::readFromFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
1499  {
1500  if (format == InputOutputFormat::STANDARD_CSV)
1501  {
1502  return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1503  }
1504  else if (format == InputOutputFormat::STANDARD_TSV)
1505  {
1506  return readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1507  }
1508  else
1509  {
1510  //OUTPUT FORMAT NOT RECOGNIZED
1511  return -1;
1512  }
1513  }
1514 
1515  //ostream overload
1516  template <typename T>
1517  std::ostream &operator<<(std::ostream &os, const Node<T> &node)
1518  {
1519  os << "Node: {\n"
1520  << " Id:\t" << node.id << "\n Data:\t" << node.data << "\n}";
1521  return os;
1522  }
1523 
1524  template <typename T>
1525  std::ostream &operator<<(std::ostream &os, const Edge<T> &edge)
1526  {
1527  os << "((Node: " << edge.nodePair.first->getId() << ")) ?----- |Edge: " << edge.id << "|-----? ((Node: " << edge.nodePair.second->getId() << "))";
1528  return os;
1529  }
1530 
1531  template <typename T>
1532  std::ostream &operator<<(std::ostream &os, const DirectedEdge<T> &edge)
1533  {
1534  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getTo().getId() << "))";
1535  return os;
1536  }
1537 
1538  template <typename T>
1539  std::ostream &operator<<(std::ostream &os, const UndirectedEdge<T> &edge)
1540  {
1541  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
1542  return os;
1543  }
1544 
1545  template <typename T>
1546  std::ostream &operator<<(std::ostream &os, const DirectedWeightedEdge<T> &edge)
1547  {
1548  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getTo().getId() << "))";
1549  return os;
1550  }
1551 
1552  template <typename T>
1553  std::ostream &operator<<(std::ostream &os, const UndirectedWeightedEdge<T> &edge)
1554  {
1555  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
1556  return os;
1557  }
1558 
1559  template <typename T>
1560  std::ostream &operator<<(std::ostream &os, const AdjacencyMatrix<T> &adj)
1561  {
1562  os << "Adjacency Matrix:\n";
1563  auto it = adj.begin();
1564  unsigned long max_column = 0;
1565  for (it; it != adj.end(); ++it)
1566  {
1567  if (it->second.size() > max_column)
1568  {
1569  max_column = it->second.size();
1570  }
1571  }
1572  if (max_column == 0)
1573  {
1574  os << "ERROR in Print\n";
1575  return os;
1576  }
1577  else
1578  {
1579  it = adj.begin();
1580  os << "|--|";
1581  for (int i = 0; i < max_column; i++)
1582  {
1583  os << "-----|";
1584  }
1585  os << "\n";
1586  for (it; it != adj.end(); ++it)
1587  {
1588  os << "|N" << it->first->getId() << "|";
1589  auto it2 = it->second.begin();
1590  for (it2; it2 != it->second.end(); ++it2)
1591  {
1592  os << "N" << it2->first->getId() << ",E" << it2->second->getId() << "|";
1593  }
1594  os << "\n|--|";
1595  for (int i = 0; i < max_column; i++)
1596  {
1597  os << "-----|";
1598  }
1599  os << "\n";
1600  }
1601  }
1602  return os;
1603  }
1604 
1605 } // namespace CXXGRAPH
1606 #endif // __CXXGRAPH_H__
Definition: Graph.hpp:232
Definition: Graph.hpp:346
Definition: Graph.hpp:160
Definition: Graph.hpp:466
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:1273
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:1395
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:1480
bool isDirectedGraph() const
This function checks if a graph is directed.
Definition: Graph.hpp:1464
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:1123
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:1305
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:1498
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:1233
E_InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
Definition: Graph.hpp:478
@ STANDARD_CSV
A standard csv format.
Definition: Graph.hpp:479
@ STANDARD_TSV
A standard tsv format.
Definition: Graph.hpp:480
Definition: Graph.hpp:74
Definition: Graph.hpp:289
Definition: Graph.hpp:406
Definition: Graph.hpp:122
Definition: Graph.hpp:66