23 constexpr
char ERR_NO_DIR_OR_UNDIR_EDGE[] =
"Edge are neither Directed neither Undirected";
24 constexpr
char ERR_NO_WEIGHTED_EDGE[] =
"Edge are not Weighted";
25 constexpr
char ERR_TARGET_NODE_NOT_REACHABLE[] =
"Target Node not Reachable";
26 constexpr
char ERR_TARGET_NODE_NOT_IN_GRAPH[] =
"Target Node not inside Graph";
27 constexpr
char ERR_SOURCE_NODE_NOT_IN_GRAPH[] =
"Source Node not inside Graph";
29 constexpr
double INF_DOUBLE = std::numeric_limits<double>::max();
39 class DirectedWeightedEdge;
41 class UndirectedWeightedEdge;
60 std::string errorMessage;
69 std::string errorMessage;
70 std::map<unsigned long, long> minDistanceMap;
77 unsigned int numberOfPartitions;
78 unsigned int numberOfNodes;
79 unsigned int replicatedNodesCount;
80 unsigned int numberOfEdges;
81 unsigned int replicatedEdgesCount;
82 unsigned int maxEdgesLoad;
83 unsigned int minEdgesLoad;
84 unsigned int maxNodesLoad;
85 unsigned int minNodesLoad;
86 double balanceEdgesFactor;
87 double balanceNodesFactor;
88 double nodesReplicationFactor;
89 double edgesReplicationFactor;
93 os <<
"Partitioning Stats:\n";
94 os <<
"\tNumber of Partitions: " << partitionStats.numberOfPartitions <<
"\n";
95 os <<
"\tNumber of Nodes: " << partitionStats.numberOfNodes <<
"\n";
96 os <<
"\tNumber of Edges: " << partitionStats.numberOfEdges <<
"\n";
97 os <<
"\tNumber of Nodes Replica: " << partitionStats.replicatedNodesCount <<
"\n";
98 os <<
"\tNumber of Edges Replica: " << partitionStats.replicatedEdgesCount <<
"\n";
99 os <<
"\tNodes Replication Factor: " << partitionStats.nodesReplicationFactor <<
"\n";
100 os <<
"\tEdges Replication Factor: " << partitionStats.edgesReplicationFactor <<
"\n";
101 os <<
"\tMax Edges Load: " << partitionStats.maxEdgesLoad <<
"\n";
102 os <<
"\tMin Edges Load: " << partitionStats.minEdgesLoad <<
"\n";
103 os <<
"\tBalance Edges Factor: " << partitionStats.balanceEdgesFactor <<
"\n";
104 os <<
"\tMax Nodes Load: " << partitionStats.maxNodesLoad <<
"\n";
105 os <<
"\tMin Nodes Load: " << partitionStats.minNodesLoad <<
"\n";
106 os <<
"\tBalance Nodes Factor: " << partitionStats.balanceNodesFactor <<
"\n";
112 template <
typename T>
113 using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *,
const Edge<T> *>>>;
115 template <
typename T>
116 std::ostream &operator<<(std::ostream &o,
const Node<T> &node);
117 template <
typename T>
118 std::ostream &operator<<(std::ostream &o,
const Edge<T> &edge);
119 template <
typename T>
120 std::ostream &operator<<(std::ostream &o,
const DirectedEdge<T> &edge);
121 template <
typename T>
123 template <
typename T>
125 template <
typename T>
127 template <
typename T>
128 std::ostream &operator<<(std::ostream &o,
const Graph<T> &graph);
129 template <
typename T>
130 std::ostream &operator<<(std::ostream &o,
const AdjacencyMatrix<T> &adj);
131 template <
typename T>
132 using PartitionMap = std::map<unsigned int, Partition<T> *>;
134 template <
typename T>
142 Node(
const unsigned long id,
const T &data);
144 const unsigned long &getId()
const;
145 const T &getData()
const;
147 bool operator==(
const Node<T> &b)
const;
148 bool operator<(
const Node<T> &b)
const;
149 friend std::ostream &operator<<<>(std::ostream &os,
const Node<T> &node);
152 template <
typename T>
159 template <
typename T>
160 const unsigned long &Node<T>::getId()
const
165 template <
typename T>
166 const T &Node<T>::getData()
const
171 template <
typename T>
172 bool Node<T>::operator==(
const Node<T> &b)
const
174 return (this->
id == b.id && this->data == b.data);
177 template <
typename T>
178 bool Node<T>::operator<(
const Node<T> &b)
const
180 return (this->
id < b.id);
192 double getWeight()
const;
193 void setWeight(
const double weight);
197 inline Weighted::Weighted()
203 inline Weighted::Weighted(
const double weight)
205 this->weight = weight;
209 inline double Weighted::getWeight()
const
215 inline void Weighted::setWeight(
const double weight)
217 this->weight = weight;
223 void getLock()
const;
224 void releaseLock()
const;
227 mutable std::mutex mutex;
230 inline void ThreadSafe::getLock()
const
235 inline void ThreadSafe::releaseLock()
const
240 template <
typename T>
245 std::pair<const Node<T> *,
const Node<T> *> nodePair;
249 Edge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair);
250 virtual ~
Edge() =
default;
251 const unsigned long &getId()
const;
252 const std::pair<const Node<T> *,
const Node<T> *> &getNodePair()
const;
253 virtual const std::optional<bool> isDirected()
const;
254 virtual const std::optional<bool> isWeighted()
const;
256 virtual bool operator==(
const Edge<T> &b)
const;
257 bool operator<(
const Edge<T> &b)
const;
261 friend std::ostream &operator<<<>(std::ostream &os,
const Edge<T> &edge);
264 template <
typename T>
270 template <
typename T>
271 Edge<T>::Edge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : nodePair(nodepair)
276 template <
typename T>
277 const unsigned long &Edge<T>::getId()
const
282 template <
typename T>
283 const std::pair<const Node<T> *,
const Node<T> *> &Edge<T>::getNodePair()
const
288 template <
typename T>
289 const std::optional<bool> Edge<T>::isDirected()
const
294 template <
typename T>
295 const std::optional<bool> Edge<T>::isWeighted()
const
300 template <
typename T>
301 bool Edge<T>::operator==(
const Edge<T> &b)
const
303 return (this->
id == b.id && this->nodePair == b.nodePair);
306 template <
typename T>
307 bool Edge<T>::operator<(
const Edge<T> &b)
const
309 return (this->
id < b.id);
312 template <
typename T>
320 const Node<T> &getFrom()
const;
322 const std::optional<bool> isDirected()
const override;
323 const std::optional<bool> isWeighted()
const override;
327 friend std::ostream &operator<<<>(std::ostream &os,
const DirectedEdge<T> &edge);
330 template <
typename T>
335 template <
typename T>
336 DirectedEdge<T>::DirectedEdge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
340 template <
typename T>
341 DirectedEdge<T>::DirectedEdge(
const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
345 template <
typename T>
346 const Node<T> &DirectedEdge<T>::getFrom()
const
348 return *(Edge<T>::getNodePair().first);
351 template <
typename T>
352 const Node<T> &DirectedEdge<T>::getTo()
const
354 return *(Edge<T>::getNodePair().second);
357 template <
typename T>
358 const std::optional<bool> DirectedEdge<T>::isDirected()
const
363 template <
typename T>
364 const std::optional<bool> DirectedEdge<T>::isWeighted()
const
369 template <
typename T>
377 const Node<T> &getNode1()
const;
378 const Node<T> &getNode2()
const;
379 const std::optional<bool> isDirected()
const override;
380 const std::optional<bool> isWeighted()
const override;
384 friend std::ostream &operator<<<>(std::ostream &os,
const UndirectedEdge<T> &edge);
387 template <
typename T>
392 template <
typename T>
393 UndirectedEdge<T>::UndirectedEdge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
397 template <
typename T>
398 UndirectedEdge<T>::UndirectedEdge(
const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
402 template <
typename T>
403 const Node<T> &UndirectedEdge<T>::getNode1()
const
405 return *(Edge<T>::getNodePair().first);
408 template <
typename T>
409 const Node<T> &UndirectedEdge<T>::getNode2()
const
411 return *(Edge<T>::getNodePair().second);
414 template <
typename T>
415 const std::optional<bool> UndirectedEdge<T>::isDirected()
const
420 template <
typename T>
421 const std::optional<bool> UndirectedEdge<T>::isWeighted()
const
426 template <
typename T>
438 const std::optional<bool> isWeighted()
const override;
445 template <
typename T>
450 template <
typename T>
451 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)
455 template <
typename T>
456 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
460 template <
typename T>
461 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
465 template <
typename T>
466 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
470 template <
typename T>
471 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
475 template <
typename T>
476 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
480 template <
typename T>
481 const std::optional<bool> DirectedWeightedEdge<T>::isWeighted()
const
486 template <
typename T>
498 const std::optional<bool> isWeighted()
const override;
505 template <
typename T>
510 template <
typename T>
511 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)
515 template <
typename T>
516 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
520 template <
typename T>
521 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
525 template <
typename T>
526 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
530 template <
typename T>
531 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
535 template <
typename T>
536 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
540 template <
typename T>
541 const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted()
const
546 template <
typename T>
550 template <
typename T>
554 std::list<const Edge<T> *> edgeSet;
555 void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix,
const Node<T> *nodeFrom,
const Node<T> *nodeTo,
const Edge<T> *edge)
const;
556 int writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
557 int readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
558 int writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
559 int readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
560 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);
561 void greedyPartition(PartitionMap<T> &partitionMap)
const;
595 virtual const std::list<const Edge<T> *> &
getEdgeSet()
const;
622 virtual void removeEdge(
unsigned long edgeId);
631 virtual const std::list<const Node<T> *>
getNodeSet()
const;
641 virtual const std::optional<const Edge<T> *>
getEdge(
unsigned long edgeId)
const;
741 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;
756 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);
767 virtual PartitionMap<T>
partitionGraph(PartitionAlgorithm algorithm,
unsigned int numberOfPartitions)
const;
769 friend std::ostream &operator<<<>(std::ostream &os,
const Graph<T> &graph);
770 friend std::ostream &operator<<<>(std::ostream &os,
const AdjacencyMatrix<T> &adj);
773 template <
typename T>
774 Graph<T>::Graph(
const std::list<
const Edge<T> *> &edgeSet)
776 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
778 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
779 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
781 this->edgeSet.push_back(*edgeSetIt);
786 template <
typename T>
792 template <
typename T>
795 this->edgeSet.clear();
796 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
798 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
799 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
801 this->edgeSet.push_back(*edgeSetIt);
806 template <
typename T>
809 if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](
const Edge<T> *edge_a)
810 { return (*edge == *edge_a); }) == edgeSet.end())
812 edgeSet.push_back(edge);
816 template <
typename T>
819 auto edgeOpt = getEdge(edgeId);
820 if (edgeOpt.has_value())
822 edgeSet.erase(std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeOpt](
const Edge<T> *edge)
823 { return (*(edgeOpt.value()) == *edge); }));
827 template <
typename T>
830 std::list<const Node<T> *> nodeSet;
831 for (
auto edge : edgeSet)
833 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
834 { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
836 nodeSet.push_back(edge->getNodePair().first);
838 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
839 { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
841 nodeSet.push_back(edge->getNodePair().second);
847 template <
typename T>
851 auto it = edgeSet.begin();
852 for (it; it != edgeSet.end(); ++it)
854 if ((*it)->getId() == edgeId)
863 template <
typename T>
866 std::pair<const Node<T> *,
const Edge<T> *> elem = {nodeTo, edge};
867 adjMatrix[nodeFrom].push_back(elem);
872 template <
typename T>
873 int Graph<T>::writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
875 std::ofstream ofileGraph;
876 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
877 ofileGraph.open(completePathToFileGraph);
878 if (!ofileGraph.is_open())
883 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
884 { ofileGraph << e->getId() <<
"," << e->getNodePair().first->getId() <<
"," << e->getNodePair().second->getId() <<
"," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
885 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
890 std::ofstream ofileNodeFeat;
891 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
893 ofileNodeFeat.open(completePathToFileNodeFeat);
894 if (!ofileNodeFeat.is_open())
899 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
900 { ofileNodeFeat << node->getId() <<
"," << node->getData() << std::endl; };
901 auto nodeSet = getNodeSet();
902 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
903 ofileNodeFeat.close();
908 std::ofstream ofileEdgeWeight;
909 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
911 ofileEdgeWeight.open(completePathToFileEdgeWeight);
912 if (!ofileEdgeWeight.is_open())
917 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
918 { 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; };
920 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
921 ofileEdgeWeight.close();
926 template <
typename T>
927 int Graph<T>::readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
929 std::ifstream ifileGraph;
930 std::ifstream ifileNodeFeat;
931 std::ifstream ifileEdgeWeight;
932 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
933 std::map<unsigned long, bool> edgeDirectedMap;
934 std::map<unsigned long, T> nodeFeatMap;
935 std::map<unsigned long, double> edgeWeightMap;
936 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
937 ifileGraph.open(completePathToFileGraph);
938 if (!ifileGraph.is_open())
946 unsigned long edgeId;
947 unsigned long nodeId1;
948 unsigned long nodeId2;
950 ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
951 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
952 edgeDirectedMap[edgeId] = directed;
953 if (ifileGraph.fail() || ifileGraph.eof())
955 ifileGraph.ignore(128,
'\n');
961 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
963 ifileNodeFeat.open(completePathToFileNodeFeat);
964 if (!ifileNodeFeat.is_open())
971 unsigned long nodeId;
973 ifileNodeFeat >> nodeId >> comma >> nodeFeat;
974 nodeFeatMap[nodeId] = nodeFeat;
975 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
977 ifileNodeFeat.ignore(128,
'\n');
979 ifileNodeFeat.close();
984 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
986 ifileEdgeWeight.open(completePathToFileEdgeWeight);
987 if (!ifileEdgeWeight.is_open())
994 unsigned long edgeId;
997 ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
1000 edgeWeightMap[edgeId] = weight;
1002 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
1004 ifileEdgeWeight.ignore(128,
'\n');
1006 ifileEdgeWeight.close();
1008 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
1012 template <
typename T>
1013 int Graph<T>::writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
1015 std::ofstream ofileGraph;
1016 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
1017 ofileGraph.open(completePathToFileGraph);
1018 if (!ofileGraph.is_open())
1023 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
1024 { 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; };
1025 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
1030 std::ofstream ofileNodeFeat;
1031 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
1033 ofileNodeFeat.open(completePathToFileNodeFeat);
1034 if (!ofileNodeFeat.is_open())
1039 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
1040 { ofileNodeFeat << node->getId() <<
"\t" << node->getData() << std::endl; };
1041 auto nodeSet = getNodeSet();
1042 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
1043 ofileNodeFeat.close();
1046 if (writeEdgeWeight)
1048 std::ofstream ofileEdgeWeight;
1049 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
1051 ofileEdgeWeight.open(completePathToFileEdgeWeight);
1052 if (!ofileEdgeWeight.is_open())
1057 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
1058 { 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; };
1060 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
1061 ofileEdgeWeight.close();
1066 template <
typename T>
1067 int Graph<T>::readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
1069 std::ifstream ifileGraph;
1070 std::ifstream ifileNodeFeat;
1071 std::ifstream ifileEdgeWeight;
1072 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
1073 std::map<unsigned long, bool> edgeDirectedMap;
1074 std::map<unsigned long, T> nodeFeatMap;
1075 std::map<unsigned long, double> edgeWeightMap;
1076 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
1077 ifileGraph.open(completePathToFileGraph);
1078 if (!ifileGraph.is_open())
1085 unsigned long edgeId;
1086 unsigned long nodeId1;
1087 unsigned long nodeId2;
1089 ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
1090 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
1091 edgeDirectedMap[edgeId] = directed;
1092 if (ifileGraph.fail() || ifileGraph.eof())
1094 ifileGraph.ignore(128,
'\n');
1100 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
1102 ifileNodeFeat.open(completePathToFileNodeFeat);
1103 if (!ifileNodeFeat.is_open())
1110 unsigned long nodeId;
1112 ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
1113 nodeFeatMap[nodeId] = nodeFeat;
1114 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
1116 ifileNodeFeat.ignore(128,
'\n');
1118 ifileNodeFeat.close();
1123 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
1125 ifileEdgeWeight.open(completePathToFileEdgeWeight);
1126 if (!ifileEdgeWeight.is_open())
1133 unsigned long edgeId;
1136 ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
1139 edgeWeightMap[edgeId] = weight;
1141 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
1143 ifileEdgeWeight.ignore(128,
'\n');
1145 ifileEdgeWeight.close();
1147 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
1151 template <
typename T>
1152 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)
1154 std::map<unsigned long, Node<T> *> nodeMap;
1155 for (
auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
1157 Node<T> *node1 =
nullptr;
1158 Node<T> *node2 =
nullptr;
1159 if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
1163 if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
1165 feat = nodeFeatMap.at(edgeIt->second.first);
1167 node1 =
new Node<T>(edgeIt->second.first, feat);
1168 nodeMap[edgeIt->second.first] = node1;
1172 node1 = nodeMap.at(edgeIt->second.first);
1174 if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
1178 if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
1180 feat = nodeFeatMap.at(edgeIt->second.second);
1182 node2 =
new Node<T>(edgeIt->second.second, feat);
1183 nodeMap[edgeIt->second.second] = node2;
1187 node2 = nodeMap.at(edgeIt->second.second);
1190 if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
1192 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1194 auto edge =
new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1199 auto edge =
new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1205 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1207 auto edge =
new DirectedEdge<T>(edgeIt->first, *node1, *node2);
1212 auto edge =
new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
1219 template <
typename T>
1220 void Graph<T>::greedyPartition(PartitionMap<T> &partitionMap)
const
1222 unsigned int index = 0;
1223 unsigned int numberOfPartitions = partitionMap.size();
1224 if (index == numberOfPartitions)
1229 auto edgeSet = getEdgeSet();
1230 for (
auto edge : edgeSet)
1232 partitionMap.at(index)->addEdge(edge);
1234 index = index % numberOfPartitions;
1238 template <
typename T>
1241 AdjacencyMatrix<T> adj;
1242 auto edgeSetIt = edgeSet.begin();
1243 for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
1245 if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
1248 addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
1250 else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
1254 addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
1255 addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
1265 template <
typename T>
1269 result.success =
false;
1270 result.errorMessage =
"";
1271 result.result = INF_DOUBLE;
1272 auto nodeSet = getNodeSet();
1273 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1276 result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1279 if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1282 result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
1285 const AdjacencyMatrix<T> adj = getAdjMatrix();
1290 std::map<const Node<T> *,
double> dist;
1292 for (
auto elem : adj)
1294 dist[elem.first] = INF_DOUBLE;
1300 std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1301 std::greater<std::pair<double, const Node<T> *>>>
1305 pq.push(std::make_pair(0.0, &source));
1313 const Node<T> *currentNode = pq.top().second;
1316 double currentDist = pq.top().first;
1322 if (adj.find(currentNode) != adj.end())
1324 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
1327 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1329 if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1332 if (currentDist + dw_edge->getWeight() < dist[elem.first])
1334 dist[elem.first] = currentDist + dw_edge->getWeight();
1335 pq.push(std::make_pair(dist[elem.first], elem.first));
1338 else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1341 if (currentDist + udw_edge->getWeight() < dist[elem.first])
1343 dist[elem.first] = currentDist + udw_edge->getWeight();
1344 pq.push(std::make_pair(dist[elem.first], elem.first));
1350 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1357 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1363 if (dist[&target] != INF_DOUBLE)
1365 result.success =
true;
1366 result.errorMessage =
"";
1367 result.result = dist[&target];
1370 result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
1375 template <
typename T>
1379 std::vector<Node<T>> visited;
1380 auto nodeSet = getNodeSet();
1382 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1386 const AdjacencyMatrix<T> adj = getAdjMatrix();
1388 std::queue<const Node<T> *> tracker;
1391 visited.push_back(start);
1392 tracker.push(&start);
1393 while (!tracker.empty())
1395 const Node<T> *node = tracker.front();
1397 if (adj.find(node) != adj.end())
1399 for (
auto elem : adj.at(node))
1403 if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1405 visited.push_back(*(elem.first));
1406 tracker.push(elem.first);
1415 template <
typename T>
1419 std::vector<Node<T>> visited;
1420 auto nodeSet = getNodeSet();
1422 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1426 const AdjacencyMatrix<T> adj = getAdjMatrix();
1427 std::function<void(
const AdjacencyMatrix<T> &,
const Node<T> &, std::vector<
Node<T>> &)> explore;
1428 explore = [&explore](
const AdjacencyMatrix<T> &adj,
const Node<T> &node, std::vector<Node<T>> &visited) ->
void
1430 visited.push_back(node);
1431 if (adj.find(&node) != adj.end())
1433 for (
auto x : adj.at(&node))
1435 if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1437 explore(adj, *(x.first), visited);
1442 explore(adj, start, visited);
1447 template <
typename T>
1450 if (!isDirectedGraph())
1454 enum nodeStates : uint8_t
1460 auto nodeSet = this->getNodeSet();
1461 auto adjMatrix = this->getAdjMatrix();
1470 std::map<unsigned long, nodeStates> state;
1471 for (
auto node : nodeSet)
1473 state[node->getId()] = not_visited;
1475 int stateCounter = 0;
1478 for (
auto node : nodeSet)
1483 if (state[node->getId()] == not_visited)
1486 std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &,
const Node<T> *)> isCyclicDFSHelper;
1487 isCyclicDFSHelper = [
this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states,
const Node<T> *node)
1490 states[node->getId()] = in_stack;
1494 auto const it = adjMatrix.find(node);
1495 if (it != adjMatrix.end())
1497 for (
auto child : it->second)
1501 auto state_of_child = states.at((std::get<0>(child))->getId());
1502 if (state_of_child == not_visited)
1504 if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1509 else if (state_of_child == in_stack)
1521 states[node->getId()] = visited;
1525 if (isCyclicDFSHelper(adjMatrix, state, node))
1537 template <
typename T>
1540 if (!isDirectedGraph())
1544 auto adjMatrix = this->getAdjMatrix();
1545 auto nodeSet = this->getNodeSet();
1547 std::map<unsigned long, unsigned int> indegree;
1548 for (
auto node : nodeSet)
1550 indegree[node->getId()] = 0;
1553 for (
auto const &list : adjMatrix)
1555 auto children = list.second;
1556 for (
auto const &child : children)
1558 indegree[std::get<0>(child)->getId()]++;
1562 std::queue<const Node<T> *> can_be_solved;
1563 for (
auto node : nodeSet)
1567 if (!indegree[node->getId()])
1569 can_be_solved.emplace(&(*node));
1574 auto remain = this->getNodeSet().size();
1576 while (!can_be_solved.empty())
1578 auto solved = can_be_solved.front();
1580 can_be_solved.pop();
1585 auto it = adjMatrix.find(solved);
1586 if (it != adjMatrix.end())
1588 for (
auto child : it->second)
1591 if (--indegree[std::get<0>(child)->getId()] == 0)
1595 can_be_solved.emplace(std::get<0>(child));
1603 return !(remain == 0);
1606 template <
typename T>
1609 auto edgeSet = this->getEdgeSet();
1610 for (
auto edge : edgeSet)
1612 if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1622 template <
typename T>
1626 result.success =
false;
1628 auto adj = getAdjMatrix();
1629 auto nodeSet = getNodeSet();
1631 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1634 result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1642 unsigned int V = nodeSet.size();
1643 std::map<const Node<T> *, std::pair<long, const Node<T> *>> dist;
1646 for (
auto node : nodeSet)
1648 dist[&(*node)].first = std::numeric_limits<long>::max();
1653 std::list<const Node<T> *> B[maxWeight * V + 1];
1655 B[0].push_back(&source);
1656 dist[&source].first = 0;
1663 while (B[idx].size() == 0 && idx < maxWeight * V)
1669 if (idx == maxWeight * V)
1675 auto u = B[idx].front();
1680 for (
auto i = adj[u].begin(); i != adj[u].end(); ++i)
1682 auto v = (*i).first;
1684 if ((*i).second->isWeighted().has_value() && (*i).second->isWeighted().value())
1686 if ((*i).second->isDirected().has_value() && (*i).second->isDirected().value())
1689 weight = dw_edge->getWeight();
1691 else if ((*i).second->isDirected().has_value() && !(*i).second->isDirected().value())
1694 weight = udw_edge->getWeight();
1699 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1706 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1709 auto u_i = std::find_if(dist.begin(), dist.end(), [u](std::pair<
const Node<T> *, std::pair<
long,
const Node<T> *>>
const &it)
1710 { return (*u == *(it.first)); });
1712 auto v_i = std::find_if(dist.begin(), dist.end(), [v](std::pair<
const Node<T> *, std::pair<
long,
const Node<T> *>>
const &it)
1713 { return (*v == *(it.first)); });
1714 long du = u_i->second.first;
1715 long dv = v_i->second.first;
1718 if (dv > du + weight)
1723 if (dv != std::numeric_limits<long>::max())
1725 auto findIter = std::find(B[dv].begin(), B[dv].end(), dist[v].second);
1726 B[dv].erase(findIter);
1730 dist[v].first = du + weight;
1734 B[dv].push_front(v);
1737 dist[v].second = *(B[dv].begin());
1741 for (
auto dist_i : dist)
1743 result.minDistanceMap[dist_i.first->getId()] = dist_i.second.first;
1745 result.success =
true;
1750 template <
typename T>
1751 int Graph<T>::writeToFile(InputOutputFormat format,
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
1753 if (format == InputOutputFormat::STANDARD_CSV)
1755 return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1757 else if (format == InputOutputFormat::STANDARD_TSV)
1759 return writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1768 template <
typename T>
1771 if (format == InputOutputFormat::STANDARD_CSV)
1773 return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1775 else if (format == InputOutputFormat::STANDARD_TSV)
1777 return readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1786 template <
typename T>
1789 PartitionMap<T> partitionMap;
1790 for (
unsigned int i = 0; i < numberOfPartitions; ++i)
1794 if (algorithm == PartitionAlgorithm::GREEDY_VC)
1796 greedyPartition(partitionMap);
1801 partitionMap.clear();
1803 return partitionMap;
1807 template <
typename T>
1823 const std::list<const Edge<T> *> &
getEdgeSet()
const override;
1850 void removeEdge(
unsigned long edgeId)
override;
1859 const std::list<const Node<T> *>
getNodeSet()
const override;
1869 const std::optional<const Edge<T> *>
getEdge(
unsigned long edgeId)
const override;
1875 const AdjacencyMatrix<T>
getAdjMatrix()
const override;
1998 template <
typename T>
2001 template <
typename T>
2002 Graph_TS<T>::Graph_TS(
const Graph<T> &graph) : Graph<T>(graph), ThreadSafe() {}
2004 template <
typename T>
2007 std::lock_guard<std::mutex> lock(mutex);
2011 template <
typename T>
2019 template <
typename T>
2027 template <
typename T>
2035 template <
typename T>
2044 template <
typename T>
2053 template <
typename T>
2062 template <
typename T>
2071 template <
typename T>
2080 template <
typename T>
2089 template <
typename T>
2098 template <
typename T>
2107 template <
typename T>
2116 template <
typename T>
2125 template <
typename T>
2129 auto result =
Graph<T>::writeToFile(format, workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
2134 template <
typename T>
2138 auto result =
Graph<T>::readFromFile(format, workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
2143 template <
typename T>
2152 template <
typename T>
2159 Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet);
2175 unsigned int partitionId;
2185 template <
typename T>
2186 static PartitioningStats getPartitionStats(
const PartitionMap<T> &partitionMap);
2195 template <
typename T>
2196 static unsigned int getMaxEdgesLoad(
const PartitionMap<T> &partitionMap);
2205 template <
typename T>
2206 static unsigned int getMinEdgesLoad(
const PartitionMap<T> &partitionMap);
2215 template <
typename T>
2216 static unsigned int getMaxNodesLoad(
const PartitionMap<T> &partitionMap);
2225 template <
typename T>
2226 static unsigned int getMinNodesLoad(
const PartitionMap<T> &partitionMap);
2235 template <
typename T>
2236 static unsigned int getNumberOfEdges(
const PartitionMap<T> &partitionMap);
2245 template <
typename T>
2246 static unsigned int getNumberOfNodes(
const PartitionMap<T> &partitionMap);
2255 template <
typename T>
2256 static unsigned int getNumberOfReplicatedEdges(
const PartitionMap<T> &partitionMap);
2265 template <
typename T>
2266 static unsigned int getNumberOfReplicatedNodes(
const PartitionMap<T> &partitionMap);
2268 template <
typename T>
2274 template <
typename T>
2275 Partition<T>::Partition(
unsigned int partitionId) : Graph<T>()
2277 this->partitionId = partitionId;
2280 template <
typename T>
2281 Partition<T>::Partition(
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
2286 template <
typename T>
2287 Partition<T>::Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
2289 this->partitionId = partitionId;
2292 template <
typename T>
2298 template <
typename T>
2301 this->partitionId = partitionId;
2304 template <
typename T>
2308 result.numberOfPartitions = partitionMap.size();
2309 result.numberOfNodes = getNumberOfNodes(partitionMap);
2310 result.numberOfEdges = getNumberOfEdges(partitionMap);
2311 result.replicatedNodesCount = getNumberOfReplicatedNodes(partitionMap);
2312 result.replicatedEdgesCount = getNumberOfReplicatedEdges(partitionMap);
2313 result.maxEdgesLoad = getMaxEdgesLoad(partitionMap);
2314 result.minEdgesLoad = getMinEdgesLoad(partitionMap);
2315 result.maxNodesLoad = getMaxNodesLoad(partitionMap);
2316 result.minNodesLoad = getMinNodesLoad(partitionMap);
2317 result.edgesReplicationFactor = (double)result.replicatedEdgesCount / result.numberOfEdges;
2318 result.nodesReplicationFactor = (
double)result.replicatedNodesCount / result.numberOfNodes;
2319 result.balanceEdgesFactor = (double)(result.maxEdgesLoad - result.minEdgesLoad) / (result.maxEdgesLoad);
2320 result.balanceNodesFactor = (double)(result.maxNodesLoad - result.minNodesLoad) / (result.maxNodesLoad);
2324 template <
typename T>
2325 unsigned int getMaxEdgesLoad(
const PartitionMap<T> &partitionMap)
2327 unsigned int maxLoad = 0;
2328 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2330 if (it->second->getEdgeSet().size() > maxLoad)
2332 maxLoad = it->second->getEdgeSet().size();
2338 template <
typename T>
2339 unsigned int getMinEdgesLoad(
const PartitionMap<T> &partitionMap)
2341 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
2342 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2344 if (it->second->getEdgeSet().size() < minLoad)
2346 minLoad = it->second->getEdgeSet().size();
2352 template <
typename T>
2353 unsigned int getMaxNodesLoad(
const PartitionMap<T> &partitionMap)
2355 unsigned int maxLoad = 0;
2356 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2358 if (it->second->getNodeSet().size() > maxLoad)
2360 maxLoad = it->second->getNodeSet().size();
2366 template <
typename T>
2367 unsigned int getMinNodesLoad(
const PartitionMap<T> &partitionMap)
2369 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
2370 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2372 if (it->second->getNodeSet().size() < minLoad)
2374 minLoad = it->second->getNodeSet().size();
2380 template <
typename T>
2381 unsigned int getNumberOfEdges(
const PartitionMap<T> &partitionMap)
2383 unsigned int numberOfEdges = 0;
2384 std::list<const Edge<T> *> edgeSet;
2386 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2388 const std::list<const Edge<T> *> partitionEdgeSet = it->second->getEdgeSet();
2389 for (
auto it2 = partitionEdgeSet.begin(); it2 != partitionEdgeSet.end(); ++it2)
2391 if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](
const Edge<T> *edge)
2392 { return (*(*it2) == *edge); }) == edgeSet.end())
2394 edgeSet.push_back(*it2);
2399 return edgeSet.size();
2402 template <
typename T>
2403 unsigned int getNumberOfNodes(
const PartitionMap<T> &partitionMap)
2405 unsigned int numberOfNodes = 0;
2406 std::list<const Node<T> *> nodeSet;
2408 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2410 const std::list<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
2411 for (
auto it2 = partitionNodeSet.begin(); it2 != partitionNodeSet.end(); ++it2)
2413 if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](
const Node<T> *node)
2414 { return (*(*it2) == *node); }) == nodeSet.end())
2416 nodeSet.push_back(*it2);
2421 return nodeSet.size();
2424 template <
typename T>
2425 unsigned int getNumberOfReplicatedEdges(
const PartitionMap<T> &partitionMap)
2428 unsigned int numberOfEdges = 0;
2429 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2431 numberOfEdges += it->second->getEdgeSet().size();
2433 return numberOfEdges;
2436 template <
typename T>
2437 unsigned int getNumberOfReplicatedNodes(
const PartitionMap<T> &partitionMap)
2439 unsigned int numberOfNodes = 0;
2440 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
2442 numberOfNodes += it->second->getNodeSet().size();
2444 return numberOfNodes;
2451 template <
typename T>
2470 template <
typename T>
2482 virtual int ReadGraph(
Graph<T> &graph, std::ifstream &file) = 0;
2486 template <
typename T>
2488 operator<<(std::ostream &os,
const Node<T> &node)
2491 <<
" Id:\t" << node.id <<
"\n Data:\t" << node.data <<
"\n}";
2495 template <
typename T>
2496 std::ostream &operator<<(std::ostream &os,
const Edge<T> &edge)
2498 os <<
"((Node: " << edge.nodePair.first->getId() <<
")) ?----- |Edge: " << edge.id <<
"|-----? ((Node: " << edge.nodePair.second->getId() <<
"))";
2502 template <
typename T>
2503 std::ostream &operator<<(std::ostream &os,
const DirectedEdge<T> &edge)
2505 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
2509 template <
typename T>
2510 std::ostream &operator<<(std::ostream &os,
const UndirectedEdge<T> &edge)
2512 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
2516 template <
typename T>
2517 std::ostream &operator<<(std::ostream &os,
const DirectedWeightedEdge<T> &edge)
2519 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
2523 template <
typename T>
2524 std::ostream &operator<<(std::ostream &os,
const UndirectedWeightedEdge<T> &edge)
2526 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
2530 template <
typename T>
2531 std::ostream &operator<<(std::ostream &os,
const AdjacencyMatrix<T> &adj)
2533 os <<
"Adjacency Matrix:\n";
2534 auto it = adj.begin();
2535 unsigned long max_column = 0;
2536 for (it; it != adj.end(); ++it)
2538 if (it->second.size() > max_column)
2540 max_column = it->second.size();
2543 if (max_column == 0)
2545 os <<
"ERROR in Print\n";
2552 for (
int i = 0; i < max_column; i++)
2557 for (it; it != adj.end(); ++it)
2559 os <<
"|N" << it->first->getId() <<
"|";
2560 auto it2 = it->second.begin();
2561 for (it2; it2 != it->second.end(); ++it2)
2563 os <<
"N" << it2->first->getId() <<
",E" << it2->second->getId() <<
"|";
2566 for (
int i = 0; i < max_column; i++)
Definition: Graph.hpp:314
Definition: Graph.hpp:428
Definition: Graph.hpp:242
Class that implement the Thread Safe Graph.
Definition: Graph.hpp:1809
const std::optional< const Edge< T > * > getEdge(unsigned long edgeId) const override
Function that return an Edge with specific ID if Exist in the Graph Note: Thread Safe.
Definition: Graph.hpp:2045
const std::list< const Node< T > * > getNodeSet() const override
Function that return the Node Set of the Graph Note: Thread Safe.
Definition: Graph.hpp:2036
void setEdgeSet(std::list< const Edge< T > * > &edgeSet) override
Function set the Edge Set of the Graph Note: Thread Safe.
Definition: Graph.hpp:2012
bool isDirectedGraph() const override
This function checks if a graph is directed Note: Thread Safe.
Definition: Graph.hpp:2108
const DijkstraResult dijkstra(const Node< T > &source, const Node< T > &target) const override
Function runs the dijkstra algorithm for some source node and target node in the graph and returns th...
Definition: Graph.hpp:2063
void addEdge(const Edge< T > *edge) override
Function add an Edge to the Graph Edge Set Note: Thread Safe.
Definition: Graph.hpp:2020
PartitionMap< T > partitionGraph(typename Graph< T >::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const override
This function partition a graph in a set of partitions Note: Thread Safe.
Definition: Graph.hpp:2144
bool isCyclicDirectedGraphBFS() const override
This function uses BFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:2099
const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const override
Function performs the breadth first search algorithm over the graph Note: Thread Safe.
Definition: Graph.hpp:2072
void removeEdge(unsigned long edgeId) override
Function remove an Edge from the Graph Edge Set Note: Thread Safe.
Definition: Graph.hpp:2028
const std::list< const Edge< T > * > & getEdgeSet() const override
Function that return the Edge set of the Graph Note: Thread Safe.
Definition: Graph.hpp:2005
const std::vector< Node< T > > depth_first_search(const Node< T > &start) const override
Function performs the depth first search algorithm over the graph Note: Thread Safe.
Definition: Graph.hpp:2081
int readFromFile(typename Graph< T >::InputOutputFormat format=Graph< T >::InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool readNodeFeat=false, bool readEdgeWeight=false) override
This function write the graph in an output file Note: Thread Safe.
Definition: Graph.hpp:2135
const DialResult dial(const Node< T > &source, int maxWeight) const override
This function write the graph in an output file Note: Thread Safe.
Definition: Graph.hpp:2117
bool isCyclicDirectedGraphDFS() const override
This function uses DFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:2090
const AdjacencyMatrix< T > getAdjMatrix() const override
This function generate a list of adjacency matrix with every element of the matrix contain the node w...
Definition: Graph.hpp:2054
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:552
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:1416
E_PartitionAlgorithm
Specify the Partition Algorithm.
Definition: Graph.hpp:577
@ GREEDY_VC
A Greedy Vertex-Cut Algorithm.
Definition: Graph.hpp:578
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:787
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:848
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:1538
virtual void removeEdge(unsigned long edgeId)
Function remove an Edge from the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:817
virtual bool isDirectedGraph() const
This function checks if a graph is directed Note: No Thread Safe.
Definition: Graph.hpp:1607
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:1623
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:1266
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:1448
virtual void addEdge(const Edge< T > *edge)
Function add an Edge to the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:807
virtual PartitionMap< T > partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
This function partition a graph in a set of partitions Note: No Thread Safe.
Definition: Graph.hpp:1787
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 write the graph in an output file Note: No Thread Safe.
Definition: Graph.hpp:1769
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:1239
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:828
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:1376
virtual void setEdgeSet(std::list< const Edge< T > * > &edgeSet)
Function set the Edge Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:793
E_InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
Definition: Graph.hpp:566
@ STANDARD_CSV
A standard csv format.
Definition: Graph.hpp:567
@ STANDARD_TSV
A standard tsv format.
Definition: Graph.hpp:568
Definition: Graph.hpp:136
Definition: Graph.hpp:2154
void setPartitionId(unsigned int partitionId)
Set the Partition ID.
Definition: Graph.hpp:2299
unsigned int getPartitionId() const
Get the Partition ID.
Definition: Graph.hpp:2293
Definition: Graph.hpp:2472
Definition: Graph.hpp:221
Definition: Graph.hpp:371
Definition: Graph.hpp:488
Definition: Graph.hpp:184
Definition: Graph.hpp:2453
virtual int writeGraph(const Graph< T > &graph, std::ofstream &file)=0
Function performs the writing of the Graph to the file.
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Graph.hpp:67
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Graph.hpp:58
Struct that contains the information about the partitioning statistics.
Definition: Graph.hpp:76