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();
36 class DirectedWeightedEdge;
38 class UndirectedWeightedEdge;
45 using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *,
const Edge<T> *>>>;
48 std::ostream &operator<<(std::ostream &o,
const Node<T> &node);
50 std::ostream &operator<<(std::ostream &o,
const Edge<T> &edge);
52 std::ostream &operator<<(std::ostream &o,
const DirectedEdge<T> &edge);
54 std::ostream &operator<<(std::ostream &o,
const UndirectedEdge<T> &edge);
56 std::ostream &operator<<(std::ostream &o,
const DirectedWeightedEdge<T> &edge);
58 std::ostream &operator<<(std::ostream &o,
const UndirectedWeightedEdge<T> &edge);
60 std::ostream &operator<<(std::ostream &o,
const Graph<T> &graph);
62 std::ostream &operator<<(std::ostream &o,
const AdjacencyMatrix<T> &adj);
67 std::string errorMessage;
79 Node(
const unsigned long id,
const T &data);
81 const unsigned long &getId()
const;
82 const T &getData()
const;
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);
97 const unsigned long &Node<T>::getId()
const
102 template <
typename T>
103 const T &Node<T>::getData()
const
108 template <
typename T>
109 bool Node<T>::operator==(
const Node<T> &b)
const
111 return (this->
id == b.id && this->data == b.data);
114 template <
typename T>
115 bool Node<T>::operator<(
const Node<T> &b)
const
117 return (this->
id < b.id);
129 double getWeight()
const;
130 void setWeight(
const double weight);
134 inline Weighted::Weighted()
140 inline Weighted::Weighted(
const double weight)
142 this->weight = weight;
146 inline double Weighted::getWeight()
const
152 inline void Weighted::setWeight(
const double weight)
154 this->weight = weight;
157 template <
typename T>
162 std::pair<const Node<T> *,
const Node<T> *> nodePair;
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;
173 virtual bool operator==(
const Edge<T> &b)
const;
174 bool operator<(
const Edge<T> &b)
const;
178 friend std::ostream &operator<<<>(std::ostream &os,
const Edge<T> &edge);
181 template <
typename T>
187 template <
typename T>
188 Edge<T>::Edge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : nodePair(nodepair)
193 template <
typename T>
194 const unsigned long &Edge<T>::getId()
const
199 template <
typename T>
200 const std::pair<const Node<T> *,
const Node<T> *> &Edge<T>::getNodePair()
const
205 template <
typename T>
206 const std::optional<bool> Edge<T>::isDirected()
const
211 template <
typename T>
212 const std::optional<bool> Edge<T>::isWeighted()
const
217 template <
typename T>
218 bool Edge<T>::operator==(
const Edge<T> &b)
const
220 return (this->
id == b.id && this->nodePair == b.nodePair);
223 template <
typename T>
224 bool Edge<T>::operator<(
const Edge<T> &b)
const
226 return (this->
id < b.id);
229 template <
typename T>
237 const Node<T> &getFrom()
const;
239 const std::optional<bool> isDirected()
const override;
240 virtual const std::optional<bool> isWeighted()
const override;
244 friend std::ostream &operator<<<>(std::ostream &os,
const DirectedEdge<T> &edge);
247 template <
typename T>
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)
257 template <
typename T>
258 DirectedEdge<T>::DirectedEdge(
const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
262 template <
typename T>
263 const Node<T> &DirectedEdge<T>::getFrom()
const
265 return *(Edge<T>::getNodePair().first);
268 template <
typename T>
269 const Node<T> &DirectedEdge<T>::getTo()
const
271 return *(Edge<T>::getNodePair().second);
274 template <
typename T>
275 const std::optional<bool> DirectedEdge<T>::isDirected()
const
280 template <
typename T>
281 const std::optional<bool> DirectedEdge<T>::isWeighted()
const
286 template <
typename T>
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;
301 friend std::ostream &operator<<<>(std::ostream &os,
const UndirectedEdge<T> &edge);
304 template <
typename T>
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)
314 template <
typename T>
315 UndirectedEdge<T>::UndirectedEdge(
const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
319 template <
typename T>
320 const Node<T> &UndirectedEdge<T>::getNode1()
const
322 return *(Edge<T>::getNodePair().first);
325 template <
typename T>
326 const Node<T> &UndirectedEdge<T>::getNode2()
const
328 return *(Edge<T>::getNodePair().second);
331 template <
typename T>
332 const std::optional<bool> UndirectedEdge<T>::isDirected()
const
337 template <
typename T>
338 const std::optional<bool> UndirectedEdge<T>::isWeighted()
const
343 template <
typename T>
355 const std::optional<bool> isWeighted()
const override;
362 template <
typename T>
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)
372 template <
typename T>
373 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
377 template <
typename T>
378 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
382 template <
typename T>
383 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
387 template <
typename T>
388 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
392 template <
typename T>
393 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
397 template <
typename T>
398 const std::optional<bool> DirectedWeightedEdge<T>::isWeighted()
const
403 template <
typename T>
415 const std::optional<bool> isWeighted()
const override;
422 template <
typename T>
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)
432 template <
typename T>
433 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
437 template <
typename T>
438 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
442 template <
typename T>
443 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
447 template <
typename T>
448 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
452 template <
typename T>
453 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
457 template <
typename T>
458 const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted()
const
463 template <
typename T>
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;
472 typedef enum E_OutputFormat
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;
491 const AdjacencyMatrix<T> getAdjMatrix()
const;
562 int writeToFile(OutputFormat format = OutputFormat::STANDARD, std::string OFileName =
"graph.csv",
bool compress =
false,
bool writeNodeFeat =
false,
bool writeEdgeWeight =
false)
const;
564 friend std::ostream &operator<<<>(std::ostream &os,
const Graph<T> &graph);
565 friend std::ostream &operator<<<>(std::ostream &os,
const AdjacencyMatrix<T> &adj);
568 template <
typename T>
571 this->edgeSet = edgeSet;
574 template <
typename T>
575 const std::set<const Edge<T> *> &Graph<T>::getEdgeSet()
const
580 template <
typename T>
581 void Graph<T>::setEdgeSet(std::set<
const Edge<T> *> &edgeSet)
583 this->edgeSet = edgeSet;
586 template <
typename T>
587 void Graph<T>::addEdge(
const Edge<T> &edge)
589 edgeSet.insert(&edge);
592 template <
typename T>
593 void Graph<T>::removeEdge(
unsigned long edgeId)
595 auto edgeOpt = getEdge(edgeId);
596 if (edgeOpt.has_value())
598 edgeSet.erase(edgeSet.find(edgeOpt.value()));
602 template <
typename T>
603 const std::set<const Node<T> *> Graph<T>::getNodeSet()
const
605 std::set<const Node<T> *> nodeSet;
606 for (
auto edge : edgeSet)
608 nodeSet.insert(edge->getNodePair().first);
609 nodeSet.insert(edge->getNodePair().second);
614 template <
typename T>
615 const std::optional<const Edge<T> *> Graph<T>::getEdge(
unsigned long edgeId)
const
618 auto it = edgeSet.begin();
619 for (it; it != edgeSet.end(); ++it)
621 if ((*it)->getId() == edgeId)
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
633 std::pair<const Node<T> *,
const Edge<T> *> elem = {nodeTo, edge};
634 adjMatrix[nodeFrom].push_back(elem);
639 template <
typename T>
640 int Graph<T>::writeToStandardFile(std::string OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
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);
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();
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; };
667 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
668 ofileEdgeWeight.close();
673 template <
typename T>
674 const AdjacencyMatrix<T> Graph<T>::getAdjMatrix()
const
676 AdjacencyMatrix<T> adj;
677 auto edgeSetIt = edgeSet.begin();
678 for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
680 if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
682 const DirectedEdge<T> *d_edge =
dynamic_cast<const DirectedEdge<T> *
>(*edgeSetIt);
683 addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
685 else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
687 const UndirectedEdge<T> *ud_edge =
dynamic_cast<const UndirectedEdge<T> *
>(*edgeSetIt);
689 addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
690 addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
700 template <
typename T>
704 result.success =
false;
705 result.errorMessage =
"";
706 result.result = INF_DOUBLE;
707 auto nodeSet = getNodeSet();
708 if (nodeSet.find(&source) == nodeSet.end())
711 result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
714 if (nodeSet.find(&target) == nodeSet.end())
717 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
720 const AdjacencyMatrix<T> adj = getAdjMatrix();
725 std::map<const Node<T> *,
double> dist;
727 for (
auto elem : adj)
729 dist[elem.first] = INF_DOUBLE;
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> *>>>
740 pq.push(std::make_pair(0.0, &source));
748 const Node<T> *currentNode = pq.top().second;
751 double currentDist = pq.top().first;
757 if (adj.find(currentNode) != adj.end())
759 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
762 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
764 if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
767 if (currentDist + dw_edge->getWeight() < dist[elem.first])
769 dist[elem.first] = currentDist + dw_edge->getWeight();
770 pq.push(std::make_pair(dist[elem.first], elem.first));
773 else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
776 if (currentDist + udw_edge->getWeight() < dist[elem.first])
778 dist[elem.first] = currentDist + udw_edge->getWeight();
779 pq.push(std::make_pair(dist[elem.first], elem.first));
785 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
792 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
798 if (dist[&target] != INF_DOUBLE)
800 result.success =
true;
801 result.errorMessage =
"";
802 result.result = dist[&target];
805 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
810 template <
typename T>
814 std::vector<Node<T>> visited;
815 auto nodeSet = getNodeSet();
817 if (nodeSet.find(&start) == nodeSet.end())
821 const AdjacencyMatrix<T> adj = getAdjMatrix();
823 std::queue<const Node<T> *> tracker;
826 visited.push_back(start);
827 tracker.push(&start);
828 while (!tracker.empty())
830 const Node<T> *node = tracker.front();
832 if (adj.find(node) != adj.end())
834 for (
auto elem : adj.at(node))
838 if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
840 visited.push_back(*(elem.first));
841 tracker.push(elem.first);
850 template <
typename T>
854 std::vector<Node<T>> visited;
855 auto nodeSet = getNodeSet();
857 if (nodeSet.find(&start) == nodeSet.end())
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
865 visited.push_back(node);
866 if (adj.find(&node) != adj.end())
868 for (
auto x : adj.at(&node))
870 if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
872 explore(adj, *(x.first), visited);
877 explore(adj, start, visited);
882 template <
typename T>
885 if (!isDirectedGraph())
889 enum nodeStates : uint8_t
895 auto nodeSet = this->getNodeSet();
896 auto adjMatrix = this->getAdjMatrix();
905 std::map<unsigned long, nodeStates> state;
906 for (
auto node : nodeSet)
908 state[node->getId()] = not_visited;
910 int stateCounter = 0;
913 for (
auto node : nodeSet)
918 if (state[node->getId()] == not_visited)
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)
925 states[node->getId()] = in_stack;
929 auto const it = adjMatrix.find(node);
930 if (it != adjMatrix.end())
932 for (
auto child : it->second)
936 auto state_of_child = states.at((std::get<0>(child))->getId());
937 if (state_of_child == not_visited)
939 if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
944 else if (state_of_child == in_stack)
956 states[node->getId()] = visited;
960 if (isCyclicDFSHelper(adjMatrix, state, node))
972 template <
typename T>
975 if (!isDirectedGraph())
979 auto adjMatrix = this->getAdjMatrix();
980 auto nodeSet = this->getNodeSet();
982 std::map<unsigned long, unsigned int> indegree;
983 for (
auto node : nodeSet)
985 indegree[node->getId()] = 0;
988 for (
auto const &list : adjMatrix)
990 auto children = list.second;
991 for (
auto const &child : children)
993 indegree[std::get<0>(child)->getId()]++;
997 std::queue<const Node<T> *> can_be_solved;
998 for (
auto node : nodeSet)
1002 if (!indegree[node->getId()])
1004 can_be_solved.emplace(&(*node));
1009 auto remain = this->getNodeSet().size();
1011 while (!can_be_solved.empty())
1013 auto solved = can_be_solved.front();
1015 can_be_solved.pop();
1020 auto it = adjMatrix.find(solved);
1021 if (it != adjMatrix.end())
1023 for (
auto child : it->second)
1026 if (--indegree[std::get<0>(child)->getId()] == 0)
1030 can_be_solved.emplace(std::get<0>(child));
1038 return !(remain == 0);
1041 template <
typename T>
1044 auto edgeSet = this->getEdgeSet();
1045 for (
auto edge : edgeSet)
1047 if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1057 template <
typename T>
1058 int Graph<T>::writeToFile(OutputFormat format, std::string OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
1060 if (format == OutputFormat::STANDARD)
1062 return writeToStandardFile(OFileName, compress, writeNodeFeat, writeEdgeWeight);
1072 template <
typename T>
1073 std::ostream &operator<<(std::ostream &os,
const Node<T> &node)
1076 <<
" Id:\t" << node.id <<
"\n Data:\t" << node.data <<
"\n}";
1080 template <
typename T>
1081 std::ostream &operator<<(std::ostream &os,
const Edge<T> &edge)
1083 os <<
"((Node: " << edge.nodePair.first->getId() <<
")) ?----- |Edge: " << edge.id <<
"|-----? ((Node: " << edge.nodePair.second->getId() <<
"))";
1087 template <
typename T>
1088 std::ostream &operator<<(std::ostream &os,
const DirectedEdge<T> &edge)
1090 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1094 template <
typename T>
1095 std::ostream &operator<<(std::ostream &os,
const UndirectedEdge<T> &edge)
1097 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1101 template <
typename T>
1102 std::ostream &operator<<(std::ostream &os,
const DirectedWeightedEdge<T> &edge)
1104 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1108 template <
typename T>
1109 std::ostream &operator<<(std::ostream &os,
const UndirectedWeightedEdge<T> &edge)
1111 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1115 template <
typename T>
1116 std::ostream &operator<<(std::ostream &os,
const AdjacencyMatrix<T> &adj)
1118 os <<
"Adjacency Matrix:\n";
1119 auto it = adj.begin();
1120 unsigned long max_column = 0;
1121 for (it; it != adj.end(); ++it)
1123 if (it->second.size() > max_column)
1125 max_column = it->second.size();
1128 if (max_column == 0)
1130 os <<
"ERROR in Print\n";
1137 for (
int i = 0; i < max_column; i++)
1142 for (it; it != adj.end(); ++it)
1144 os <<
"|N" << it->first->getId() <<
"|";
1145 auto it2 = it->second.begin();
1146 for (it2; it2 != it->second.end(); ++it2)
1148 os <<
"N" << it2->first->getId() <<
",E" << it2->second->getId() <<
"|";
1151 for (
int i = 0; i < max_column; i++)
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:288
Definition: Graph.hpp:405
Definition: Graph.hpp:121