CXXGraph  0.0.6
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 <queue>
13 #include <string>
14 #include <functional>
15 #include <fstream>
16 
17 namespace CXXGRAPH
18 {
19  //STRING ERROR CONST EXPRESSION
20  constexpr char ERR_NO_DIR_OR_UNDIR_EDGE[] = "Edge are neither Directed neither Undirected";
21  constexpr char ERR_NO_WEIGHTED_EDGE[] = "Edge are not Weighted";
22  constexpr char ERR_DIJ_TARGET_NODE_NOT_REACHABLE[] = "Target Node not Reachable";
23  constexpr char ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH[] = "Target Node not inside Graph";
24  constexpr char ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH[] = "Source Node not inside Graph";
26  constexpr double INF_DOUBLE = std::numeric_limits<double>::max();
27  template <typename T>
28  class Node;
29  template <typename T>
30  class Edge;
31  template <typename T>
32  class DirectedEdge;
33  template <typename T>
34  class UndirectedEdge;
35  template <typename T>
36  class DirectedWeightedEdge;
37  template <typename T>
38  class UndirectedWeightedEdge;
39  template <typename T>
40  class Graph;
41 
42  class Weighted;
43 
44  template <typename T>
45  using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *, const Edge<T> *>>>;
46 
47  template <typename T>
48  std::ostream &operator<<(std::ostream &o, const Node<T> &node);
49  template <typename T>
50  std::ostream &operator<<(std::ostream &o, const Edge<T> &edge);
51  template <typename T>
52  std::ostream &operator<<(std::ostream &o, const DirectedEdge<T> &edge);
53  template <typename T>
54  std::ostream &operator<<(std::ostream &o, const UndirectedEdge<T> &edge);
55  template <typename T>
56  std::ostream &operator<<(std::ostream &o, const DirectedWeightedEdge<T> &edge);
57  template <typename T>
58  std::ostream &operator<<(std::ostream &o, const UndirectedWeightedEdge<T> &edge);
59  template <typename T>
60  std::ostream &operator<<(std::ostream &o, const Graph<T> &graph);
61  template <typename T>
62  std::ostream &operator<<(std::ostream &o, const AdjacencyMatrix<T> &adj);
63 
64  typedef struct DijkstraResult_struct
65  {
66  bool success; // TRUE if the function does not return error, FALSE otherwise
67  std::string errorMessage; //message of error
68  double result; //result (valid only if success is TRUE)
70 
71  template <typename T>
72  class Node
73  {
74  private:
75  unsigned long id;
76  T data;
77 
78  public:
79  Node(const unsigned long id, const T &data);
80  ~Node() = default;
81  const unsigned long &getId() const;
82  const T &getData() const;
83  //operator
84  bool operator==(const Node<T> &b) const;
85  bool operator<(const Node<T> &b) const;
86  friend std::ostream &operator<<<>(std::ostream &os, const Node<T> &node);
87  };
88 
89  template <typename T>
90  Node<T>::Node(const unsigned long id, const T &data)
91  {
92  this->id = id;
93  this->data = data;
94  }
95 
96  template <typename T>
97  const unsigned long &Node<T>::getId() const
98  {
99  return id;
100  }
101 
102  template <typename T>
103  const T &Node<T>::getData() const
104  {
105  return data;
106  }
107 
108  template <typename T>
109  bool Node<T>::operator==(const Node<T> &b) const
110  {
111  return (this->id == b.id && this->data == b.data);
112  }
113 
114  template <typename T>
115  bool Node<T>::operator<(const Node<T> &b) const
116  {
117  return (this->id < b.id);
118  }
119 
120  class Weighted
121  {
122  private:
123  double weight;
124 
125  public:
126  Weighted();
127  Weighted(const double weight);
128  virtual ~Weighted() = default;
129  double getWeight() const;
130  void setWeight(const double weight);
131  };
132 
133  //inline because the implementation of non-template function in header file
134  inline Weighted::Weighted()
135  {
136  weight = 0.0;
137  }
138 
139  //inline because the implementation of non-template function in header file
140  inline Weighted::Weighted(const double weight)
141  {
142  this->weight = weight;
143  }
144 
145  //inline because the implementation of non-template function in header file
146  inline double Weighted::getWeight() const
147  {
148  return weight;
149  }
150 
151  //inline because the implementation of non-template function in header file
152  inline void Weighted::setWeight(const double weight)
153  {
154  this->weight = weight;
155  }
156 
157  template <typename T>
158  class Edge
159  {
160  private:
161  unsigned long id;
162  std::pair<const Node<T> *, const Node<T> *> nodePair;
163 
164  public:
165  Edge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
166  Edge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
167  virtual ~Edge() = default;
168  const unsigned long &getId() const;
169  const std::pair<const Node<T> *, const Node<T> *> &getNodePair() const;
170  virtual const std::optional<bool> isDirected() const;
171  virtual const std::optional<bool> isWeighted() const;
172  //operator
173  virtual bool operator==(const Edge<T> &b) const;
174  bool operator<(const Edge<T> &b) const;
175  //operator DirectedEdge<T>() const { return DirectedEdge<T>(id, nodePair); }
176  //operator UndirectedEdge<T>() const { return UndirectedEdge<T>(id, nodePair); }
177 
178  friend std::ostream &operator<<<>(std::ostream &os, const Edge<T> &edge);
179  };
180 
181  template <typename T>
182  Edge<T>::Edge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : nodePair(&node1, &node2)
183  {
184  this->id = id;
185  }
186 
187  template <typename T>
188  Edge<T>::Edge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : nodePair(nodepair)
189  {
190  this->id = id;
191  }
192 
193  template <typename T>
194  const unsigned long &Edge<T>::getId() const
195  {
196  return id;
197  }
198 
199  template <typename T>
200  const std::pair<const Node<T> *, const Node<T> *> &Edge<T>::getNodePair() const
201  {
202  return nodePair;
203  }
204 
205  template <typename T>
206  const std::optional<bool> Edge<T>::isDirected() const
207  {
208  return std::nullopt;
209  }
210 
211  template <typename T>
212  const std::optional<bool> Edge<T>::isWeighted() const
213  {
214  return std::nullopt;
215  }
216 
217  template <typename T>
218  bool Edge<T>::operator==(const Edge<T> &b) const
219  {
220  return (this->id == b.id && this->nodePair == b.nodePair);
221  }
222 
223  template <typename T>
224  bool Edge<T>::operator<(const Edge<T> &b) const
225  {
226  return (this->id < b.id);
227  }
228 
229  template <typename T>
230  class DirectedEdge : public Edge<T>
231  {
232  public:
233  DirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
234  DirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
235  DirectedEdge(const Edge<T> &edge);
236  virtual ~DirectedEdge() = default;
237  const Node<T> &getFrom() const;
238  const Node<T> &getTo() const;
239  const std::optional<bool> isDirected() const override;
240  virtual const std::optional<bool> isWeighted() const override;
241  //operator
242  explicit operator UndirectedEdge<T>() const { return UndirectedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair()); }
243 
244  friend std::ostream &operator<<<>(std::ostream &os, const DirectedEdge<T> &edge);
245  };
246 
247  template <typename T>
248  DirectedEdge<T>::DirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : Edge<T>(id, node1, node2)
249  {
250  }
251 
252  template <typename T>
253  DirectedEdge<T>::DirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
254  {
255  }
256 
257  template <typename T>
258  DirectedEdge<T>::DirectedEdge(const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
259  {
260  }
261 
262  template <typename T>
263  const Node<T> &DirectedEdge<T>::getFrom() const
264  {
265  return *(Edge<T>::getNodePair().first);
266  }
267 
268  template <typename T>
269  const Node<T> &DirectedEdge<T>::getTo() const
270  {
271  return *(Edge<T>::getNodePair().second);
272  }
273 
274  template <typename T>
275  const std::optional<bool> DirectedEdge<T>::isDirected() const
276  {
277  return true;
278  }
279 
280  template <typename T>
281  const std::optional<bool> DirectedEdge<T>::isWeighted() const
282  {
283  return false;
284  }
285 
286  template <typename T>
287  class UndirectedEdge : public Edge<T>
288  {
289  public:
290  UndirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2);
291  UndirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair);
292  UndirectedEdge(const Edge<T> &edge);
293  virtual ~UndirectedEdge() = default;
294  const Node<T> &getNode1() const;
295  const Node<T> &getNode2() const;
296  const std::optional<bool> isDirected() const override;
297  const std::optional<bool> isWeighted() const override;
298  //operator
299  explicit operator DirectedEdge<T>() const { return DirectedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair()); }
300 
301  friend std::ostream &operator<<<>(std::ostream &os, const UndirectedEdge<T> &edge);
302  };
303 
304  template <typename T>
305  UndirectedEdge<T>::UndirectedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2) : Edge<T>(id, node1, node2)
306  {
307  }
308 
309  template <typename T>
310  UndirectedEdge<T>::UndirectedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
311  {
312  }
313 
314  template <typename T>
315  UndirectedEdge<T>::UndirectedEdge(const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
316  {
317  }
318 
319  template <typename T>
320  const Node<T> &UndirectedEdge<T>::getNode1() const
321  {
322  return *(Edge<T>::getNodePair().first);
323  }
324 
325  template <typename T>
326  const Node<T> &UndirectedEdge<T>::getNode2() const
327  {
328  return *(Edge<T>::getNodePair().second);
329  }
330 
331  template <typename T>
332  const std::optional<bool> UndirectedEdge<T>::isDirected() const
333  {
334  return false;
335  }
336 
337  template <typename T>
338  const std::optional<bool> UndirectedEdge<T>::isWeighted() const
339  {
340  return false;
341  }
342 
343  template <typename T>
344  class DirectedWeightedEdge : public DirectedEdge<T>, public Weighted
345  {
346  public:
347  DirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight);
348  DirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight);
349  DirectedWeightedEdge(const DirectedEdge<T> &edge, const double weight);
350  DirectedWeightedEdge(const Edge<T> &edge, const double weight);
352  DirectedWeightedEdge(const Edge<T> &edge);
354  virtual ~DirectedWeightedEdge() = default;
355  const std::optional<bool> isWeighted() const override;
356  //operator
357  explicit operator UndirectedWeightedEdge<T>() const { return UndirectedWeightedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair(), Weighted::getWeight()); }
358 
359  friend std::ostream &operator<<<>(std::ostream &os, const DirectedWeightedEdge<T> &edge);
360  };
361 
362  template <typename T>
363  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)
364  {
365  }
366 
367  template <typename T>
368  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)
369  {
370  }
371 
372  template <typename T>
373  DirectedWeightedEdge<T>::DirectedWeightedEdge(const DirectedEdge<T> &edge, const double weight) : DirectedEdge<T>(edge), Weighted(weight)
374  {
375  }
376 
377  template <typename T>
378  DirectedWeightedEdge<T>::DirectedWeightedEdge(const Edge<T> &edge, const double weight) : DirectedEdge<T>(edge), Weighted(weight)
379  {
380  }
381 
382  template <typename T>
383  DirectedWeightedEdge<T>::DirectedWeightedEdge(const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
384  {
385  }
386 
387  template <typename T>
388  DirectedWeightedEdge<T>::DirectedWeightedEdge(const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
389  {
390  }
391 
392  template <typename T>
393  DirectedWeightedEdge<T>::DirectedWeightedEdge(const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
394  {
395  }
396 
397  template <typename T>
398  const std::optional<bool> DirectedWeightedEdge<T>::isWeighted() const
399  {
400  return true;
401  }
402 
403  template <typename T>
405  {
406  public:
407  UndirectedWeightedEdge(const unsigned long id, const Node<T> &node1, const Node<T> &node2, const double weight);
408  UndirectedWeightedEdge(const unsigned long id, const std::pair<const Node<T> *, const Node<T> *> &nodepair, const double weight);
409  UndirectedWeightedEdge(const UndirectedEdge<T> &edge, const double weight);
410  UndirectedWeightedEdge(const Edge<T> &edge, const double weight);
412  UndirectedWeightedEdge(const Edge<T> &edge);
414  virtual ~UndirectedWeightedEdge() = default;
415  const std::optional<bool> isWeighted() const override;
416  //operator
417  explicit operator DirectedWeightedEdge<T>() const { return DirectedWeightedEdge<T>(Edge<T>::getId(), Edge<T>::getNodePair(), Weighted::getWeight()); }
418 
419  friend std::ostream &operator<<<>(std::ostream &os, const UndirectedWeightedEdge<T> &edge);
420  };
421 
422  template <typename T>
423  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)
424  {
425  }
426 
427  template <typename T>
428  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)
429  {
430  }
431 
432  template <typename T>
433  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const UndirectedEdge<T> &edge, const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
434  {
435  }
436 
437  template <typename T>
438  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const Edge<T> &edge, const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
439  {
440  }
441 
442  template <typename T>
443  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
444  {
445  }
446 
447  template <typename T>
448  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
449  {
450  }
451 
452  template <typename T>
453  UndirectedWeightedEdge<T>::UndirectedWeightedEdge(const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
454  {
455  }
456 
457  template <typename T>
458  const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted() const
459  {
460  return true;
461  }
462 
463  template <typename T>
464  class Graph
465  {
466  private:
467  std::set<const Edge<T> *> edgeSet;
468  void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const;
469  int writeToStandardFile(std::string OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
470 
471  public:
472  typedef enum E_OutputFormat
473  {
474  STANDARD,
475  OUT_1,
476  OUT_2
477  } OutputFormat;
478 
479  Graph() = default;
480  Graph(const std::set<const Edge<T> *> &edgeSet);
481  ~Graph() = default;
482  const std::set<const Edge<T> *> &getEdgeSet() const;
483  void setEdgeSet(std::set<const Edge<T> *> &edgeSet);
484  void addEdge(const Edge<T> &edge);
485  void removeEdge(unsigned long edgeId);
486  const std::set<const Node<T> *> getNodeSet() const;
487  const std::optional<const Edge<T> *> getEdge(unsigned long edgeId) const;
488  /*This function generate a list of adjacency matrix with every element of the matrix
489  * contain the node where is directed the link and the Edge corrispondent to the link
490  */
491  const AdjacencyMatrix<T> getAdjMatrix() const;
503  const DijkstraResult dijkstra(const Node<T> &source, const Node<T> &target) const;
513  const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const;
523  const std::vector<Node<T>> depth_first_search(const Node<T> &start) const;
524 
532  const bool isCyclicDirectedGraphDFS() const;
533 
541  const bool isCyclicDirectedGraphBFS() const;
542 
549  const bool isDirectedGraph() const;
550 
562  int writeToFile(OutputFormat format = OutputFormat::STANDARD, std::string OFileName = "graph.csv", bool compress = false, bool writeNodeFeat = false, bool writeEdgeWeight = false) const;
563 
564  friend std::ostream &operator<<<>(std::ostream &os, const Graph<T> &graph);
565  friend std::ostream &operator<<<>(std::ostream &os, const AdjacencyMatrix<T> &adj);
566  };
567 
568  template <typename T>
569  Graph<T>::Graph(const std::set<const Edge<T> *> &edgeSet)
570  {
571  this->edgeSet = edgeSet;
572  }
573 
574  template <typename T>
575  const std::set<const Edge<T> *> &Graph<T>::getEdgeSet() const
576  {
577  return edgeSet;
578  }
579 
580  template <typename T>
581  void Graph<T>::setEdgeSet(std::set<const Edge<T> *> &edgeSet)
582  {
583  this->edgeSet = edgeSet;
584  }
585 
586  template <typename T>
587  void Graph<T>::addEdge(const Edge<T> &edge)
588  {
589  edgeSet.insert(&edge);
590  }
591 
592  template <typename T>
593  void Graph<T>::removeEdge(unsigned long edgeId)
594  {
595  auto edgeOpt = getEdge(edgeId);
596  if (edgeOpt.has_value())
597  {
598  edgeSet.erase(edgeSet.find(edgeOpt.value()));
599  }
600  }
601 
602  template <typename T>
603  const std::set<const Node<T> *> Graph<T>::getNodeSet() const
604  {
605  std::set<const Node<T> *> nodeSet;
606  for (auto edge : edgeSet)
607  {
608  nodeSet.insert(edge->getNodePair().first);
609  nodeSet.insert(edge->getNodePair().second);
610  }
611  return nodeSet;
612  }
613 
614  template <typename T>
615  const std::optional<const Edge<T> *> Graph<T>::getEdge(unsigned long edgeId) const
616  {
617 
618  auto it = edgeSet.begin();
619  for (it; it != edgeSet.end(); ++it)
620  {
621  if ((*it)->getId() == edgeId)
622  {
623  return *it;
624  }
625  }
626 
627  return std::nullopt;
628  }
629 
630  template <typename T>
631  void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const
632  {
633  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
634  adjMatrix[nodeFrom].push_back(elem);
635 
636  //adjMatrix[nodeFrom.getId()].push_back(std::make_pair<const Node<T>,const Edge<T>>(nodeTo, edge));
637  }
638 
639  template <typename T>
640  int Graph<T>::writeToStandardFile(std::string OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
641  {
642  std::ofstream ofileGraph;
643  ofileGraph.open(OFileName);
644  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
645  { ofileGraph << e->getId() << "," << e->getNodePair().first->getId() << "," << e->getNodePair().second->getId() << std::endl; };
646  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
647  ofileGraph.close();
648 
649  if (writeNodeFeat)
650  {
651  std::ofstream ofileNodeFeat;
652  ofileNodeFeat.open("NodeFeat_" + OFileName);
653  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
654  { ofileNodeFeat << node->getId() << "," << node->getData() << std::endl; };
655  auto nodeSet = getNodeSet();
656  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
657  ofileNodeFeat.close();
658  }
659 
660  if (writeEdgeWeight)
661  {
662  std::ofstream ofileEdgeWeight;
663  ofileEdgeWeight.open("EdgeWeight_" + OFileName);
664  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
665  { ofileEdgeWeight << e->getId() << "," << (e->isWeighted().has_value() && e->isWeighted().value() ? (dynamic_cast<const Weighted *>(e))->getWeight() : 0.0) << std::endl; };
666 
667  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
668  ofileEdgeWeight.close();
669  }
670  return 0;
671  }
672 
673  template <typename T>
674  const AdjacencyMatrix<T> Graph<T>::getAdjMatrix() const
675  {
676  AdjacencyMatrix<T> adj;
677  auto edgeSetIt = edgeSet.begin();
678  for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
679  {
680  if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
681  {
682  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(*edgeSetIt);
683  addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
684  }
685  else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
686  {
687  const UndirectedEdge<T> *ud_edge = dynamic_cast<const UndirectedEdge<T> *>(*edgeSetIt);
688  ;
689  addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
690  addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
691  }
692  else
693  { //is a simple edge we cannot create adj matrix
694  return adj;
695  }
696  }
697  return adj;
698  }
699 
700  template <typename T>
701  const DijkstraResult Graph<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
702  {
703  DijkstraResult result;
704  result.success = false;
705  result.errorMessage = "";
706  result.result = INF_DOUBLE;
707  auto nodeSet = getNodeSet();
708  if (nodeSet.find(&source) == nodeSet.end())
709  {
710  // check if source node exist in the graph
711  result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
712  return result;
713  }
714  if (nodeSet.find(&target) == nodeSet.end())
715  {
716  // check if target node exist in the graph
717  result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
718  return result;
719  }
720  const AdjacencyMatrix<T> adj = getAdjMatrix();
721  // n denotes the number of vertices in graph
722  int n = adj.size();
723 
724  // setting all the distances initially to INF_DOUBLE
725  std::map<const Node<T> *, double> dist;
726 
727  for (auto elem : adj)
728  {
729  dist[elem.first] = INF_DOUBLE;
730  }
731 
732  // creating a min heap using priority queue
733  // first element of pair contains the distance
734  // second element of pair contains the vertex
735  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
736  std::greater<std::pair<double, const Node<T> *>>>
737  pq;
738 
739  // pushing the source vertex 's' with 0 distance in min heap
740  pq.push(std::make_pair(0.0, &source));
741 
742  // marking the distance of source as 0
743  dist[&source] = 0;
744 
745  while (!pq.empty())
746  {
747  // second element of pair denotes the node / vertex
748  const Node<T> *currentNode = pq.top().second;
749 
750  // first element of pair denotes the distance
751  double currentDist = pq.top().first;
752 
753  pq.pop();
754 
755  // for all the reachable vertex from the currently exploring vertex
756  // we will try to minimize the distance
757  if (adj.find(currentNode) != adj.end())
758  {
759  for (std::pair<const Node<T> *, const Edge<T> *> elem : adj.at(currentNode))
760  {
761  // minimizing distances
762  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
763  {
764  if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
765  {
766  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(elem.second);
767  if (currentDist + dw_edge->getWeight() < dist[elem.first])
768  {
769  dist[elem.first] = currentDist + dw_edge->getWeight();
770  pq.push(std::make_pair(dist[elem.first], elem.first));
771  }
772  }
773  else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
774  {
775  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
776  if (currentDist + udw_edge->getWeight() < dist[elem.first])
777  {
778  dist[elem.first] = currentDist + udw_edge->getWeight();
779  pq.push(std::make_pair(dist[elem.first], elem.first));
780  }
781  }
782  else
783  {
784  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
785  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
786  return result;
787  }
788  }
789  else
790  {
791  // No Weighted Edge
792  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
793  return result;
794  }
795  }
796  }
797  }
798  if (dist[&target] != INF_DOUBLE)
799  {
800  result.success = true;
801  result.errorMessage = "";
802  result.result = dist[&target];
803  return result;
804  }
805  result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
806  result.result = -1;
807  return result;
808  }
809 
810  template <typename T>
811  const std::vector<Node<T>> Graph<T>::breadth_first_search(const Node<T> &start) const
812  {
813  // vector to keep track of visited nodes
814  std::vector<Node<T>> visited;
815  auto nodeSet = getNodeSet();
816  //check is exist node in the graph
817  if (nodeSet.find(&start) == nodeSet.end())
818  {
819  return visited;
820  }
821  const AdjacencyMatrix<T> adj = getAdjMatrix();
822  // queue that stores vertices that need to be further explored
823  std::queue<const Node<T> *> tracker;
824 
825  // mark the starting node as visited
826  visited.push_back(start);
827  tracker.push(&start);
828  while (!tracker.empty())
829  {
830  const Node<T> *node = tracker.front();
831  tracker.pop();
832  if (adj.find(node) != adj.end())
833  {
834  for (auto elem : adj.at(node))
835  {
836  // if the node is not visited then mark it as visited
837  // and push it to the queue
838  if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
839  {
840  visited.push_back(*(elem.first));
841  tracker.push(elem.first);
842  }
843  }
844  }
845  }
846 
847  return visited;
848  }
849 
850  template <typename T>
851  const std::vector<Node<T>> Graph<T>::depth_first_search(const Node<T> &start) const
852  {
853  // vector to keep track of visited nodes
854  std::vector<Node<T>> visited;
855  auto nodeSet = getNodeSet();
856  //check is exist node in the graph
857  if (nodeSet.find(&start) == nodeSet.end())
858  {
859  return visited;
860  }
861  const AdjacencyMatrix<T> adj = getAdjMatrix();
862  std::function<void(const AdjacencyMatrix<T> &, const Node<T> &, std::vector<Node<T>> &)> explore;
863  explore = [&explore](const AdjacencyMatrix<T> &adj, const Node<T> &node, std::vector<Node<T>> &visited) -> void
864  {
865  visited.push_back(node);
866  if (adj.find(&node) != adj.end())
867  {
868  for (auto x : adj.at(&node))
869  {
870  if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
871  {
872  explore(adj, *(x.first), visited);
873  }
874  }
875  }
876  };
877  explore(adj, start, visited);
878 
879  return visited;
880  }
881 
882  template <typename T>
884  {
885  if (!isDirectedGraph())
886  {
887  return false;
888  }
889  enum nodeStates : uint8_t
890  {
891  not_visited,
892  in_stack,
893  visited
894  };
895  auto nodeSet = this->getNodeSet();
896  auto adjMatrix = this->getAdjMatrix();
897 
898  /* State of the node.
899  *
900  * It is a vector of "nodeStates" which represents the state node is in.
901  * It can take only 3 values: "not_visited", "in_stack", and "visited".
902  *
903  * Initially, all nodes are in "not_visited" state.
904  */
905  std::map<unsigned long, nodeStates> state;
906  for (auto node : nodeSet)
907  {
908  state[node->getId()] = not_visited;
909  }
910  int stateCounter = 0;
911 
912  // Start visiting each node.
913  for (auto node : nodeSet)
914  {
915  // If a node is not visited, only then check for presence of cycle.
916  // There is no need to check for presence of cycle for a visited
917  // node as it has already been checked for presence of cycle.
918  if (state[node->getId()] == not_visited)
919  {
920  // Check for cycle.
921  std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &, const Node<T> *)> isCyclicDFSHelper;
922  isCyclicDFSHelper = [this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states, const Node<T> *node)
923  {
924  // Add node "in_stack" state.
925  states[node->getId()] = in_stack;
926 
927  // If the node has children, then recursively visit all children of the
928  // node.
929  auto const it = adjMatrix.find(node);
930  if (it != adjMatrix.end())
931  {
932  for (auto child : it->second)
933  {
934  // If state of child node is "not_visited", evaluate that child
935  // for presence of cycle.
936  auto state_of_child = states.at((std::get<0>(child))->getId());
937  if (state_of_child == not_visited)
938  {
939  if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
940  {
941  return true;
942  }
943  }
944  else if (state_of_child == in_stack)
945  {
946  // If child node was "in_stack", then that means that there
947  // is a cycle in the graph. Return true for presence of the
948  // cycle.
949  return true;
950  }
951  }
952  }
953 
954  // Current node has been evaluated for the presence of cycle and had no
955  // cycle. Mark current node as "visited".
956  states[node->getId()] = visited;
957  // Return that current node didn't result in any cycles.
958  return false;
959  };
960  if (isCyclicDFSHelper(adjMatrix, state, node))
961  {
962  return true;
963  }
964  }
965  }
966 
967  // All nodes have been safely traversed, that means there is no cycle in
968  // the graph. Return false.
969  return false;
970  }
971 
972  template <typename T>
974  {
975  if (!isDirectedGraph())
976  {
977  return false;
978  }
979  auto adjMatrix = this->getAdjMatrix();
980  auto nodeSet = this->getNodeSet();
981 
982  std::map<unsigned long, unsigned int> indegree;
983  for (auto node : nodeSet)
984  {
985  indegree[node->getId()] = 0;
986  }
987  // Calculate the indegree i.e. the number of incident edges to the node.
988  for (auto const &list : adjMatrix)
989  {
990  auto children = list.second;
991  for (auto const &child : children)
992  {
993  indegree[std::get<0>(child)->getId()]++;
994  }
995  }
996 
997  std::queue<const Node<T> *> can_be_solved;
998  for (auto node : nodeSet)
999  {
1000  // If a node doesn't have any input edges, then that node will
1001  // definately not result in a cycle and can be visited safely.
1002  if (!indegree[node->getId()])
1003  {
1004  can_be_solved.emplace(&(*node));
1005  }
1006  }
1007 
1008  // Vertices that need to be traversed.
1009  auto remain = this->getNodeSet().size();
1010  // While there are safe nodes that we can visit.
1011  while (!can_be_solved.empty())
1012  {
1013  auto solved = can_be_solved.front();
1014  // Visit the node.
1015  can_be_solved.pop();
1016  // Decrease number of nodes that need to be traversed.
1017  remain--;
1018 
1019  // Visit all the children of the visited node.
1020  auto it = adjMatrix.find(solved);
1021  if (it != adjMatrix.end())
1022  {
1023  for (auto child : it->second)
1024  {
1025  // Check if we can visited the node safely.
1026  if (--indegree[std::get<0>(child)->getId()] == 0)
1027  {
1028  // if node can be visited safely, then add that node to
1029  // the visit queue.
1030  can_be_solved.emplace(std::get<0>(child));
1031  }
1032  }
1033  }
1034  }
1035 
1036  // If there are still nodes that we can't visit, then it means that
1037  // there is a cycle and return true, else return false.
1038  return !(remain == 0);
1039  }
1040 
1041  template <typename T>
1042  const bool Graph<T>::isDirectedGraph() const
1043  {
1044  auto edgeSet = this->getEdgeSet();
1045  for (auto edge : edgeSet)
1046  {
1047  if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1048  {
1049  //Found Undirected Edge
1050  return false;
1051  }
1052  }
1053  //No Undirected Edge
1054  return true;
1055  }
1056 
1057  template <typename T>
1058  int Graph<T>::writeToFile(OutputFormat format, std::string OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
1059  {
1060  if (format == OutputFormat::STANDARD)
1061  {
1062  return writeToStandardFile(OFileName, compress, writeNodeFeat, writeEdgeWeight);
1063  }
1064  else
1065  {
1066  //OUTPUT FORMAT NOT RECOGNIZED
1067  return -1;
1068  }
1069  }
1070 
1071  //ostream overload
1072  template <typename T>
1073  std::ostream &operator<<(std::ostream &os, const Node<T> &node)
1074  {
1075  os << "Node: {\n"
1076  << " Id:\t" << node.id << "\n Data:\t" << node.data << "\n}";
1077  return os;
1078  }
1079 
1080  template <typename T>
1081  std::ostream &operator<<(std::ostream &os, const Edge<T> &edge)
1082  {
1083  os << "((Node: " << edge.nodePair.first->getId() << ")) ?----- |Edge: " << edge.id << "|-----? ((Node: " << edge.nodePair.second->getId() << "))";
1084  return os;
1085  }
1086 
1087  template <typename T>
1088  std::ostream &operator<<(std::ostream &os, const DirectedEdge<T> &edge)
1089  {
1090  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getTo().getId() << "))";
1091  return os;
1092  }
1093 
1094  template <typename T>
1095  std::ostream &operator<<(std::ostream &os, const UndirectedEdge<T> &edge)
1096  {
1097  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
1098  return os;
1099  }
1100 
1101  template <typename T>
1102  std::ostream &operator<<(std::ostream &os, const DirectedWeightedEdge<T> &edge)
1103  {
1104  os << "((Node: " << edge.getFrom().getId() << ")) +----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getTo().getId() << "))";
1105  return os;
1106  }
1107 
1108  template <typename T>
1109  std::ostream &operator<<(std::ostream &os, const UndirectedWeightedEdge<T> &edge)
1110  {
1111  os << "((Node: " << edge.getNode1().getId() << ")) <----- |Edge: #" << edge.getId() << " W:" << edge.getWeight() << "|-----> ((Node: " << edge.getNode2().getId() << "))";
1112  return os;
1113  }
1114 
1115  template <typename T>
1116  std::ostream &operator<<(std::ostream &os, const AdjacencyMatrix<T> &adj)
1117  {
1118  os << "Adjacency Matrix:\n";
1119  auto it = adj.begin();
1120  unsigned long max_column = 0;
1121  for (it; it != adj.end(); ++it)
1122  {
1123  if (it->second.size() > max_column)
1124  {
1125  max_column = it->second.size();
1126  }
1127  }
1128  if (max_column == 0)
1129  {
1130  os << "ERROR in Print\n";
1131  return os;
1132  }
1133  else
1134  {
1135  it = adj.begin();
1136  os << "|--|";
1137  for (int i = 0; i < max_column; i++)
1138  {
1139  os << "-----|";
1140  }
1141  os << "\n";
1142  for (it; it != adj.end(); ++it)
1143  {
1144  os << "|N" << it->first->getId() << "|";
1145  auto it2 = it->second.begin();
1146  for (it2; it2 != it->second.end(); ++it2)
1147  {
1148  os << "N" << it2->first->getId() << ",E" << it2->second->getId() << "|";
1149  }
1150  os << "\n|--|";
1151  for (int i = 0; i < max_column; i++)
1152  {
1153  os << "-----|";
1154  }
1155  os << "\n";
1156  }
1157  }
1158  return os;
1159  }
1160 
1161 } // namespace CXXGRAPH
1162 #endif // __CXXGRAPH_H__
Definition: Graph.hpp:231
Definition: Graph.hpp:345
Definition: Graph.hpp:159
Definition: Graph.hpp:465
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:851
const bool isDirectedGraph() const
This function checks if a graph is directed.
Definition: Graph.hpp:1042
const 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:973
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:701
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:811
int writeToFile(OutputFormat format=OutputFormat::STANDARD, std::string OFileName="graph.csv", bool compress=false, bool writeNodeFeat=false, bool writeEdgeWeight=false) const
This function write the graph in an output file.
Definition: Graph.hpp:1058
const 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:883
Definition: Graph.hpp:73
Definition: Graph.hpp:288
Definition: Graph.hpp:405
Definition: Graph.hpp:121
Definition: Graph.hpp:65