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"
63 namespace PARTITIONING{
69 std::ostream &operator<<(std::ostream &o,
const Graph<T> &graph);
71 std::ostream &operator<<(std::ostream &o,
const AdjacencyMatrix<T> &adj);
78 std::list<const Edge<T> *> edgeSet;
79 void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix,
const Node<T> *nodeFrom,
const Node<T> *nodeTo,
const Edge<T> *edge)
const;
80 int writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
81 int readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
82 int writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
83 int readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
84 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);
85 int compressFile(
const std::string &inputFile,
const std::string &outputFile)
const;
86 int decompressFile(
const std::string &inputFile,
const std::string &outputFile)
const;
87 void greedyPartition(PartitionMap<T> &partitionMap)
const;
88 void HDRFPartition(PartitionMap<T> &partitionMap)
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;
261 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;
276 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);
287 virtual PartitionMap<T>
partitionGraph(PARTITIONING::PartitionAlgorithm algorithm,
unsigned int numberOfPartitions)
const;
289 friend std::ostream &operator<<<>(std::ostream &os,
const Graph<T> &graph);
290 friend std::ostream &operator<<<>(std::ostream &os,
const AdjacencyMatrix<T> &adj);
293 template <
typename T>
296 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
298 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
299 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
301 this->edgeSet.push_back(*edgeSetIt);
306 template <
typename T>
312 template <
typename T>
315 this->edgeSet.clear();
316 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
318 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
319 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
321 this->edgeSet.push_back(*edgeSetIt);
326 template <
typename T>
329 if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](
const Edge<T> *edge_a)
330 { return (*edge == *edge_a); }) == edgeSet.end())
332 edgeSet.push_back(edge);
336 template <
typename T>
340 if (edgeOpt.has_value())
342 edgeSet.erase(std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeOpt](
const Edge<T> *edge)
343 { return (*(edgeOpt.value()) == *edge); }));
347 template <
typename T>
350 std::list<const Node<T> *> nodeSet;
351 for (
auto edge : edgeSet)
353 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
354 { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
356 nodeSet.push_back(edge->getNodePair().first);
358 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
359 { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
361 nodeSet.push_back(edge->getNodePair().second);
367 template <
typename T>
371 auto it = edgeSet.begin();
372 for (it; it != edgeSet.end(); ++it)
374 if ((*it)->getId() == edgeId)
383 template <
typename T>
386 std::pair<const Node<T> *,
const Edge<T> *> elem = {nodeTo, edge};
387 adjMatrix[nodeFrom].push_back(elem);
392 template <
typename T>
393 int Graph<T>::writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
395 std::ofstream ofileGraph;
396 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
397 ofileGraph.open(completePathToFileGraph);
398 if (!ofileGraph.is_open())
403 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
404 { ofileGraph << e->getId() <<
"," << e->getNodePair().first->getId() <<
"," << e->getNodePair().second->getId() <<
"," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
405 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
410 std::ofstream ofileNodeFeat;
411 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
413 ofileNodeFeat.open(completePathToFileNodeFeat);
414 if (!ofileNodeFeat.is_open())
419 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
420 { ofileNodeFeat << node->getId() <<
"," << node->getData() << std::endl; };
421 auto nodeSet = getNodeSet();
422 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
423 ofileNodeFeat.close();
428 std::ofstream ofileEdgeWeight;
429 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
431 ofileEdgeWeight.open(completePathToFileEdgeWeight);
432 if (!ofileEdgeWeight.is_open())
437 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
438 { 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; };
440 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
441 ofileEdgeWeight.close();
446 template <
typename T>
447 int Graph<T>::readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
449 std::ifstream ifileGraph;
450 std::ifstream ifileNodeFeat;
451 std::ifstream ifileEdgeWeight;
452 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
453 std::map<unsigned long, bool> edgeDirectedMap;
454 std::map<unsigned long, T> nodeFeatMap;
455 std::map<unsigned long, double> edgeWeightMap;
456 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
457 ifileGraph.open(completePathToFileGraph);
458 if (!ifileGraph.is_open())
466 unsigned long edgeId;
467 unsigned long nodeId1;
468 unsigned long nodeId2;
470 ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
471 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
472 edgeDirectedMap[edgeId] = directed;
473 if (ifileGraph.fail() || ifileGraph.eof())
475 ifileGraph.ignore(128,
'\n');
481 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
483 ifileNodeFeat.open(completePathToFileNodeFeat);
484 if (!ifileNodeFeat.is_open())
491 unsigned long nodeId;
493 ifileNodeFeat >> nodeId >> comma >> nodeFeat;
494 nodeFeatMap[nodeId] = nodeFeat;
495 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
497 ifileNodeFeat.ignore(128,
'\n');
499 ifileNodeFeat.close();
504 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
506 ifileEdgeWeight.open(completePathToFileEdgeWeight);
507 if (!ifileEdgeWeight.is_open())
514 unsigned long edgeId;
517 ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
520 edgeWeightMap[edgeId] = weight;
522 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
524 ifileEdgeWeight.ignore(128,
'\n');
526 ifileEdgeWeight.close();
528 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
532 template <
typename T>
533 int Graph<T>::writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
535 std::ofstream ofileGraph;
536 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
537 ofileGraph.open(completePathToFileGraph);
538 if (!ofileGraph.is_open())
543 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
544 { 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; };
545 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
550 std::ofstream ofileNodeFeat;
551 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
553 ofileNodeFeat.open(completePathToFileNodeFeat);
554 if (!ofileNodeFeat.is_open())
559 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
560 { ofileNodeFeat << node->getId() <<
"\t" << node->getData() << std::endl; };
561 auto nodeSet = getNodeSet();
562 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
563 ofileNodeFeat.close();
568 std::ofstream ofileEdgeWeight;
569 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
571 ofileEdgeWeight.open(completePathToFileEdgeWeight);
572 if (!ofileEdgeWeight.is_open())
577 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
578 { 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; };
580 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
581 ofileEdgeWeight.close();
586 template <
typename T>
587 int Graph<T>::readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
589 std::ifstream ifileGraph;
590 std::ifstream ifileNodeFeat;
591 std::ifstream ifileEdgeWeight;
592 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
593 std::map<unsigned long, bool> edgeDirectedMap;
594 std::map<unsigned long, T> nodeFeatMap;
595 std::map<unsigned long, double> edgeWeightMap;
596 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
597 ifileGraph.open(completePathToFileGraph);
598 if (!ifileGraph.is_open())
605 unsigned long edgeId;
606 unsigned long nodeId1;
607 unsigned long nodeId2;
609 ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
610 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
611 edgeDirectedMap[edgeId] = directed;
612 if (ifileGraph.fail() || ifileGraph.eof())
614 ifileGraph.ignore(128,
'\n');
620 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
622 ifileNodeFeat.open(completePathToFileNodeFeat);
623 if (!ifileNodeFeat.is_open())
630 unsigned long nodeId;
632 ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
633 nodeFeatMap[nodeId] = nodeFeat;
634 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
636 ifileNodeFeat.ignore(128,
'\n');
638 ifileNodeFeat.close();
643 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
645 ifileEdgeWeight.open(completePathToFileEdgeWeight);
646 if (!ifileEdgeWeight.is_open())
653 unsigned long edgeId;
656 ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
659 edgeWeightMap[edgeId] = weight;
661 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
663 ifileEdgeWeight.ignore(128,
'\n');
665 ifileEdgeWeight.close();
667 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
671 template <
typename T>
672 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)
674 std::map<unsigned long, Node<T> *> nodeMap;
675 for (
auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
677 Node<T> *node1 =
nullptr;
678 Node<T> *node2 =
nullptr;
679 if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
683 if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
685 feat = nodeFeatMap.at(edgeIt->second.first);
687 node1 =
new Node<T>(edgeIt->second.first, feat);
688 nodeMap[edgeIt->second.first] = node1;
692 node1 = nodeMap.at(edgeIt->second.first);
694 if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
698 if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
700 feat = nodeFeatMap.at(edgeIt->second.second);
702 node2 =
new Node<T>(edgeIt->second.second, feat);
703 nodeMap[edgeIt->second.second] = node2;
707 node2 = nodeMap.at(edgeIt->second.second);
710 if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
712 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
714 auto edge =
new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
719 auto edge =
new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
725 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
727 auto edge =
new DirectedEdge<T>(edgeIt->first, *node1, *node2);
732 auto edge =
new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
739 template <
typename T>
740 int Graph<T>::compressFile(
const std::string &inputFile,
const std::string &outputFile)
const
750 std::string content((std::istreambuf_iterator<char>(ifs)),
751 (std::istreambuf_iterator<char>()));
753 const char *content_ptr = content.c_str();
754 gzFile outFileZ = gzopen(outputFile.c_str(),
"wb");
755 if (outFileZ == NULL)
761 unsigned int zippedBytes;
762 zippedBytes = gzwrite(outFileZ, content_ptr, strlen(content_ptr));
769 template <
typename T>
770 int Graph<T>::decompressFile(
const std::string &inputFile,
const std::string &outputFile)
const
773 gzFile inFileZ = gzopen(inputFile.c_str(),
"rb");
779 unsigned char unzipBuffer[8192];
780 unsigned int unzippedBytes;
781 std::vector<unsigned char> unzippedData;
783 ofs.open(outputFile);
791 unzippedBytes = gzread(inFileZ, unzipBuffer, 8192);
792 if (unzippedBytes > 0)
794 unzippedData.insert(unzippedData.end(), unzipBuffer, unzipBuffer + unzippedBytes);
801 for (
auto c : unzippedData)
811 template <
typename T>
812 void Graph<T>::greedyPartition(PartitionMap<T> &partitionMap)
const
814 unsigned int index = 0;
815 unsigned int numberOfPartitions = partitionMap.size();
816 if (index == numberOfPartitions)
821 auto edgeSet = getEdgeSet();
822 for (
auto edge : edgeSet)
824 partitionMap.at(index)->addEdge(edge);
826 index = index % numberOfPartitions;
830 template <
typename T>
831 void Graph<T>::HDRFPartition(PartitionMap<T> &partitionMap)
const
835 template <
typename T>
838 AdjacencyMatrix<T> adj;
839 auto edgeSetIt = edgeSet.begin();
840 for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
842 if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
845 addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
847 else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
851 addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
852 addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
862 template <
typename T>
866 result.success =
false;
867 result.errorMessage =
"";
868 result.result = INF_DOUBLE;
869 auto nodeSet = getNodeSet();
870 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
873 result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
876 if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
879 result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
882 const AdjacencyMatrix<T> adj = getAdjMatrix();
887 std::map<const Node<T> *,
double> dist;
889 for (
auto elem : adj)
891 dist[elem.first] = INF_DOUBLE;
897 std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
898 std::greater<std::pair<double, const Node<T> *>>>
902 pq.push(std::make_pair(0.0, &source));
910 const Node<T> *currentNode = pq.top().second;
913 double currentDist = pq.top().first;
919 if (adj.find(currentNode) != adj.end())
921 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
924 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
926 if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
929 if (currentDist + dw_edge->getWeight() < dist[elem.first])
931 dist[elem.first] = currentDist + dw_edge->getWeight();
932 pq.push(std::make_pair(dist[elem.first], elem.first));
935 else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
938 if (currentDist + udw_edge->getWeight() < dist[elem.first])
940 dist[elem.first] = currentDist + udw_edge->getWeight();
941 pq.push(std::make_pair(dist[elem.first], elem.first));
947 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
954 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
960 if (dist[&target] != INF_DOUBLE)
962 result.success =
true;
963 result.errorMessage =
"";
964 result.result = dist[&target];
967 result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
972 template <
typename T>
976 std::vector<Node<T>> visited;
977 auto nodeSet = getNodeSet();
979 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
983 const AdjacencyMatrix<T> adj = getAdjMatrix();
985 std::queue<const Node<T> *> tracker;
988 visited.push_back(start);
989 tracker.push(&start);
990 while (!tracker.empty())
992 const Node<T> *node = tracker.front();
994 if (adj.find(node) != adj.end())
996 for (
auto elem : adj.at(node))
1000 if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1002 visited.push_back(*(elem.first));
1003 tracker.push(elem.first);
1012 template <
typename T>
1016 std::vector<Node<T>> visited;
1017 auto nodeSet = getNodeSet();
1019 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1023 const AdjacencyMatrix<T> adj = getAdjMatrix();
1024 std::function<void(
const AdjacencyMatrix<T> &,
const Node<T> &, std::vector<
Node<T>> &)> explore;
1025 explore = [&explore](
const AdjacencyMatrix<T> &adj,
const Node<T> &node, std::vector<Node<T>> &visited) ->
void
1027 visited.push_back(node);
1028 if (adj.find(&node) != adj.end())
1030 for (
auto x : adj.at(&node))
1032 if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1034 explore(adj, *(x.first), visited);
1039 explore(adj, start, visited);
1044 template <
typename T>
1047 if (!isDirectedGraph())
1051 enum nodeStates : uint8_t
1057 auto nodeSet = this->getNodeSet();
1058 auto adjMatrix = this->getAdjMatrix();
1067 std::map<unsigned long, nodeStates> state;
1068 for (
auto node : nodeSet)
1070 state[node->getId()] = not_visited;
1072 int stateCounter = 0;
1075 for (
auto node : nodeSet)
1080 if (state[node->getId()] == not_visited)
1083 std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &,
const Node<T> *)> isCyclicDFSHelper;
1084 isCyclicDFSHelper = [
this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states,
const Node<T> *node)
1087 states[node->getId()] = in_stack;
1091 auto const it = adjMatrix.find(node);
1092 if (it != adjMatrix.end())
1094 for (
auto child : it->second)
1098 auto state_of_child = states.at((std::get<0>(child))->getId());
1099 if (state_of_child == not_visited)
1101 if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1106 else if (state_of_child == in_stack)
1118 states[node->getId()] = visited;
1122 if (isCyclicDFSHelper(adjMatrix, state, node))
1134 template <
typename T>
1137 if (!isDirectedGraph())
1141 auto adjMatrix = this->getAdjMatrix();
1142 auto nodeSet = this->getNodeSet();
1144 std::map<unsigned long, unsigned int> indegree;
1145 for (
auto node : nodeSet)
1147 indegree[node->getId()] = 0;
1150 for (
auto const &list : adjMatrix)
1152 auto children = list.second;
1153 for (
auto const &child : children)
1155 indegree[std::get<0>(child)->getId()]++;
1159 std::queue<const Node<T> *> can_be_solved;
1160 for (
auto node : nodeSet)
1164 if (!indegree[node->getId()])
1166 can_be_solved.emplace(&(*node));
1171 auto remain = this->getNodeSet().size();
1173 while (!can_be_solved.empty())
1175 auto solved = can_be_solved.front();
1177 can_be_solved.pop();
1182 auto it = adjMatrix.find(solved);
1183 if (it != adjMatrix.end())
1185 for (
auto child : it->second)
1188 if (--indegree[std::get<0>(child)->getId()] == 0)
1192 can_be_solved.emplace(std::get<0>(child));
1200 return !(remain == 0);
1203 template <
typename T>
1206 auto edgeSet = this->getEdgeSet();
1207 for (
auto edge : edgeSet)
1209 if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1219 template <
typename T>
1223 result.success =
false;
1225 auto adj = getAdjMatrix();
1226 auto nodeSet = getNodeSet();
1228 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1231 result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1239 unsigned int V = nodeSet.size();
1240 std::map<const Node<T> *, std::pair<long, const Node<T> *>> dist;
1243 for (
auto node : nodeSet)
1245 dist[&(*node)].first = std::numeric_limits<long>::max();
1250 std::list<const Node<T> *> B[maxWeight * V + 1];
1252 B[0].push_back(&source);
1253 dist[&source].first = 0;
1260 while (B[idx].size() == 0 && idx < maxWeight * V)
1266 if (idx == maxWeight * V)
1272 auto u = B[idx].front();
1277 for (
auto i = adj[u].begin(); i != adj[u].end(); ++i)
1279 auto v = (*i).first;
1281 if ((*i).second->isWeighted().has_value() && (*i).second->isWeighted().value())
1283 if ((*i).second->isDirected().has_value() && (*i).second->isDirected().value())
1286 weight = dw_edge->getWeight();
1288 else if ((*i).second->isDirected().has_value() && !(*i).second->isDirected().value())
1291 weight = udw_edge->getWeight();
1296 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1303 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1306 auto u_i = std::find_if(dist.begin(), dist.end(), [u](std::pair<
const Node<T> *, std::pair<
long,
const Node<T> *>>
const &it)
1307 { return (*u == *(it.first)); });
1309 auto v_i = std::find_if(dist.begin(), dist.end(), [v](std::pair<
const Node<T> *, std::pair<
long,
const Node<T> *>>
const &it)
1310 { return (*v == *(it.first)); });
1311 long du = u_i->second.first;
1312 long dv = v_i->second.first;
1315 if (dv > du + weight)
1320 if (dv != std::numeric_limits<long>::max())
1322 auto findIter = std::find(B[dv].begin(), B[dv].end(), dist[v].second);
1323 B[dv].erase(findIter);
1327 dist[v].first = du + weight;
1331 B[dv].push_front(v);
1334 dist[v].second = *(B[dv].begin());
1338 for (
auto dist_i : dist)
1340 result.minDistanceMap[dist_i.first->getId()] = dist_i.second.first;
1342 result.success =
true;
1347 template <
typename T>
1348 int Graph<T>::writeToFile(InputOutputFormat format,
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
1351 if (format == InputOutputFormat::STANDARD_CSV)
1353 result = writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1355 else if (format == InputOutputFormat::STANDARD_TSV)
1357 result = writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1364 if (result == 0 && compress)
1366 auto compress = [
this, &workingDir, &OFileName, &writeNodeFeat, &writeEdgeWeight](
const std::string &extension)
1368 std::string completePathToFileGraph = workingDir +
"/" + OFileName + extension;
1369 std::string completePathToFileGraphCompressed = workingDir +
"/" + OFileName + extension +
".gz";
1370 int _result = compressFile(completePathToFileGraph, completePathToFileGraphCompressed);
1373 _result = remove(completePathToFileGraph.c_str());
1379 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat" + extension;
1380 std::string completePathToFileNodeFeatCompressed = workingDir +
"/" + OFileName +
"_NodeFeat" + extension +
".gz";
1381 _result = compressFile(completePathToFileNodeFeat, completePathToFileNodeFeatCompressed);
1384 _result = remove(completePathToFileNodeFeat.c_str());
1390 if (writeEdgeWeight)
1392 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight" + extension;
1393 std::string completePathToFileEdgeWeightCompressed = workingDir +
"/" + OFileName +
"_EdgeWeight" + extension +
".gz";
1394 _result = compressFile(completePathToFileEdgeWeight, completePathToFileEdgeWeightCompressed);
1397 _result = remove(completePathToFileEdgeWeight.c_str());
1403 if (format == InputOutputFormat::STANDARD_CSV)
1405 auto result = compress(
".csv");
1407 else if (format == InputOutputFormat::STANDARD_TSV)
1409 auto result = compress(
".tsv");
1420 template <
typename T>
1421 int Graph<T>::readFromFile(InputOutputFormat format,
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
1426 auto decompress = [
this, &workingDir, &OFileName, &readNodeFeat, &readEdgeWeight](
const std::string &extension)
1428 std::string completePathToFileGraph = workingDir +
"/" + OFileName + extension;
1429 std::string completePathToFileGraphCompressed = workingDir +
"/" + OFileName + extension +
".gz";
1430 int _result = decompressFile(completePathToFileGraphCompressed, completePathToFileGraph);
1435 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat" + extension;
1436 std::string completePathToFileNodeFeatCompressed = workingDir +
"/" + OFileName +
"_NodeFeat" + extension +
".gz";
1437 _result = decompressFile(completePathToFileNodeFeatCompressed, completePathToFileNodeFeat);
1444 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight" + extension;
1445 std::string completePathToFileEdgeWeightCompressed = workingDir +
"/" + OFileName +
"_EdgeWeight" + extension +
".gz";
1446 _result = decompressFile(completePathToFileEdgeWeightCompressed, completePathToFileEdgeWeight);
1451 if (format == InputOutputFormat::STANDARD_CSV)
1453 result = decompress(
".csv");
1455 else if (format == InputOutputFormat::STANDARD_TSV)
1457 result = decompress(
".tsv");
1467 if (format == InputOutputFormat::STANDARD_CSV)
1469 result = readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1471 else if (format == InputOutputFormat::STANDARD_TSV)
1473 result = readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1484 template <
typename T>
1487 PartitionMap<T> partitionMap;
1488 for (
unsigned int i = 0; i < numberOfPartitions; ++i)
1492 if (algorithm == PARTITIONING::PartitionAlgorithm::GREEDY_VC_ALG)
1494 greedyPartition(partitionMap);
1496 else if (algorithm == PARTITIONING::PartitionAlgorithm::HDRF_ALG)
1498 HDRFPartition(partitionMap);
1503 partitionMap.clear();
1505 return partitionMap;
1509 template <
typename T>
1510 std::ostream &operator<<(std::ostream &os,
const AdjacencyMatrix<T> &adj)
1512 os <<
"Adjacency Matrix:\n";
1513 auto it = adj.begin();
1514 unsigned long max_column = 0;
1515 for (it; it != adj.end(); ++it)
1517 if (it->second.size() > max_column)
1519 max_column = it->second.size();
1522 if (max_column == 0)
1524 os <<
"ERROR in Print\n";
1531 for (
int i = 0; i < max_column; i++)
1536 for (it; it != adj.end(); ++it)
1538 os <<
"|N" << it->first->getId() <<
"|";
1539 auto it2 = it->second.begin();
1540 for (it2; it2 != it->second.end(); ++it2)
1542 os <<
"N" << it2->first->getId() <<
",E" << it2->second->getId() <<
"|";
1545 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:76
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:1013
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:307
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:368
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:1135
virtual void removeEdge(unsigned long edgeId)
Function remove an Edge from the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:337
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:1348
virtual bool isDirectedGraph() const
This function checks if a graph is directed Note: No Thread Safe.
Definition: Graph.hpp:1204
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:1220
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:863
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:1045
virtual void addEdge(const Edge< T > *edge)
Function add an Edge to the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:327
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:1485
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:1421
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:836
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:348
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:973
virtual void setEdgeSet(std::list< const Edge< T > * > &edgeSet)
Function set the Edge Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:313
Definition: Partition.hpp:38
Definition: UndirectedEdge.hpp:39
Definition: UndirectedWeightedEdge.hpp:43
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:62