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();
37 class DirectedWeightedEdge;
39 class UndirectedWeightedEdge;
46 using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *,
const Edge<T> *>>>;
49 std::ostream &operator<<(std::ostream &o,
const Node<T> &node);
51 std::ostream &operator<<(std::ostream &o,
const Edge<T> &edge);
53 std::ostream &operator<<(std::ostream &o,
const DirectedEdge<T> &edge);
55 std::ostream &operator<<(std::ostream &o,
const UndirectedEdge<T> &edge);
57 std::ostream &operator<<(std::ostream &o,
const DirectedWeightedEdge<T> &edge);
59 std::ostream &operator<<(std::ostream &o,
const UndirectedWeightedEdge<T> &edge);
61 std::ostream &operator<<(std::ostream &o,
const Graph<T> &graph);
63 std::ostream &operator<<(std::ostream &o,
const AdjacencyMatrix<T> &adj);
68 std::string errorMessage;
80 Node(
const unsigned long id,
const T &data);
82 const unsigned long &getId()
const;
83 const T &getData()
const;
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);
98 const unsigned long &Node<T>::getId()
const
103 template <
typename T>
104 const T &Node<T>::getData()
const
109 template <
typename T>
110 bool Node<T>::operator==(
const Node<T> &b)
const
112 return (this->
id == b.id && this->data == b.data);
115 template <
typename T>
116 bool Node<T>::operator<(
const Node<T> &b)
const
118 return (this->
id < b.id);
130 double getWeight()
const;
131 void setWeight(
const double weight);
135 inline Weighted::Weighted()
141 inline Weighted::Weighted(
const double weight)
143 this->weight = weight;
147 inline double Weighted::getWeight()
const
153 inline void Weighted::setWeight(
const double weight)
155 this->weight = weight;
158 template <
typename T>
163 std::pair<const Node<T> *,
const Node<T> *> nodePair;
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;
174 virtual bool operator==(
const Edge<T> &b)
const;
175 bool operator<(
const Edge<T> &b)
const;
179 friend std::ostream &operator<<<>(std::ostream &os,
const Edge<T> &edge);
182 template <
typename T>
188 template <
typename T>
189 Edge<T>::Edge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : nodePair(nodepair)
194 template <
typename T>
195 const unsigned long &Edge<T>::getId()
const
200 template <
typename T>
201 const std::pair<const Node<T> *,
const Node<T> *> &Edge<T>::getNodePair()
const
206 template <
typename T>
207 const std::optional<bool> Edge<T>::isDirected()
const
212 template <
typename T>
213 const std::optional<bool> Edge<T>::isWeighted()
const
218 template <
typename T>
219 bool Edge<T>::operator==(
const Edge<T> &b)
const
221 return (this->
id == b.id && this->nodePair == b.nodePair);
224 template <
typename T>
225 bool Edge<T>::operator<(
const Edge<T> &b)
const
227 return (this->
id < b.id);
230 template <
typename T>
238 const Node<T> &getFrom()
const;
240 const std::optional<bool> isDirected()
const override;
241 virtual const std::optional<bool> isWeighted()
const override;
245 friend std::ostream &operator<<<>(std::ostream &os,
const DirectedEdge<T> &edge);
248 template <
typename T>
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)
258 template <
typename T>
259 DirectedEdge<T>::DirectedEdge(
const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
263 template <
typename T>
264 const Node<T> &DirectedEdge<T>::getFrom()
const
266 return *(Edge<T>::getNodePair().first);
269 template <
typename T>
270 const Node<T> &DirectedEdge<T>::getTo()
const
272 return *(Edge<T>::getNodePair().second);
275 template <
typename T>
276 const std::optional<bool> DirectedEdge<T>::isDirected()
const
281 template <
typename T>
282 const std::optional<bool> DirectedEdge<T>::isWeighted()
const
287 template <
typename T>
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;
302 friend std::ostream &operator<<<>(std::ostream &os,
const UndirectedEdge<T> &edge);
305 template <
typename T>
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)
315 template <
typename T>
316 UndirectedEdge<T>::UndirectedEdge(
const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
320 template <
typename T>
321 const Node<T> &UndirectedEdge<T>::getNode1()
const
323 return *(Edge<T>::getNodePair().first);
326 template <
typename T>
327 const Node<T> &UndirectedEdge<T>::getNode2()
const
329 return *(Edge<T>::getNodePair().second);
332 template <
typename T>
333 const std::optional<bool> UndirectedEdge<T>::isDirected()
const
338 template <
typename T>
339 const std::optional<bool> UndirectedEdge<T>::isWeighted()
const
344 template <
typename T>
356 const std::optional<bool> isWeighted()
const override;
363 template <
typename T>
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)
373 template <
typename T>
374 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
378 template <
typename T>
379 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
383 template <
typename T>
384 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
388 template <
typename T>
389 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
393 template <
typename T>
394 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
398 template <
typename T>
399 const std::optional<bool> DirectedWeightedEdge<T>::isWeighted()
const
404 template <
typename T>
416 const std::optional<bool> isWeighted()
const override;
423 template <
typename T>
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)
433 template <
typename T>
434 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
438 template <
typename T>
439 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
443 template <
typename T>
444 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
448 template <
typename T>
449 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
453 template <
typename T>
454 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
458 template <
typename T>
459 const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted()
const
464 template <
typename T>
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);
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;
494 const AdjacencyMatrix<T> getAdjMatrix()
const;
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);
581 friend std::ostream &operator<<<>(std::ostream &os,
const Graph<T> &graph);
582 friend std::ostream &operator<<<>(std::ostream &os,
const AdjacencyMatrix<T> &adj);
585 template <
typename T>
586 Graph<T>::Graph(
const std::list<
const Edge<T> *> &edgeSet)
588 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
590 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
591 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
593 this->edgeSet.push_back(*edgeSetIt);
598 template <
typename T>
599 const std::list<const Edge<T> *> &Graph<T>::getEdgeSet()
const
604 template <
typename T>
605 void Graph<T>::setEdgeSet(std::list<
const Edge<T> *> &edgeSet)
607 this->edgeSet.clear();
608 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
610 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
611 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
613 this->edgeSet.push_back(*edgeSetIt);
618 template <
typename T>
619 void Graph<T>::addEdge(
const Edge<T> *edge)
621 if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](
const Edge<T> *edge_a)
622 { return (*edge == *edge_a); }) == edgeSet.end())
624 edgeSet.push_back(edge);
628 template <
typename T>
629 void Graph<T>::removeEdge(
unsigned long edgeId)
631 auto edgeOpt = getEdge(edgeId);
632 if (edgeOpt.has_value())
634 edgeSet.erase(edgeSet.find(edgeOpt.value()));
638 template <
typename T>
639 const std::list<const Node<T> *> Graph<T>::getNodeSet()
const
641 std::list<const Node<T> *> nodeSet;
642 for (
auto edge : edgeSet)
644 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
645 { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
647 nodeSet.push_back(edge->getNodePair().first);
649 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
650 { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
652 nodeSet.push_back(edge->getNodePair().second);
658 template <
typename T>
659 const std::optional<const Edge<T> *> Graph<T>::getEdge(
unsigned long edgeId)
const
662 auto it = edgeSet.begin();
663 for (it; it != edgeSet.end(); ++it)
665 if ((*it)->getId() == edgeId)
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
677 std::pair<const Node<T> *,
const Edge<T> *> elem = {nodeTo, edge};
678 adjMatrix[nodeFrom].push_back(elem);
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
686 std::ofstream ofileGraph;
687 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
688 ofileGraph.open(completePathToFileGraph);
689 if (!ofileGraph.is_open())
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);
701 std::ofstream ofileNodeFeat;
702 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
704 ofileNodeFeat.open(completePathToFileNodeFeat);
705 if (!ofileNodeFeat.is_open())
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();
719 std::ofstream ofileEdgeWeight;
720 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
722 ofileEdgeWeight.open(completePathToFileEdgeWeight);
723 if (!ofileEdgeWeight.is_open())
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; };
731 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
732 ofileEdgeWeight.close();
737 template <
typename T>
738 int Graph<T>::readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
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())
757 unsigned long edgeId;
758 unsigned long nodeId1;
759 unsigned long nodeId2;
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())
768 ifileGraph.ignore(128,
'\n');
774 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
776 ifileNodeFeat.open(completePathToFileNodeFeat);
777 if (!ifileNodeFeat.is_open())
785 unsigned long nodeId;
787 ifileNodeFeat >> nodeId >> comma >> nodeFeat;
788 nodeFeatMap[nodeId] = nodeFeat;
789 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
791 ifileNodeFeat.ignore(128,
'\n');
793 ifileNodeFeat.close();
799 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
801 ifileEdgeWeight.open(completePathToFileEdgeWeight);
802 if (!ifileEdgeWeight.is_open())
810 unsigned long edgeId;
813 ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
816 edgeWeightMap[edgeId] = weight;
818 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
820 ifileEdgeWeight.ignore(128,
'\n');
822 ifileEdgeWeight.close();
824 std::map<unsigned long, Node<T> *> nodeMap;
825 for (
auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
827 Node<T> *node1 =
nullptr;
828 Node<T> *node2 =
nullptr;
829 if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
833 if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
835 feat = nodeFeatMap.at(edgeIt->second.first);
837 node1 =
new Node<T>(edgeIt->second.first, feat);
838 nodeMap[edgeIt->second.first] = node1;
842 node1 = nodeMap.at(edgeIt->second.first);
844 if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
848 if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
850 feat = nodeFeatMap.at(edgeIt->second.second);
852 node2 =
new Node<T>(edgeIt->second.second, feat);
853 nodeMap[edgeIt->second.second] = node2;
857 node2 = nodeMap.at(edgeIt->second.second);
860 if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
862 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
864 auto edge =
new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
865 std::cout <<
"ADD Edge : " << *edge << std::endl;
867 std::cout <<
"EdgeSet size : " << getEdgeSet().size() << std::endl;
871 auto edge =
new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
872 std::cout <<
"ADD Edge : " << *edge << std::endl;
874 std::cout <<
"EdgeSet size : " << getEdgeSet().size() << std::endl;
879 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
881 auto edge =
new DirectedEdge<T>(edgeIt->first, *node1, *node2);
882 std::cout <<
"ADD Edge : " << *edge << std::endl;
884 std::cout <<
"EdgeSet size : " << getEdgeSet().size() << std::endl;
888 auto edge =
new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
889 std::cout <<
"ADD Edge : " << *edge << std::endl;
891 std::cout <<
"EdgeSet size : " << getEdgeSet().size() << std::endl;
899 template <
typename T>
900 const AdjacencyMatrix<T> Graph<T>::getAdjMatrix()
const
902 AdjacencyMatrix<T> adj;
903 auto edgeSetIt = edgeSet.begin();
904 for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
906 if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
908 const DirectedEdge<T> *d_edge =
dynamic_cast<const DirectedEdge<T> *
>(*edgeSetIt);
909 addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
911 else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
913 const UndirectedEdge<T> *ud_edge =
dynamic_cast<const UndirectedEdge<T> *
>(*edgeSetIt);
915 addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
916 addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
926 template <
typename T>
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())
937 result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
940 if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
943 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
946 const AdjacencyMatrix<T> adj = getAdjMatrix();
951 std::map<const Node<T> *,
double> dist;
953 for (
auto elem : adj)
955 dist[elem.first] = INF_DOUBLE;
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> *>>>
966 pq.push(std::make_pair(0.0, &source));
974 const Node<T> *currentNode = pq.top().second;
977 double currentDist = pq.top().first;
983 if (adj.find(currentNode) != adj.end())
985 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
988 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
990 if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
993 if (currentDist + dw_edge->getWeight() < dist[elem.first])
995 dist[elem.first] = currentDist + dw_edge->getWeight();
996 pq.push(std::make_pair(dist[elem.first], elem.first));
999 else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1002 if (currentDist + udw_edge->getWeight() < dist[elem.first])
1004 dist[elem.first] = currentDist + udw_edge->getWeight();
1005 pq.push(std::make_pair(dist[elem.first], elem.first));
1011 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1018 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1024 if (dist[&target] != INF_DOUBLE)
1026 result.success =
true;
1027 result.errorMessage =
"";
1028 result.result = dist[&target];
1031 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
1036 template <
typename T>
1040 std::vector<Node<T>> visited;
1041 auto nodeSet = getNodeSet();
1043 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1047 const AdjacencyMatrix<T> adj = getAdjMatrix();
1049 std::queue<const Node<T> *> tracker;
1052 visited.push_back(start);
1053 tracker.push(&start);
1054 while (!tracker.empty())
1056 const Node<T> *node = tracker.front();
1058 if (adj.find(node) != adj.end())
1060 for (
auto elem : adj.at(node))
1064 if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1066 visited.push_back(*(elem.first));
1067 tracker.push(elem.first);
1076 template <
typename T>
1080 std::vector<Node<T>> visited;
1081 auto nodeSet = getNodeSet();
1083 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
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
1091 visited.push_back(node);
1092 if (adj.find(&node) != adj.end())
1094 for (
auto x : adj.at(&node))
1096 if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1098 explore(adj, *(x.first), visited);
1103 explore(adj, start, visited);
1108 template <
typename T>
1111 if (!isDirectedGraph())
1115 enum nodeStates : uint8_t
1121 auto nodeSet = this->getNodeSet();
1122 auto adjMatrix = this->getAdjMatrix();
1131 std::map<unsigned long, nodeStates> state;
1132 for (
auto node : nodeSet)
1134 state[node->getId()] = not_visited;
1136 int stateCounter = 0;
1139 for (
auto node : nodeSet)
1144 if (state[node->getId()] == not_visited)
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)
1151 states[node->getId()] = in_stack;
1155 auto const it = adjMatrix.find(node);
1156 if (it != adjMatrix.end())
1158 for (
auto child : it->second)
1162 auto state_of_child = states.at((std::get<0>(child))->getId());
1163 if (state_of_child == not_visited)
1165 if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1170 else if (state_of_child == in_stack)
1182 states[node->getId()] = visited;
1186 if (isCyclicDFSHelper(adjMatrix, state, node))
1198 template <
typename T>
1201 if (!isDirectedGraph())
1205 auto adjMatrix = this->getAdjMatrix();
1206 auto nodeSet = this->getNodeSet();
1208 std::map<unsigned long, unsigned int> indegree;
1209 for (
auto node : nodeSet)
1211 indegree[node->getId()] = 0;
1214 for (
auto const &list : adjMatrix)
1216 auto children = list.second;
1217 for (
auto const &child : children)
1219 indegree[std::get<0>(child)->getId()]++;
1223 std::queue<const Node<T> *> can_be_solved;
1224 for (
auto node : nodeSet)
1228 if (!indegree[node->getId()])
1230 can_be_solved.emplace(&(*node));
1235 auto remain = this->getNodeSet().size();
1237 while (!can_be_solved.empty())
1239 auto solved = can_be_solved.front();
1241 can_be_solved.pop();
1246 auto it = adjMatrix.find(solved);
1247 if (it != adjMatrix.end())
1249 for (
auto child : it->second)
1252 if (--indegree[std::get<0>(child)->getId()] == 0)
1256 can_be_solved.emplace(std::get<0>(child));
1264 return !(remain == 0);
1267 template <
typename T>
1270 auto edgeSet = this->getEdgeSet();
1271 for (
auto edge : edgeSet)
1273 if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1283 template <
typename T>
1286 if (format == InputOutputFormat::STANDARD_CSV)
1288 return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1297 template <
typename T>
1300 if (format == InputOutputFormat::STANDARD_CSV)
1302 return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1312 template <
typename T>
1313 std::ostream &operator<<(std::ostream &os,
const Node<T> &node)
1316 <<
" Id:\t" << node.id <<
"\n Data:\t" << node.data <<
"\n}";
1320 template <
typename T>
1321 std::ostream &operator<<(std::ostream &os,
const Edge<T> &edge)
1323 os <<
"((Node: " << edge.nodePair.first->getId() <<
")) ?----- |Edge: " << edge.id <<
"|-----? ((Node: " << edge.nodePair.second->getId() <<
"))";
1327 template <
typename T>
1328 std::ostream &operator<<(std::ostream &os,
const DirectedEdge<T> &edge)
1330 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1334 template <
typename T>
1335 std::ostream &operator<<(std::ostream &os,
const UndirectedEdge<T> &edge)
1337 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1341 template <
typename T>
1342 std::ostream &operator<<(std::ostream &os,
const DirectedWeightedEdge<T> &edge)
1344 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1348 template <
typename T>
1349 std::ostream &operator<<(std::ostream &os,
const UndirectedWeightedEdge<T> &edge)
1351 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1355 template <
typename T>
1356 std::ostream &operator<<(std::ostream &os,
const AdjacencyMatrix<T> &adj)
1358 os <<
"Adjacency Matrix:\n";
1359 auto it = adj.begin();
1360 unsigned long max_column = 0;
1361 for (it; it != adj.end(); ++it)
1363 if (it->second.size() > max_column)
1365 max_column = it->second.size();
1368 if (max_column == 0)
1370 os <<
"ERROR in Print\n";
1377 for (
int i = 0; i < max_column; i++)
1382 for (it; it != adj.end(); ++it)
1384 os <<
"|N" << it->first->getId() <<
"|";
1385 auto it2 = it->second.begin();
1386 for (it2; it2 != it->second.end(); ++it2)
1388 os <<
"N" << it2->first->getId() <<
",E" << it2->second->getId() <<
"|";
1391 for (
int i = 0; i < max_column; i++)
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:289
Definition: Graph.hpp:406
Definition: Graph.hpp:122