45 #include "Edge/Weighted.hpp"
46 #include "Node/Node.hpp"
47 #include "Edge/Edge.hpp"
48 #include "Edge/DirectedEdge.hpp"
49 #include "Edge/UndirectedEdge.hpp"
50 #include "Edge/DirectedWeightedEdge.hpp"
51 #include "Edge/UndirectedWeightedEdge.hpp"
52 #include "Utility/ThreadSafe.hpp"
53 #include "Utility/Writer.hpp"
54 #include "Utility/Reader.hpp"
55 #include "Utility/ConstString.hpp"
56 #include "Utility/ConstValue.hpp"
57 #include "Utility/Typedef.hpp"
58 #include "Partitioning/Partition.hpp"
59 #include "Partitioning/PartitionAlgorithm.hpp"
60 #include "Partitioning/Partitioner.hpp"
61 #include "Partitioning/Utility/Globals.hpp"
65 namespace PARTITIONING{
71 std::ostream &operator<<(std::ostream &o,
const Graph<T> &graph);
73 std::ostream &operator<<(std::ostream &o,
const AdjacencyMatrix<T> &adj);
80 std::list<const Edge<T> *> edgeSet;
81 void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix,
const Node<T> *nodeFrom,
const Node<T> *nodeTo,
const Edge<T> *edge)
const;
82 int writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
83 int readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
84 int writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
85 int readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
86 void recreateGraphFromReadFiles(std::map<
unsigned long, std::pair<unsigned long, unsigned long>> &edgeMap, std::map<unsigned long, bool> &edgeDirectedMap, std::map<unsigned long, T> &nodeFeatMap, std::map<unsigned long, double> &edgeWeightMap);
87 int compressFile(
const std::string &inputFile,
const std::string &outputFile)
const;
88 int decompressFile(
const std::string &inputFile,
const std::string &outputFile)
const;
102 virtual const std::list<const Edge<T> *> &
getEdgeSet()
const;
129 virtual void removeEdge(
unsigned long edgeId);
138 virtual const std::list<const Node<T> *>
getNodeSet()
const;
148 virtual const std::optional<const Edge<T> *>
getEdge(
unsigned long edgeId)
const;
317 virtual 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;
332 virtual 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);
343 virtual PartitionMap<T>
partitionGraph(PARTITIONING::PartitionAlgorithm algorithm,
unsigned int numberOfPartitions)
const;
345 friend std::ostream &operator<<<>(std::ostream &os,
const Graph<T> &graph);
346 friend std::ostream &operator<<<>(std::ostream &os,
const AdjacencyMatrix<T> &adj);
349 template <
typename T>
352 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
354 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
355 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
357 this->edgeSet.push_back(*edgeSetIt);
362 template <
typename T>
368 template <
typename T>
371 this->edgeSet.clear();
372 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
374 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
375 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
377 this->edgeSet.push_back(*edgeSetIt);
382 template <
typename T>
385 if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](
const Edge<T> *edge_a)
386 { return (*edge == *edge_a); }) == edgeSet.end())
388 edgeSet.push_back(edge);
392 template <
typename T>
396 if (edgeOpt.has_value())
398 edgeSet.erase(std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeOpt](
const Edge<T> *edge)
399 { return (*(edgeOpt.value()) == *edge); }));
403 template <
typename T>
406 std::list<const Node<T> *> nodeSet;
407 for (
auto edge : edgeSet)
409 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
410 { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
412 nodeSet.push_back(edge->getNodePair().first);
414 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
415 { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
417 nodeSet.push_back(edge->getNodePair().second);
423 template <
typename T>
427 auto it = edgeSet.begin();
428 for (it; it != edgeSet.end(); ++it)
430 if ((*it)->getId() == edgeId)
439 template <
typename T>
442 std::pair<const Node<T> *,
const Edge<T> *> elem = {nodeTo, edge};
443 adjMatrix[nodeFrom].push_back(elem);
448 template <
typename T>
449 int Graph<T>::writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
451 std::ofstream ofileGraph;
452 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
453 ofileGraph.open(completePathToFileGraph);
454 if (!ofileGraph.is_open())
459 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
460 { ofileGraph << e->getId() <<
"," << e->getNodePair().first->getId() <<
"," << e->getNodePair().second->getId() <<
"," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
461 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
466 std::ofstream ofileNodeFeat;
467 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
469 ofileNodeFeat.open(completePathToFileNodeFeat);
470 if (!ofileNodeFeat.is_open())
475 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
476 { ofileNodeFeat << node->getId() <<
"," << node->getData() << std::endl; };
477 auto nodeSet = getNodeSet();
478 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
479 ofileNodeFeat.close();
484 std::ofstream ofileEdgeWeight;
485 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
487 ofileEdgeWeight.open(completePathToFileEdgeWeight);
488 if (!ofileEdgeWeight.is_open())
493 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
494 { 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; };
496 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
497 ofileEdgeWeight.close();
502 template <
typename T>
503 int Graph<T>::readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
505 std::ifstream ifileGraph;
506 std::ifstream ifileNodeFeat;
507 std::ifstream ifileEdgeWeight;
508 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
509 std::map<unsigned long, bool> edgeDirectedMap;
510 std::map<unsigned long, T> nodeFeatMap;
511 std::map<unsigned long, double> edgeWeightMap;
512 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
513 ifileGraph.open(completePathToFileGraph);
514 if (!ifileGraph.is_open())
522 unsigned long edgeId;
523 unsigned long nodeId1;
524 unsigned long nodeId2;
526 ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
527 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
528 edgeDirectedMap[edgeId] = directed;
529 if (ifileGraph.fail() || ifileGraph.eof())
531 ifileGraph.ignore(128,
'\n');
537 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
539 ifileNodeFeat.open(completePathToFileNodeFeat);
540 if (!ifileNodeFeat.is_open())
547 unsigned long nodeId;
549 ifileNodeFeat >> nodeId >> comma >> nodeFeat;
550 nodeFeatMap[nodeId] = nodeFeat;
551 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
553 ifileNodeFeat.ignore(128,
'\n');
555 ifileNodeFeat.close();
560 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
562 ifileEdgeWeight.open(completePathToFileEdgeWeight);
563 if (!ifileEdgeWeight.is_open())
570 unsigned long edgeId;
573 ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
576 edgeWeightMap[edgeId] = weight;
578 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
580 ifileEdgeWeight.ignore(128,
'\n');
582 ifileEdgeWeight.close();
584 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
588 template <
typename T>
589 int Graph<T>::writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
591 std::ofstream ofileGraph;
592 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
593 ofileGraph.open(completePathToFileGraph);
594 if (!ofileGraph.is_open())
599 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
600 { 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; };
601 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
606 std::ofstream ofileNodeFeat;
607 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
609 ofileNodeFeat.open(completePathToFileNodeFeat);
610 if (!ofileNodeFeat.is_open())
615 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
616 { ofileNodeFeat << node->getId() <<
"\t" << node->getData() << std::endl; };
617 auto nodeSet = getNodeSet();
618 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
619 ofileNodeFeat.close();
624 std::ofstream ofileEdgeWeight;
625 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
627 ofileEdgeWeight.open(completePathToFileEdgeWeight);
628 if (!ofileEdgeWeight.is_open())
633 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
634 { 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; };
636 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
637 ofileEdgeWeight.close();
642 template <
typename T>
643 int Graph<T>::readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
645 std::ifstream ifileGraph;
646 std::ifstream ifileNodeFeat;
647 std::ifstream ifileEdgeWeight;
648 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
649 std::map<unsigned long, bool> edgeDirectedMap;
650 std::map<unsigned long, T> nodeFeatMap;
651 std::map<unsigned long, double> edgeWeightMap;
652 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
653 ifileGraph.open(completePathToFileGraph);
654 if (!ifileGraph.is_open())
661 unsigned long edgeId;
662 unsigned long nodeId1;
663 unsigned long nodeId2;
665 ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
666 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
667 edgeDirectedMap[edgeId] = directed;
668 if (ifileGraph.fail() || ifileGraph.eof())
670 ifileGraph.ignore(128,
'\n');
676 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
678 ifileNodeFeat.open(completePathToFileNodeFeat);
679 if (!ifileNodeFeat.is_open())
686 unsigned long nodeId;
688 ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
689 nodeFeatMap[nodeId] = nodeFeat;
690 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
692 ifileNodeFeat.ignore(128,
'\n');
694 ifileNodeFeat.close();
699 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
701 ifileEdgeWeight.open(completePathToFileEdgeWeight);
702 if (!ifileEdgeWeight.is_open())
709 unsigned long edgeId;
712 ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
715 edgeWeightMap[edgeId] = weight;
717 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
719 ifileEdgeWeight.ignore(128,
'\n');
721 ifileEdgeWeight.close();
723 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
727 template <
typename T>
728 void Graph<T>::recreateGraphFromReadFiles(std::map<
unsigned long, std::pair<unsigned long, unsigned long>> &edgeMap, std::map<unsigned long, bool> &edgeDirectedMap, std::map<unsigned long, T> &nodeFeatMap, std::map<unsigned long, double> &edgeWeightMap)
730 std::map<unsigned long, Node<T> *> nodeMap;
731 for (
auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
733 Node<T> *node1 =
nullptr;
734 Node<T> *node2 =
nullptr;
735 if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
739 if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
741 feat = nodeFeatMap.at(edgeIt->second.first);
743 node1 =
new Node<T>(edgeIt->second.first, feat);
744 nodeMap[edgeIt->second.first] = node1;
748 node1 = nodeMap.at(edgeIt->second.first);
750 if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
754 if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
756 feat = nodeFeatMap.at(edgeIt->second.second);
758 node2 =
new Node<T>(edgeIt->second.second, feat);
759 nodeMap[edgeIt->second.second] = node2;
763 node2 = nodeMap.at(edgeIt->second.second);
766 if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
768 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
770 auto edge =
new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
775 auto edge =
new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
781 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
783 auto edge =
new DirectedEdge<T>(edgeIt->first, *node1, *node2);
788 auto edge =
new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
795 template <
typename T>
796 int Graph<T>::compressFile(
const std::string &inputFile,
const std::string &outputFile)
const
806 std::string content((std::istreambuf_iterator<char>(ifs)),
807 (std::istreambuf_iterator<char>()));
809 const char *content_ptr = content.c_str();
810 gzFile outFileZ = gzopen(outputFile.c_str(),
"wb");
811 if (outFileZ == NULL)
817 unsigned int zippedBytes;
818 zippedBytes = gzwrite(outFileZ, content_ptr, strlen(content_ptr));
825 template <
typename T>
826 int Graph<T>::decompressFile(
const std::string &inputFile,
const std::string &outputFile)
const
829 gzFile inFileZ = gzopen(inputFile.c_str(),
"rb");
835 unsigned char unzipBuffer[8192];
836 unsigned int unzippedBytes;
837 std::vector<unsigned char> unzippedData;
839 ofs.open(outputFile);
847 unzippedBytes = gzread(inFileZ, unzipBuffer, 8192);
848 if (unzippedBytes > 0)
850 unzippedData.insert(unzippedData.end(), unzipBuffer, unzipBuffer + unzippedBytes);
857 for (
auto c : unzippedData)
867 template <
typename T>
870 AdjacencyMatrix<T> adj;
871 auto edgeSetIt = edgeSet.begin();
872 for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
874 if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
877 addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
879 else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
883 addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
884 addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
894 template <
typename T>
898 result.success =
false;
899 result.errorMessage =
"";
900 result.result = INF_DOUBLE;
902 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
905 result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
908 if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
911 result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
919 std::map<const Node<T> *,
double> dist;
921 for (
auto elem : adj)
923 dist[elem.first] = INF_DOUBLE;
929 std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
930 std::greater<std::pair<double, const Node<T> *>>>
934 pq.push(std::make_pair(0.0, &source));
942 const Node<T> *currentNode = pq.top().second;
945 double currentDist = pq.top().first;
951 if (adj.find(currentNode) != adj.end())
953 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
956 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
958 if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
961 if (currentDist + dw_edge->getWeight() < dist[elem.first])
963 dist[elem.first] = currentDist + dw_edge->getWeight();
964 pq.push(std::make_pair(dist[elem.first], elem.first));
967 else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
970 if (currentDist + udw_edge->getWeight() < dist[elem.first])
972 dist[elem.first] = currentDist + udw_edge->getWeight();
973 pq.push(std::make_pair(dist[elem.first], elem.first));
979 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
986 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
992 if (dist[&target] != INF_DOUBLE)
994 result.success =
true;
995 result.errorMessage =
"";
996 result.result = dist[&target];
999 result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
1004 template <
typename T>
1008 result.success =
false;
1009 result.errorMessage =
"";
1010 result.result = INF_DOUBLE;
1012 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1015 result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1018 if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1021 result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
1025 std::map<const Node<T> *,
double> dist, currentDist;
1027 auto n = nodeSet.size();
1028 for (
auto elem : nodeSet)
1030 dist[elem] = INF_DOUBLE;
1031 currentDist[elem] = INF_DOUBLE;
1038 auto earlyStopping =
false;
1040 for (
int i=0; i<n-1; i++)
1045 for (
auto edge : edgeSet)
1047 auto elem = edge->getNodePair();
1048 if (edge->isWeighted().has_value() && edge->isWeighted().value())
1050 auto edge_weight = (
dynamic_cast<const Weighted *
>(edge))->getWeight();
1051 if (dist[elem.first] + edge_weight < dist[elem.second])
1052 dist[elem.second] = dist[elem.first] + edge_weight;
1057 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1062 for (
const auto& [key, value] : dist) {
1063 if (currentDist[key]!=value)
1069 for (
const auto& [key, value] : dist) {
1070 currentDist[key] = value;
1074 earlyStopping =
true;
1083 for (
auto edge : edgeSet)
1085 auto elem = edge->getNodePair();
1086 auto edge_weight = (
dynamic_cast<const Weighted *
>(edge))->getWeight();
1087 if (dist[elem.first] + edge_weight < dist[elem.second])
1089 result.success =
true;
1090 result.negativeCycle =
true;
1091 result.errorMessage =
"";
1097 if (dist[&target] != INF_DOUBLE)
1099 result.success =
true;
1100 result.errorMessage =
"";
1101 result.negativeCycle =
false;
1102 result.result = dist[&target];
1105 result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
1110 template <
typename T>
1114 result.success =
false;
1115 result.errorMessage =
"";
1116 std::map<std::pair<unsigned long, unsigned long>,
double> pairwise_dist;
1120 for (
auto elem1 : nodeSet)
1122 for (
auto elem2 : nodeSet)
1124 auto key = std::make_pair(elem1->getId(), elem2->getId());
1126 pairwise_dist[key] = INF_DOUBLE;
1128 pairwise_dist[key] = 0.0;
1135 for (
auto edge : edgeSet)
1137 auto elem = edge->getNodePair();
1138 if (edge->isWeighted().has_value() && edge->isWeighted().value())
1140 auto edgeWeight = (
dynamic_cast<const Weighted *
>(edge))->getWeight();
1141 auto key = std::make_pair(elem.first->getId(), elem.second->getId());
1142 pairwise_dist[key] = edgeWeight;
1148 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1153 for (
auto k : nodeSet)
1156 for (
auto src : nodeSet)
1160 auto src_k = std::make_pair(src->getId(), k->getId());
1161 for (
auto dst : nodeSet)
1166 auto src_dst = std::make_pair(src->getId(), dst->getId());
1167 auto k_dst = std::make_pair(k->getId(), dst->getId());
1168 if (pairwise_dist[src_dst] > (pairwise_dist[src_k] + pairwise_dist[k_dst]) && (pairwise_dist[k_dst] != INF_DOUBLE && pairwise_dist[src_k] != INF_DOUBLE))
1169 pairwise_dist[src_dst] = pairwise_dist[src_k] + pairwise_dist[k_dst];
1174 result.success =
true;
1177 for (
auto node : nodeSet)
1179 auto diag = std::make_pair(node->getId(), node->getId());
1180 if (pairwise_dist[diag] < 0.)
1182 result.negativeCycle =
true;
1186 result.result = std::move(pairwise_dist);
1190 template <
typename T>
1194 result.success =
false;
1195 result.errorMessage =
"";
1196 result.mstCost = INF_DOUBLE;
1197 if (!isUndirectedGraph())
1199 result.errorMessage = ERR_DIR_GRAPH;
1203 auto n = nodeSet.size();
1207 std::map<const Node<T> *,
double> dist;
1208 for (
auto elem : adj)
1210 dist[elem.first] = INF_DOUBLE;
1216 std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1217 std::greater<std::pair<double, const Node<T> *>>>
1221 auto source = nodeSet.front();
1222 pq.push(std::make_pair(0.0, source));
1224 result.result.push_back(source->getId());
1229 const Node<T> *currentNode = pq.top().second;
1230 auto nodeId = currentNode->getId();
1231 if (std::find(result.result.begin(), result.result.end(), nodeId) == result.result.end())
1233 result.result.push_back(nodeId);
1234 result.mstCost += pq.top().first;
1240 if (adj.find(currentNode) != adj.end())
1242 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
1245 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1249 (udw_edge->getWeight() < dist[elem.first]) &&
1250 (std::find(result.result.begin(), result.result.end(), elem.first->getId()) == result.result.end())
1254 dist[elem.first] = udw_edge->getWeight();
1255 pq.push(std::make_pair(dist[elem.first], elem.first));
1261 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1267 result.success =
true;
1271 template <
typename T>
1275 std::vector<Node<T>> visited;
1278 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1284 std::queue<const Node<T> *> tracker;
1287 visited.push_back(start);
1288 tracker.push(&start);
1289 while (!tracker.empty())
1291 const Node<T> *node = tracker.front();
1293 if (adj.find(node) != adj.end())
1295 for (
auto elem : adj.at(node))
1299 if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1301 visited.push_back(*(elem.first));
1302 tracker.push(elem.first);
1311 template <
typename T>
1315 std::vector<Node<T>> visited;
1318 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1323 std::function<void(
const AdjacencyMatrix<T> &,
const Node<T> &, std::vector<
Node<T>> &)> explore;
1324 explore = [&explore](
const AdjacencyMatrix<T> &adj,
const Node<T> &node, std::vector<Node<T>> &visited) ->
void
1326 visited.push_back(node);
1327 if (adj.find(&node) != adj.end())
1329 for (
auto x : adj.at(&node))
1331 if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1333 explore(adj, *(x.first), visited);
1338 explore(adj, start, visited);
1343 template <
typename T>
1346 if (!isDirectedGraph())
1350 enum nodeStates : uint8_t
1366 std::map<unsigned long, nodeStates> state;
1367 for (
auto node : nodeSet)
1369 state[node->getId()] = not_visited;
1371 int stateCounter = 0;
1374 for (
auto node : nodeSet)
1379 if (state[node->getId()] == not_visited)
1382 std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &,
const Node<T> *)> isCyclicDFSHelper;
1383 isCyclicDFSHelper = [
this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states,
const Node<T> *node)
1386 states[node->getId()] = in_stack;
1390 auto const it = adjMatrix.find(node);
1391 if (it != adjMatrix.end())
1393 for (
auto child : it->second)
1397 auto state_of_child = states.at((std::get<0>(child))->getId());
1398 if (state_of_child == not_visited)
1400 if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1405 else if (state_of_child == in_stack)
1417 states[node->getId()] = visited;
1421 if (isCyclicDFSHelper(adjMatrix, state, node))
1433 template <
typename T>
1436 if (!isDirectedGraph())
1443 std::map<unsigned long, unsigned int> indegree;
1444 for (
auto node : nodeSet)
1446 indegree[node->getId()] = 0;
1449 for (
auto const &list : adjMatrix)
1451 auto children = list.second;
1452 for (
auto const &child : children)
1454 indegree[std::get<0>(child)->getId()]++;
1458 std::queue<const Node<T> *> can_be_solved;
1459 for (
auto node : nodeSet)
1463 if (!indegree[node->getId()])
1465 can_be_solved.emplace(&(*node));
1472 while (!can_be_solved.empty())
1474 auto solved = can_be_solved.front();
1476 can_be_solved.pop();
1481 auto it = adjMatrix.find(solved);
1482 if (it != adjMatrix.end())
1484 for (
auto child : it->second)
1487 if (--indegree[std::get<0>(child)->getId()] == 0)
1491 can_be_solved.emplace(std::get<0>(child));
1499 return !(remain == 0);
1502 template <
typename T>
1506 for (
auto edge : edgeSet)
1508 if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1518 template <
typename T>
1522 for (
auto edge : edgeSet)
1524 if ((edge->isDirected().has_value() && edge->isDirected().value()))
1534 template <
typename T>
1538 result.success =
false;
1543 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1546 result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1554 unsigned int V = nodeSet.size();
1555 std::map<const Node<T> *, std::pair<long, const Node<T> *>> dist;
1558 for (
auto node : nodeSet)
1560 dist[&(*node)].first = std::numeric_limits<long>::max();
1565 std::list<const Node<T> *> B[maxWeight * V + 1];
1567 B[0].push_back(&source);
1568 dist[&source].first = 0;
1575 while (B[idx].size() == 0 && idx < maxWeight * V)
1581 if (idx == maxWeight * V)
1587 auto u = B[idx].front();
1592 for (
auto i = adj[u].begin(); i != adj[u].end(); ++i)
1594 auto v = (*i).first;
1596 if ((*i).second->isWeighted().has_value() && (*i).second->isWeighted().value())
1598 if ((*i).second->isDirected().has_value() && (*i).second->isDirected().value())
1601 weight = dw_edge->getWeight();
1603 else if ((*i).second->isDirected().has_value() && !(*i).second->isDirected().value())
1606 weight = udw_edge->getWeight();
1611 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1618 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1621 auto u_i = std::find_if(dist.begin(), dist.end(), [u](std::pair<
const Node<T> *, std::pair<
long,
const Node<T> *>>
const &it)
1622 { return (*u == *(it.first)); });
1624 auto v_i = std::find_if(dist.begin(), dist.end(), [v](std::pair<
const Node<T> *, std::pair<
long,
const Node<T> *>>
const &it)
1625 { return (*v == *(it.first)); });
1626 long du = u_i->second.first;
1627 long dv = v_i->second.first;
1630 if (dv > du + weight)
1635 if (dv != std::numeric_limits<long>::max())
1637 auto findIter = std::find(B[dv].begin(), B[dv].end(), dist[v].second);
1638 B[dv].erase(findIter);
1642 dist[v].first = du + weight;
1646 B[dv].push_front(v);
1649 dist[v].second = *(B[dv].begin());
1653 for (
auto dist_i : dist)
1655 result.minDistanceMap[dist_i.first->getId()] = dist_i.second.first;
1657 result.success =
true;
1662 template <
typename T>
1665 std::vector<Node<T>> result;
1669 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1674 std::list<const Node<T> *> C1;
1675 for (
auto const node : nodeSet)
1678 if (std::find_if(C.begin(), C.end(), [node](
const Node<T> nodeC)
1679 { return (*node == nodeC); }) == C.end())
1685 std::vector<Node<T>> M;
1686 for (
auto const node : C1)
1689 M.insert(M.end(),reachableNodes.begin(),reachableNodes.end());
1694 if (std::find_if(M.begin(), M.end(), [nodeC](
const Node<T> nodeM)
1695 { return (nodeM == nodeC); }) == M.end())
1696 result.push_back(nodeC);
1701 template <
typename T>
1702 int Graph<T>::writeToFile(InputOutputFormat format,
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
1705 if (format == InputOutputFormat::STANDARD_CSV)
1707 result = writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1709 else if (format == InputOutputFormat::STANDARD_TSV)
1711 result = writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1718 if (result == 0 && compress)
1720 auto compress = [
this, &workingDir, &OFileName, &writeNodeFeat, &writeEdgeWeight](
const std::string &extension)
1722 std::string completePathToFileGraph = workingDir +
"/" + OFileName + extension;
1723 std::string completePathToFileGraphCompressed = workingDir +
"/" + OFileName + extension +
".gz";
1724 int _result = compressFile(completePathToFileGraph, completePathToFileGraphCompressed);
1727 _result = remove(completePathToFileGraph.c_str());
1733 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat" + extension;
1734 std::string completePathToFileNodeFeatCompressed = workingDir +
"/" + OFileName +
"_NodeFeat" + extension +
".gz";
1735 _result = compressFile(completePathToFileNodeFeat, completePathToFileNodeFeatCompressed);
1738 _result = remove(completePathToFileNodeFeat.c_str());
1744 if (writeEdgeWeight)
1746 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight" + extension;
1747 std::string completePathToFileEdgeWeightCompressed = workingDir +
"/" + OFileName +
"_EdgeWeight" + extension +
".gz";
1748 _result = compressFile(completePathToFileEdgeWeight, completePathToFileEdgeWeightCompressed);
1751 _result = remove(completePathToFileEdgeWeight.c_str());
1757 if (format == InputOutputFormat::STANDARD_CSV)
1759 auto result = compress(
".csv");
1761 else if (format == InputOutputFormat::STANDARD_TSV)
1763 auto result = compress(
".tsv");
1774 template <
typename T>
1775 int Graph<T>::readFromFile(InputOutputFormat format,
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
1780 auto decompress = [
this, &workingDir, &OFileName, &readNodeFeat, &readEdgeWeight](
const std::string &extension)
1782 std::string completePathToFileGraph = workingDir +
"/" + OFileName + extension;
1783 std::string completePathToFileGraphCompressed = workingDir +
"/" + OFileName + extension +
".gz";
1784 int _result = decompressFile(completePathToFileGraphCompressed, completePathToFileGraph);
1789 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat" + extension;
1790 std::string completePathToFileNodeFeatCompressed = workingDir +
"/" + OFileName +
"_NodeFeat" + extension +
".gz";
1791 _result = decompressFile(completePathToFileNodeFeatCompressed, completePathToFileNodeFeat);
1798 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight" + extension;
1799 std::string completePathToFileEdgeWeightCompressed = workingDir +
"/" + OFileName +
"_EdgeWeight" + extension +
".gz";
1800 _result = decompressFile(completePathToFileEdgeWeightCompressed, completePathToFileEdgeWeight);
1805 if (format == InputOutputFormat::STANDARD_CSV)
1807 result = decompress(
".csv");
1809 else if (format == InputOutputFormat::STANDARD_TSV)
1811 result = decompress(
".tsv");
1821 if (format == InputOutputFormat::STANDARD_CSV)
1823 result = readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1825 else if (format == InputOutputFormat::STANDARD_TSV)
1827 result = readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1838 template <
typename T>
1841 PartitionMap<T> partitionMap;
1846 partitionMap = partitionState.getPartitionMap();
1848 return partitionMap;
1852 template <
typename T>
1853 std::ostream &operator<<(std::ostream &os,
const Graph<T> &graph){
1856 auto it = edgeList.begin();
1857 for(it; it != edgeList.end(); ++it){
1858 if (((*it)->isDirected().has_value()&& (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
1860 os << dynamic_cast<const DirectedWeightedEdge<T> &>(**it) <<
"\n";
1862 else if (((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
1864 os << dynamic_cast<const DirectedEdge<T> &>(**it) <<
"\n";
1866 else if (!((*it)->isDirected().has_value() && (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
1868 os << dynamic_cast<const UndirectedWeightedEdge<T> &>(**it) <<
"\n";
1870 else if (!((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
1872 os << dynamic_cast<const UndirectedEdge<T> &>(**it) <<
"\n";
1882 template <
typename T>
1883 std::ostream &operator<<(std::ostream &os,
const AdjacencyMatrix<T> &adj)
1885 os <<
"Adjacency Matrix:\n";
1886 auto it = adj.begin();
1887 unsigned long max_column = 0;
1888 for (it; it != adj.end(); ++it)
1890 if (it->second.size() > max_column)
1892 max_column = it->second.size();
1895 if (max_column == 0)
1897 os <<
"ERROR in Print\n";
1904 for (
int i = 0; i < max_column; i++)
1909 for (it; it != adj.end(); ++it)
1911 os <<
"|N" << it->first->getId() <<
"|";
1912 auto it2 = it->second.begin();
1913 for (it2; it2 != it->second.end(); ++it2)
1915 os <<
"N" << it2->first->getId() <<
",E" << it2->second->getId() <<
"|";
1918 for (
int i = 0; i < max_column; i++)
Definition: DirectedEdge.hpp:39
Definition: DirectedWeightedEdge.hpp:42
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:78
virtual const FWResult floydWarshall() const
Function runs the floyd-warshall algorithm and returns the shortest distance of all pair of nodes....
Definition: Graph.hpp:1111
virtual const std::vector< Node< T > > depth_first_search(const Node< T > &start) const
Function performs the depth first search algorithm over the graph Note: No Thread Safe.
Definition: Graph.hpp:1312
virtual bool isUndirectedGraph() const
This function checks if a graph is undirected Note: No Thread Safe.
Definition: Graph.hpp:1519
virtual const std::list< const Edge< T > * > & getEdgeSet() const
Function that return the Edge set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:363
virtual const std::optional< const Edge< T > * > getEdge(unsigned long edgeId) const
Function that return an Edge with specific ID if Exist in the Graph Note: No Thread Safe.
Definition: Graph.hpp:424
virtual 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:1434
virtual void removeEdge(unsigned long edgeId)
Function remove an Edge from the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:393
virtual 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 Note: No Thread Safe.
Definition: Graph.hpp:1702
virtual bool isDirectedGraph() const
This function checks if a graph is directed Note: No Thread Safe.
Definition: Graph.hpp:1503
virtual const DialResult dial(const Node< T > &source, int maxWeight) const
This function write the graph in an output file Note: No Thread Safe.
Definition: Graph.hpp:1535
virtual const std::vector< Node< T > > graph_slicing(const Node< T > &start) const
This function performs Graph Slicing based on connectivity.
Definition: Graph.hpp:1663
virtual 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:895
virtual 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:1344
virtual void addEdge(const Edge< T > *edge)
Function add an Edge to the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:383
virtual const PrimResult prim() const
Function runs the prim algorithm and returns the minimum spanning tree if the graph is undirected....
Definition: Graph.hpp:1191
virtual PartitionMap< T > partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
This function partition a graph in a set of partitions Note: No Thread Safe.
Definition: Graph.hpp:1839
virtual 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 read the graph from an input file Note: No Thread Safe.
Definition: Graph.hpp:1775
virtual const AdjacencyMatrix< T > getAdjMatrix() const
This function generate a list of adjacency matrix with every element of the matrix contain the node w...
Definition: Graph.hpp:868
virtual const std::list< const Node< T > * > getNodeSet() const
Function that return the Node Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:404
virtual const BellmanFordResult bellmanford(const Node< T > &source, const Node< T > &target) const
Function runs the bellman-ford algorithm for some source node and target node in the graph and return...
Definition: Graph.hpp:1005
virtual const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const
Function performs the breadth first search algorithm over the graph Note: No Thread Safe.
Definition: Graph.hpp:1272
virtual void setEdgeSet(std::list< const Edge< T > * > &edgeSet)
Function set the Edge Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:369
Definition: CoordinatedPartitionState.hpp:40
Definition: Globals.hpp:32
Definition: Partitioner.hpp:40
Definition: UndirectedEdge.hpp:39
Definition: UndirectedWeightedEdge.hpp:43
Definition: Weighted.hpp:28
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:71
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:101
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:62
Struct that contains the information about Floyd-Warshall Algorithm results.
Definition: Typedef.hpp:81
Struct that contains the information about Prim Algorithm results.
Definition: Typedef.hpp:91