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);
472 int writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
473 int readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
488 const std::list<const Edge<T> *> &getEdgeSet()
const;
489 void setEdgeSet(std::list<
const Edge<T> *> &edgeSet);
490 void addEdge(
const Edge<T> *edge);
491 void removeEdge(
unsigned long edgeId);
492 const std::list<const Node<T> *> getNodeSet()
const;
493 const std::optional<const Edge<T> *> getEdge(
unsigned long edgeId)
const;
497 const AdjacencyMatrix<T> getAdjMatrix()
const;
569 int writeToFile(
InputOutputFormat format = InputOutputFormat::STANDARD_CSV,
const std::string &workingDir =
".",
const std::string &OFileName =
"graph",
bool compress =
false,
bool writeNodeFeat =
false,
bool writeEdgeWeight =
false)
const;
582 int readFromFile(
InputOutputFormat format = InputOutputFormat::STANDARD_CSV,
const std::string &workingDir =
".",
const std::string &OFileName =
"graph",
bool compress =
false,
bool readNodeFeat =
false,
bool readEdgeWeight =
false);
584 friend std::ostream &operator<<<>(std::ostream &os,
const Graph<T> &graph);
585 friend std::ostream &operator<<<>(std::ostream &os,
const AdjacencyMatrix<T> &adj);
588 template <
typename T>
589 Graph<T>::Graph(
const std::list<
const Edge<T> *> &edgeSet)
591 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
593 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
594 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
596 this->edgeSet.push_back(*edgeSetIt);
601 template <
typename T>
602 const std::list<const Edge<T> *> &Graph<T>::getEdgeSet()
const
607 template <
typename T>
608 void Graph<T>::setEdgeSet(std::list<
const Edge<T> *> &edgeSet)
610 this->edgeSet.clear();
611 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
613 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
614 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
616 this->edgeSet.push_back(*edgeSetIt);
621 template <
typename T>
622 void Graph<T>::addEdge(
const Edge<T> *edge)
624 if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](
const Edge<T> *edge_a)
625 { return (*edge == *edge_a); }) == edgeSet.end())
627 edgeSet.push_back(edge);
631 template <
typename T>
632 void Graph<T>::removeEdge(
unsigned long edgeId)
634 auto edgeOpt = getEdge(edgeId);
635 if (edgeOpt.has_value())
637 edgeSet.erase(edgeSet.find(edgeOpt.value()));
641 template <
typename T>
642 const std::list<const Node<T> *> Graph<T>::getNodeSet()
const
644 std::list<const Node<T> *> nodeSet;
645 for (
auto edge : edgeSet)
647 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
648 { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
650 nodeSet.push_back(edge->getNodePair().first);
652 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
653 { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
655 nodeSet.push_back(edge->getNodePair().second);
661 template <
typename T>
662 const std::optional<const Edge<T> *> Graph<T>::getEdge(
unsigned long edgeId)
const
665 auto it = edgeSet.begin();
666 for (it; it != edgeSet.end(); ++it)
668 if ((*it)->getId() == edgeId)
677 template <
typename T>
678 void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix,
const Node<T> *nodeFrom,
const Node<T> *nodeTo,
const Edge<T> *edge)
const
680 std::pair<const Node<T> *,
const Edge<T> *> elem = {nodeTo, edge};
681 adjMatrix[nodeFrom].push_back(elem);
686 template <
typename T>
687 int Graph<T>::writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
689 std::ofstream ofileGraph;
690 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
691 ofileGraph.open(completePathToFileGraph);
692 if (!ofileGraph.is_open())
697 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
698 { ofileGraph << e->getId() <<
"," << e->getNodePair().first->getId() <<
"," << e->getNodePair().second->getId() <<
"," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
699 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
704 std::ofstream ofileNodeFeat;
705 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
707 ofileNodeFeat.open(completePathToFileNodeFeat);
708 if (!ofileNodeFeat.is_open())
713 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
714 { ofileNodeFeat << node->getId() <<
"," << node->getData() << std::endl; };
715 auto nodeSet = getNodeSet();
716 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
717 ofileNodeFeat.close();
722 std::ofstream ofileEdgeWeight;
723 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
725 ofileEdgeWeight.open(completePathToFileEdgeWeight);
726 if (!ofileEdgeWeight.is_open())
731 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
732 { ofileEdgeWeight << e->getId() <<
"," << (e->isWeighted().has_value() && e->isWeighted().value() ? (
dynamic_cast<const Weighted *
>(e))->getWeight() : 0.0) <<
"," << (e->isWeighted().has_value() && e->isWeighted().value() ? 1 : 0) << std::endl; };
734 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
735 ofileEdgeWeight.close();
740 template <
typename T>
741 int Graph<T>::readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
743 std::ifstream ifileGraph;
744 std::ifstream ifileNodeFeat;
745 std::ifstream ifileEdgeWeight;
746 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
747 std::map<unsigned long, bool> edgeDirectedMap;
748 std::map<unsigned long, T> nodeFeatMap;
749 std::map<unsigned long, double> edgeWeightMap;
750 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
751 ifileGraph.open(completePathToFileGraph);
752 if (!ifileGraph.is_open())
760 unsigned long edgeId;
761 unsigned long nodeId1;
762 unsigned long nodeId2;
764 ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
765 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
766 edgeDirectedMap[edgeId] = directed;
767 if (ifileGraph.fail() || ifileGraph.eof())
769 ifileGraph.ignore(128,
'\n');
775 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
777 ifileNodeFeat.open(completePathToFileNodeFeat);
778 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())
809 unsigned long edgeId;
812 ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
815 edgeWeightMap[edgeId] = weight;
817 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
819 ifileEdgeWeight.ignore(128,
'\n');
821 ifileEdgeWeight.close();
823 std::map<unsigned long, Node<T> *> nodeMap;
824 for (
auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
826 Node<T> *node1 =
nullptr;
827 Node<T> *node2 =
nullptr;
828 if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
832 if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
834 feat = nodeFeatMap.at(edgeIt->second.first);
836 node1 =
new Node<T>(edgeIt->second.first, feat);
837 nodeMap[edgeIt->second.first] = node1;
841 node1 = nodeMap.at(edgeIt->second.first);
843 if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
847 if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
849 feat = nodeFeatMap.at(edgeIt->second.second);
851 node2 =
new Node<T>(edgeIt->second.second, feat);
852 nodeMap[edgeIt->second.second] = node2;
856 node2 = nodeMap.at(edgeIt->second.second);
859 if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
861 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
863 auto edge =
new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
868 auto edge =
new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
874 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
876 auto edge =
new DirectedEdge<T>(edgeIt->first, *node1, *node2);
881 auto edge =
new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
890 template <
typename T>
891 int Graph<T>::writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
893 std::ofstream ofileGraph;
894 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
895 ofileGraph.open(completePathToFileGraph);
896 if (!ofileGraph.is_open())
901 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
902 { ofileGraph << e->getId() <<
"\t" << e->getNodePair().first->getId() <<
"\t" << e->getNodePair().second->getId() <<
"\t" << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
903 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
908 std::ofstream ofileNodeFeat;
909 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
911 ofileNodeFeat.open(completePathToFileNodeFeat);
912 if (!ofileNodeFeat.is_open())
917 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
918 { ofileNodeFeat << node->getId() <<
"\t" << node->getData() << std::endl; };
919 auto nodeSet = getNodeSet();
920 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
921 ofileNodeFeat.close();
926 std::ofstream ofileEdgeWeight;
927 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
929 ofileEdgeWeight.open(completePathToFileEdgeWeight);
930 if (!ofileEdgeWeight.is_open())
935 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
936 { ofileEdgeWeight << e->getId() <<
"\t" << (e->isWeighted().has_value() && e->isWeighted().value() ? (
dynamic_cast<const Weighted *
>(e))->getWeight() : 0.0) <<
"\t" << (e->isWeighted().has_value() && e->isWeighted().value() ? 1 : 0) << std::endl; };
938 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
939 ofileEdgeWeight.close();
944 template <
typename T>
945 int Graph<T>::readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
947 std::ifstream ifileGraph;
948 std::ifstream ifileNodeFeat;
949 std::ifstream ifileEdgeWeight;
950 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
951 std::map<unsigned long, bool> edgeDirectedMap;
952 std::map<unsigned long, T> nodeFeatMap;
953 std::map<unsigned long, double> edgeWeightMap;
954 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
955 ifileGraph.open(completePathToFileGraph);
956 if (!ifileGraph.is_open())
964 unsigned long edgeId;
965 unsigned long nodeId1;
966 unsigned long nodeId2;
968 ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
969 std::cout << edgeId << nodeId1 << nodeId2 << directed << std::endl;
970 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
971 edgeDirectedMap[edgeId] = directed;
972 if (ifileGraph.fail() || ifileGraph.eof())
974 ifileGraph.ignore(128,
'\n');
980 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
982 ifileNodeFeat.open(completePathToFileNodeFeat);
983 if (!ifileNodeFeat.is_open())
990 unsigned long nodeId;
992 ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
993 nodeFeatMap[nodeId] = nodeFeat;
994 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
996 ifileNodeFeat.ignore(128,
'\n');
998 ifileNodeFeat.close();
1004 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
1006 ifileEdgeWeight.open(completePathToFileEdgeWeight);
1007 if (!ifileEdgeWeight.is_open())
1014 unsigned long edgeId;
1017 ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
1020 edgeWeightMap[edgeId] = weight;
1022 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
1024 ifileEdgeWeight.ignore(128,
'\n');
1026 ifileEdgeWeight.close();
1028 std::map<unsigned long, Node<T> *> nodeMap;
1029 for (
auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
1031 Node<T> *node1 =
nullptr;
1032 Node<T> *node2 =
nullptr;
1033 if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
1037 if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
1039 feat = nodeFeatMap.at(edgeIt->second.first);
1041 node1 =
new Node<T>(edgeIt->second.first, feat);
1042 nodeMap[edgeIt->second.first] = node1;
1046 node1 = nodeMap.at(edgeIt->second.first);
1048 if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
1052 if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
1054 feat = nodeFeatMap.at(edgeIt->second.second);
1056 node2 =
new Node<T>(edgeIt->second.second, feat);
1057 nodeMap[edgeIt->second.second] = node2;
1061 node2 = nodeMap.at(edgeIt->second.second);
1064 if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
1066 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1068 auto edge =
new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1073 auto edge =
new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1079 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1081 auto edge =
new DirectedEdge<T>(edgeIt->first, *node1, *node2);
1086 auto edge =
new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
1095 template <
typename T>
1096 const AdjacencyMatrix<T> Graph<T>::getAdjMatrix()
const
1098 AdjacencyMatrix<T> adj;
1099 auto edgeSetIt = edgeSet.begin();
1100 for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
1102 if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
1104 const DirectedEdge<T> *d_edge =
dynamic_cast<const DirectedEdge<T> *
>(*edgeSetIt);
1105 addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
1107 else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
1109 const UndirectedEdge<T> *ud_edge =
dynamic_cast<const UndirectedEdge<T> *
>(*edgeSetIt);
1111 addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
1112 addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
1122 template <
typename T>
1126 result.success =
false;
1127 result.errorMessage =
"";
1128 result.result = INF_DOUBLE;
1129 auto nodeSet = getNodeSet();
1130 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1133 result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
1136 if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1139 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
1142 const AdjacencyMatrix<T> adj = getAdjMatrix();
1147 std::map<const Node<T> *,
double> dist;
1149 for (
auto elem : adj)
1151 dist[elem.first] = INF_DOUBLE;
1157 std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1158 std::greater<std::pair<double, const Node<T> *>>>
1162 pq.push(std::make_pair(0.0, &source));
1170 const Node<T> *currentNode = pq.top().second;
1173 double currentDist = pq.top().first;
1179 if (adj.find(currentNode) != adj.end())
1181 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
1184 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1186 if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1189 if (currentDist + dw_edge->getWeight() < dist[elem.first])
1191 dist[elem.first] = currentDist + dw_edge->getWeight();
1192 pq.push(std::make_pair(dist[elem.first], elem.first));
1195 else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1198 if (currentDist + udw_edge->getWeight() < dist[elem.first])
1200 dist[elem.first] = currentDist + udw_edge->getWeight();
1201 pq.push(std::make_pair(dist[elem.first], elem.first));
1207 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1214 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1220 if (dist[&target] != INF_DOUBLE)
1222 result.success =
true;
1223 result.errorMessage =
"";
1224 result.result = dist[&target];
1227 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
1232 template <
typename T>
1236 std::vector<Node<T>> visited;
1237 auto nodeSet = getNodeSet();
1239 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1243 const AdjacencyMatrix<T> adj = getAdjMatrix();
1245 std::queue<const Node<T> *> tracker;
1248 visited.push_back(start);
1249 tracker.push(&start);
1250 while (!tracker.empty())
1252 const Node<T> *node = tracker.front();
1254 if (adj.find(node) != adj.end())
1256 for (
auto elem : adj.at(node))
1260 if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1262 visited.push_back(*(elem.first));
1263 tracker.push(elem.first);
1272 template <
typename T>
1276 std::vector<Node<T>> visited;
1277 auto nodeSet = getNodeSet();
1279 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1283 const AdjacencyMatrix<T> adj = getAdjMatrix();
1284 std::function<void(
const AdjacencyMatrix<T> &,
const Node<T> &, std::vector<
Node<T>> &)> explore;
1285 explore = [&explore](
const AdjacencyMatrix<T> &adj,
const Node<T> &node, std::vector<Node<T>> &visited) ->
void
1287 visited.push_back(node);
1288 if (adj.find(&node) != adj.end())
1290 for (
auto x : adj.at(&node))
1292 if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1294 explore(adj, *(x.first), visited);
1299 explore(adj, start, visited);
1304 template <
typename T>
1307 if (!isDirectedGraph())
1311 enum nodeStates : uint8_t
1317 auto nodeSet = this->getNodeSet();
1318 auto adjMatrix = this->getAdjMatrix();
1327 std::map<unsigned long, nodeStates> state;
1328 for (
auto node : nodeSet)
1330 state[node->getId()] = not_visited;
1332 int stateCounter = 0;
1335 for (
auto node : nodeSet)
1340 if (state[node->getId()] == not_visited)
1343 std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &,
const Node<T> *)> isCyclicDFSHelper;
1344 isCyclicDFSHelper = [
this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states,
const Node<T> *node)
1347 states[node->getId()] = in_stack;
1351 auto const it = adjMatrix.find(node);
1352 if (it != adjMatrix.end())
1354 for (
auto child : it->second)
1358 auto state_of_child = states.at((std::get<0>(child))->getId());
1359 if (state_of_child == not_visited)
1361 if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1366 else if (state_of_child == in_stack)
1378 states[node->getId()] = visited;
1382 if (isCyclicDFSHelper(adjMatrix, state, node))
1394 template <
typename T>
1397 if (!isDirectedGraph())
1401 auto adjMatrix = this->getAdjMatrix();
1402 auto nodeSet = this->getNodeSet();
1404 std::map<unsigned long, unsigned int> indegree;
1405 for (
auto node : nodeSet)
1407 indegree[node->getId()] = 0;
1410 for (
auto const &list : adjMatrix)
1412 auto children = list.second;
1413 for (
auto const &child : children)
1415 indegree[std::get<0>(child)->getId()]++;
1419 std::queue<const Node<T> *> can_be_solved;
1420 for (
auto node : nodeSet)
1424 if (!indegree[node->getId()])
1426 can_be_solved.emplace(&(*node));
1431 auto remain = this->getNodeSet().size();
1433 while (!can_be_solved.empty())
1435 auto solved = can_be_solved.front();
1437 can_be_solved.pop();
1442 auto it = adjMatrix.find(solved);
1443 if (it != adjMatrix.end())
1445 for (
auto child : it->second)
1448 if (--indegree[std::get<0>(child)->getId()] == 0)
1452 can_be_solved.emplace(std::get<0>(child));
1460 return !(remain == 0);
1463 template <
typename T>
1466 auto edgeSet = this->getEdgeSet();
1467 for (
auto edge : edgeSet)
1469 if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1479 template <
typename T>
1482 if (format == InputOutputFormat::STANDARD_CSV)
1484 return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1486 else if (format == InputOutputFormat::STANDARD_TSV)
1488 return writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1497 template <
typename T>
1500 if (format == InputOutputFormat::STANDARD_CSV)
1502 return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1504 else if (format == InputOutputFormat::STANDARD_TSV)
1506 return readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1516 template <
typename T>
1517 std::ostream &operator<<(std::ostream &os,
const Node<T> &node)
1520 <<
" Id:\t" << node.id <<
"\n Data:\t" << node.data <<
"\n}";
1524 template <
typename T>
1525 std::ostream &operator<<(std::ostream &os,
const Edge<T> &edge)
1527 os <<
"((Node: " << edge.nodePair.first->getId() <<
")) ?----- |Edge: " << edge.id <<
"|-----? ((Node: " << edge.nodePair.second->getId() <<
"))";
1531 template <
typename T>
1532 std::ostream &operator<<(std::ostream &os,
const DirectedEdge<T> &edge)
1534 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1538 template <
typename T>
1539 std::ostream &operator<<(std::ostream &os,
const UndirectedEdge<T> &edge)
1541 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1545 template <
typename T>
1546 std::ostream &operator<<(std::ostream &os,
const DirectedWeightedEdge<T> &edge)
1548 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1552 template <
typename T>
1553 std::ostream &operator<<(std::ostream &os,
const UndirectedWeightedEdge<T> &edge)
1555 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1559 template <
typename T>
1560 std::ostream &operator<<(std::ostream &os,
const AdjacencyMatrix<T> &adj)
1562 os <<
"Adjacency Matrix:\n";
1563 auto it = adj.begin();
1564 unsigned long max_column = 0;
1565 for (it; it != adj.end(); ++it)
1567 if (it->second.size() > max_column)
1569 max_column = it->second.size();
1572 if (max_column == 0)
1574 os <<
"ERROR in Print\n";
1581 for (
int i = 0; i < max_column; i++)
1586 for (it; it != adj.end(); ++it)
1588 os <<
"|N" << it->first->getId() <<
"|";
1589 auto it2 = it->second.begin();
1590 for (it2; it2 != it->second.end(); ++it2)
1592 os <<
"N" << it2->first->getId() <<
",E" << it2->second->getId() <<
"|";
1595 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:1273
enum CXXGRAPH::Graph::E_InputOutputFormat InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
bool isCyclicDirectedGraphBFS() const
This function uses BFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:1395
int writeToFile(InputOutputFormat format=InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool writeNodeFeat=false, bool writeEdgeWeight=false) const
This function write the graph in an output file.
Definition: Graph.hpp:1480
bool isDirectedGraph() const
This function checks if a graph is directed.
Definition: Graph.hpp:1464
const DijkstraResult dijkstra(const Node< T > &source, const Node< T > &target) const
Function runs the dijkstra algorithm for some source node and target node in the graph and returns th...
Definition: Graph.hpp:1123
bool isCyclicDirectedGraphDFS() const
This function uses DFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:1305
int readFromFile(InputOutputFormat format=InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool readNodeFeat=false, bool readEdgeWeight=false)
This function write the graph in an output file.
Definition: Graph.hpp:1498
const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const
Function performs the breadth first search algorithm over the graph.
Definition: Graph.hpp:1233
E_InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
Definition: Graph.hpp:478
@ STANDARD_CSV
A standard csv format.
Definition: Graph.hpp:479
@ STANDARD_TSV
A standard tsv format.
Definition: Graph.hpp:480
Definition: Graph.hpp:289
Definition: Graph.hpp:406
Definition: Graph.hpp:122