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