22 constexpr
char ERR_NO_DIR_OR_UNDIR_EDGE[] =
"Edge are neither Directed neither Undirected";
23 constexpr
char ERR_NO_WEIGHTED_EDGE[] =
"Edge are not Weighted";
24 constexpr
char ERR_DIJ_TARGET_NODE_NOT_REACHABLE[] =
"Target Node not Reachable";
25 constexpr
char ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH[] =
"Target Node not inside Graph";
26 constexpr
char ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH[] =
"Source Node not inside Graph";
28 constexpr
double INF_DOUBLE = std::numeric_limits<double>::max();
38 class DirectedWeightedEdge;
40 class UndirectedWeightedEdge;
52 std::string errorMessage;
60 unsigned int numberOfPartitions;
61 unsigned int numberOfNodes;
62 unsigned int replicatedNodesCount;
63 unsigned int numberOfEdges;
64 unsigned int replicatedEdgesCount;
65 unsigned int maxEdgesLoad;
66 unsigned int minEdgesLoad;
67 unsigned int maxNodesLoad;
68 unsigned int minNodesLoad;
69 double balanceEdgesFactor;
70 double balanceNodesFactor;
71 double nodesReplicationFactor;
72 double edgesReplicationFactor;
76 os <<
"Partitioning Stats:\n";
77 os <<
"\tNumber of Partitions: " << partitionStats.numberOfPartitions <<
"\n";
78 os <<
"\tNumber of Nodes: " << partitionStats.numberOfNodes <<
"\n";
79 os <<
"\tNumber of Edges: " << partitionStats.numberOfEdges <<
"\n";
80 os <<
"\tNumber of Nodes Replica: " << partitionStats.replicatedNodesCount <<
"\n";
81 os <<
"\tNumber of Edges Replica: " << partitionStats.replicatedEdgesCount <<
"\n";
82 os <<
"\tNodes Replication Factor: " << partitionStats.nodesReplicationFactor <<
"\n";
83 os <<
"\tEdges Replication Factor: " << partitionStats.edgesReplicationFactor <<
"\n";
84 os <<
"\tMax Edges Load: " << partitionStats.maxEdgesLoad <<
"\n";
85 os <<
"\tMin Edges Load: " << partitionStats.minEdgesLoad <<
"\n";
86 os <<
"\tBalance Edges Factor: " << partitionStats.balanceEdgesFactor <<
"\n";
87 os <<
"\tMax Nodes Load: " << partitionStats.maxNodesLoad <<
"\n";
88 os <<
"\tMin Nodes Load: " << partitionStats.minNodesLoad <<
"\n";
89 os <<
"\tBalance Nodes Factor: " << partitionStats.balanceNodesFactor <<
"\n";
96 using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *,
const Edge<T> *>>>;
99 std::ostream &operator<<(std::ostream &o,
const Node<T> &node);
100 template <
typename T>
101 std::ostream &operator<<(std::ostream &o,
const Edge<T> &edge);
102 template <
typename T>
103 std::ostream &operator<<(std::ostream &o,
const DirectedEdge<T> &edge);
104 template <
typename T>
106 template <
typename T>
108 template <
typename T>
110 template <
typename T>
111 std::ostream &operator<<(std::ostream &o,
const Graph<T> &graph);
112 template <
typename T>
113 std::ostream &operator<<(std::ostream &o,
const AdjacencyMatrix<T> &adj);
114 template <
typename T>
115 using PartitionMap = std::map<unsigned int, Partition<T> *>;
117 template <
typename T>
125 Node(
const unsigned long id,
const T &data);
127 const unsigned long &getId()
const;
128 const T &getData()
const;
130 bool operator==(
const Node<T> &b)
const;
131 bool operator<(
const Node<T> &b)
const;
132 friend std::ostream &operator<<<>(std::ostream &os,
const Node<T> &node);
135 template <
typename T>
142 template <
typename T>
143 const unsigned long &Node<T>::getId()
const
148 template <
typename T>
149 const T &Node<T>::getData()
const
154 template <
typename T>
155 bool Node<T>::operator==(
const Node<T> &b)
const
157 return (this->
id == b.id && this->data == b.data);
160 template <
typename T>
161 bool Node<T>::operator<(
const Node<T> &b)
const
163 return (this->
id < b.id);
175 double getWeight()
const;
176 void setWeight(
const double weight);
180 inline Weighted::Weighted()
186 inline Weighted::Weighted(
const double weight)
188 this->weight = weight;
192 inline double Weighted::getWeight()
const
198 inline void Weighted::setWeight(
const double weight)
200 this->weight = weight;
203 template <
typename T>
208 std::pair<const Node<T> *,
const Node<T> *> nodePair;
212 Edge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair);
213 virtual ~
Edge() =
default;
214 const unsigned long &getId()
const;
215 const std::pair<const Node<T> *,
const Node<T> *> &getNodePair()
const;
216 virtual const std::optional<bool> isDirected()
const;
217 virtual const std::optional<bool> isWeighted()
const;
219 virtual bool operator==(
const Edge<T> &b)
const;
220 bool operator<(
const Edge<T> &b)
const;
224 friend std::ostream &operator<<<>(std::ostream &os,
const Edge<T> &edge);
227 template <
typename T>
233 template <
typename T>
234 Edge<T>::Edge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : nodePair(nodepair)
239 template <
typename T>
240 const unsigned long &Edge<T>::getId()
const
245 template <
typename T>
246 const std::pair<const Node<T> *,
const Node<T> *> &Edge<T>::getNodePair()
const
251 template <
typename T>
252 const std::optional<bool> Edge<T>::isDirected()
const
257 template <
typename T>
258 const std::optional<bool> Edge<T>::isWeighted()
const
263 template <
typename T>
264 bool Edge<T>::operator==(
const Edge<T> &b)
const
266 return (this->
id == b.id && this->nodePair == b.nodePair);
269 template <
typename T>
270 bool Edge<T>::operator<(
const Edge<T> &b)
const
272 return (this->
id < b.id);
275 template <
typename T>
283 const Node<T> &getFrom()
const;
285 const std::optional<bool> isDirected()
const override;
286 virtual const std::optional<bool> isWeighted()
const override;
290 friend std::ostream &operator<<<>(std::ostream &os,
const DirectedEdge<T> &edge);
293 template <
typename T>
298 template <
typename T>
299 DirectedEdge<T>::DirectedEdge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
303 template <
typename T>
304 DirectedEdge<T>::DirectedEdge(
const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
308 template <
typename T>
309 const Node<T> &DirectedEdge<T>::getFrom()
const
311 return *(Edge<T>::getNodePair().first);
314 template <
typename T>
315 const Node<T> &DirectedEdge<T>::getTo()
const
317 return *(Edge<T>::getNodePair().second);
320 template <
typename T>
321 const std::optional<bool> DirectedEdge<T>::isDirected()
const
326 template <
typename T>
327 const std::optional<bool> DirectedEdge<T>::isWeighted()
const
332 template <
typename T>
340 const Node<T> &getNode1()
const;
341 const Node<T> &getNode2()
const;
342 const std::optional<bool> isDirected()
const override;
343 const std::optional<bool> isWeighted()
const override;
347 friend std::ostream &operator<<<>(std::ostream &os,
const UndirectedEdge<T> &edge);
350 template <
typename T>
355 template <
typename T>
356 UndirectedEdge<T>::UndirectedEdge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
360 template <
typename T>
361 UndirectedEdge<T>::UndirectedEdge(
const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
365 template <
typename T>
366 const Node<T> &UndirectedEdge<T>::getNode1()
const
368 return *(Edge<T>::getNodePair().first);
371 template <
typename T>
372 const Node<T> &UndirectedEdge<T>::getNode2()
const
374 return *(Edge<T>::getNodePair().second);
377 template <
typename T>
378 const std::optional<bool> UndirectedEdge<T>::isDirected()
const
383 template <
typename T>
384 const std::optional<bool> UndirectedEdge<T>::isWeighted()
const
389 template <
typename T>
401 const std::optional<bool> isWeighted()
const override;
408 template <
typename T>
413 template <
typename T>
414 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)
418 template <
typename T>
419 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
423 template <
typename T>
424 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
428 template <
typename T>
429 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
433 template <
typename T>
434 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
438 template <
typename T>
439 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
443 template <
typename T>
444 const std::optional<bool> DirectedWeightedEdge<T>::isWeighted()
const
449 template <
typename T>
461 const std::optional<bool> isWeighted()
const override;
468 template <
typename T>
473 template <
typename T>
474 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)
478 template <
typename T>
479 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
483 template <
typename T>
484 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
488 template <
typename T>
489 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
493 template <
typename T>
494 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
498 template <
typename T>
499 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
503 template <
typename T>
504 const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted()
const
509 template <
typename T>
511 template <
typename T>
515 std::list<const Edge<T> *> edgeSet;
516 void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix,
const Node<T> *nodeFrom,
const Node<T> *nodeTo,
const Edge<T> *edge)
const;
517 int writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
518 int readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
519 int writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
520 int readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
521 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);
522 void greedyPartition(PartitionMap<T> &partitionMap)
const;
545 const std::list<const Edge<T> *> &getEdgeSet()
const;
546 void setEdgeSet(std::list<
const Edge<T> *> &edgeSet);
547 void addEdge(
const Edge<T> *edge);
548 void removeEdge(
unsigned long edgeId);
549 const std::list<const Node<T> *> getNodeSet()
const;
550 const std::optional<const Edge<T> *> getEdge(
unsigned long edgeId)
const;
627 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;
641 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);
653 friend std::ostream &operator<<<>(std::ostream &os,
const Graph<T> &graph);
654 friend std::ostream &operator<<<>(std::ostream &os,
const AdjacencyMatrix<T> &adj);
657 template <
typename T>
658 Graph<T>::Graph(
const std::list<
const Edge<T> *> &edgeSet)
660 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
662 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
663 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
665 this->edgeSet.push_back(*edgeSetIt);
670 template <
typename T>
671 const std::list<const Edge<T> *> &Graph<T>::getEdgeSet()
const
676 template <
typename T>
677 void Graph<T>::setEdgeSet(std::list<
const Edge<T> *> &edgeSet)
679 this->edgeSet.clear();
680 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
682 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
683 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
685 this->edgeSet.push_back(*edgeSetIt);
690 template <
typename T>
691 void Graph<T>::addEdge(
const Edge<T> *edge)
693 if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](
const Edge<T> *edge_a)
694 { return (*edge == *edge_a); }) == edgeSet.end())
696 edgeSet.push_back(edge);
700 template <
typename T>
701 void Graph<T>::removeEdge(
unsigned long edgeId)
703 auto edgeOpt = getEdge(edgeId);
704 if (edgeOpt.has_value())
706 edgeSet.erase(edgeSet.find(edgeOpt.value()));
710 template <
typename T>
711 const std::list<const Node<T> *> Graph<T>::getNodeSet()
const
713 std::list<const Node<T> *> nodeSet;
714 for (
auto edge : edgeSet)
716 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
717 { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
719 nodeSet.push_back(edge->getNodePair().first);
721 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
722 { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
724 nodeSet.push_back(edge->getNodePair().second);
730 template <
typename T>
731 const std::optional<const Edge<T> *> Graph<T>::getEdge(
unsigned long edgeId)
const
734 auto it = edgeSet.begin();
735 for (it; it != edgeSet.end(); ++it)
737 if ((*it)->getId() == edgeId)
746 template <
typename T>
747 void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix,
const Node<T> *nodeFrom,
const Node<T> *nodeTo,
const Edge<T> *edge)
const
749 std::pair<const Node<T> *,
const Edge<T> *> elem = {nodeTo, edge};
750 adjMatrix[nodeFrom].push_back(elem);
755 template <
typename T>
756 int Graph<T>::writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
758 std::ofstream ofileGraph;
759 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
760 ofileGraph.open(completePathToFileGraph);
761 if (!ofileGraph.is_open())
766 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
767 { ofileGraph << e->getId() <<
"," << e->getNodePair().first->getId() <<
"," << e->getNodePair().second->getId() <<
"," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
768 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
773 std::ofstream ofileNodeFeat;
774 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
776 ofileNodeFeat.open(completePathToFileNodeFeat);
777 if (!ofileNodeFeat.is_open())
782 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
783 { ofileNodeFeat << node->getId() <<
"," << node->getData() << std::endl; };
784 auto nodeSet = getNodeSet();
785 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
786 ofileNodeFeat.close();
791 std::ofstream ofileEdgeWeight;
792 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
794 ofileEdgeWeight.open(completePathToFileEdgeWeight);
795 if (!ofileEdgeWeight.is_open())
800 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
801 { 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; };
803 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
804 ofileEdgeWeight.close();
809 template <
typename T>
810 int Graph<T>::readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
812 std::ifstream ifileGraph;
813 std::ifstream ifileNodeFeat;
814 std::ifstream ifileEdgeWeight;
815 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
816 std::map<unsigned long, bool> edgeDirectedMap;
817 std::map<unsigned long, T> nodeFeatMap;
818 std::map<unsigned long, double> edgeWeightMap;
819 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
820 ifileGraph.open(completePathToFileGraph);
821 if (!ifileGraph.is_open())
829 unsigned long edgeId;
830 unsigned long nodeId1;
831 unsigned long nodeId2;
833 ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
834 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
835 edgeDirectedMap[edgeId] = directed;
836 if (ifileGraph.fail() || ifileGraph.eof())
838 ifileGraph.ignore(128,
'\n');
844 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
846 ifileNodeFeat.open(completePathToFileNodeFeat);
847 if (!ifileNodeFeat.is_open())
854 unsigned long nodeId;
856 ifileNodeFeat >> nodeId >> comma >> nodeFeat;
857 nodeFeatMap[nodeId] = nodeFeat;
858 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
860 ifileNodeFeat.ignore(128,
'\n');
862 ifileNodeFeat.close();
868 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
870 ifileEdgeWeight.open(completePathToFileEdgeWeight);
871 if (!ifileEdgeWeight.is_open())
878 unsigned long edgeId;
881 ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
884 edgeWeightMap[edgeId] = weight;
886 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
888 ifileEdgeWeight.ignore(128,
'\n');
890 ifileEdgeWeight.close();
892 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
896 template <
typename T>
897 int Graph<T>::writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
899 std::ofstream ofileGraph;
900 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
901 ofileGraph.open(completePathToFileGraph);
902 if (!ofileGraph.is_open())
907 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
908 { 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; };
909 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
914 std::ofstream ofileNodeFeat;
915 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
917 ofileNodeFeat.open(completePathToFileNodeFeat);
918 if (!ofileNodeFeat.is_open())
923 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
924 { ofileNodeFeat << node->getId() <<
"\t" << node->getData() << std::endl; };
925 auto nodeSet = getNodeSet();
926 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
927 ofileNodeFeat.close();
932 std::ofstream ofileEdgeWeight;
933 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
935 ofileEdgeWeight.open(completePathToFileEdgeWeight);
936 if (!ofileEdgeWeight.is_open())
941 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
942 { 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; };
944 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
945 ofileEdgeWeight.close();
950 template <
typename T>
951 int Graph<T>::readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
953 std::ifstream ifileGraph;
954 std::ifstream ifileNodeFeat;
955 std::ifstream ifileEdgeWeight;
956 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
957 std::map<unsigned long, bool> edgeDirectedMap;
958 std::map<unsigned long, T> nodeFeatMap;
959 std::map<unsigned long, double> edgeWeightMap;
960 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
961 ifileGraph.open(completePathToFileGraph);
962 if (!ifileGraph.is_open())
969 unsigned long edgeId;
970 unsigned long nodeId1;
971 unsigned long nodeId2;
973 ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
974 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
975 edgeDirectedMap[edgeId] = directed;
976 if (ifileGraph.fail() || ifileGraph.eof())
978 ifileGraph.ignore(128,
'\n');
984 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
986 ifileNodeFeat.open(completePathToFileNodeFeat);
987 if (!ifileNodeFeat.is_open())
994 unsigned long nodeId;
996 ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
997 nodeFeatMap[nodeId] = nodeFeat;
998 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
1000 ifileNodeFeat.ignore(128,
'\n');
1002 ifileNodeFeat.close();
1008 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
1010 ifileEdgeWeight.open(completePathToFileEdgeWeight);
1011 if (!ifileEdgeWeight.is_open())
1018 unsigned long edgeId;
1021 ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
1024 edgeWeightMap[edgeId] = weight;
1026 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
1028 ifileEdgeWeight.ignore(128,
'\n');
1030 ifileEdgeWeight.close();
1032 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
1036 template <
typename T>
1037 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)
1039 std::map<unsigned long, Node<T> *> nodeMap;
1040 for (
auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
1042 Node<T> *node1 =
nullptr;
1043 Node<T> *node2 =
nullptr;
1044 if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
1048 if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
1050 feat = nodeFeatMap.at(edgeIt->second.first);
1052 node1 =
new Node<T>(edgeIt->second.first, feat);
1053 nodeMap[edgeIt->second.first] = node1;
1057 node1 = nodeMap.at(edgeIt->second.first);
1059 if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
1063 if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
1065 feat = nodeFeatMap.at(edgeIt->second.second);
1067 node2 =
new Node<T>(edgeIt->second.second, feat);
1068 nodeMap[edgeIt->second.second] = node2;
1072 node2 = nodeMap.at(edgeIt->second.second);
1075 if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
1077 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1079 auto edge =
new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1084 auto edge =
new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1090 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1092 auto edge =
new DirectedEdge<T>(edgeIt->first, *node1, *node2);
1097 auto edge =
new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
1104 template <
typename T>
1105 void Graph<T>::greedyPartition(PartitionMap<T> &partitionMap)
const
1107 unsigned int index = 0;
1108 unsigned int numberOfPartitions = partitionMap.size();
1109 if (index == numberOfPartitions)
1114 auto edgeSet = getEdgeSet();
1115 for (
auto edge : edgeSet)
1117 partitionMap.at(index)->addEdge(edge);
1119 index = index % numberOfPartitions;
1123 template <
typename T>
1126 AdjacencyMatrix<T> adj;
1127 auto edgeSetIt = edgeSet.begin();
1128 for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
1130 if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
1133 addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
1135 else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
1139 addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
1140 addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
1150 template <
typename T>
1154 result.success =
false;
1155 result.errorMessage =
"";
1156 result.result = INF_DOUBLE;
1157 auto nodeSet = getNodeSet();
1158 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1161 result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
1164 if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1167 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
1170 const AdjacencyMatrix<T> adj = getAdjMatrix();
1175 std::map<const Node<T> *,
double> dist;
1177 for (
auto elem : adj)
1179 dist[elem.first] = INF_DOUBLE;
1185 std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1186 std::greater<std::pair<double, const Node<T> *>>>
1190 pq.push(std::make_pair(0.0, &source));
1198 const Node<T> *currentNode = pq.top().second;
1201 double currentDist = pq.top().first;
1207 if (adj.find(currentNode) != adj.end())
1209 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
1212 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1214 if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1217 if (currentDist + dw_edge->getWeight() < dist[elem.first])
1219 dist[elem.first] = currentDist + dw_edge->getWeight();
1220 pq.push(std::make_pair(dist[elem.first], elem.first));
1223 else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1226 if (currentDist + udw_edge->getWeight() < dist[elem.first])
1228 dist[elem.first] = currentDist + udw_edge->getWeight();
1229 pq.push(std::make_pair(dist[elem.first], elem.first));
1235 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1242 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1248 if (dist[&target] != INF_DOUBLE)
1250 result.success =
true;
1251 result.errorMessage =
"";
1252 result.result = dist[&target];
1255 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
1260 template <
typename T>
1264 std::vector<Node<T>> visited;
1265 auto nodeSet = getNodeSet();
1267 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1271 const AdjacencyMatrix<T> adj = getAdjMatrix();
1273 std::queue<const Node<T> *> tracker;
1276 visited.push_back(start);
1277 tracker.push(&start);
1278 while (!tracker.empty())
1280 const Node<T> *node = tracker.front();
1282 if (adj.find(node) != adj.end())
1284 for (
auto elem : adj.at(node))
1288 if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1290 visited.push_back(*(elem.first));
1291 tracker.push(elem.first);
1300 template <
typename T>
1304 std::vector<Node<T>> visited;
1305 auto nodeSet = getNodeSet();
1307 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1311 const AdjacencyMatrix<T> adj = getAdjMatrix();
1312 std::function<void(
const AdjacencyMatrix<T> &,
const Node<T> &, std::vector<
Node<T>> &)> explore;
1313 explore = [&explore](
const AdjacencyMatrix<T> &adj,
const Node<T> &node, std::vector<Node<T>> &visited) ->
void
1315 visited.push_back(node);
1316 if (adj.find(&node) != adj.end())
1318 for (
auto x : adj.at(&node))
1320 if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1322 explore(adj, *(x.first), visited);
1327 explore(adj, start, visited);
1332 template <
typename T>
1335 if (!isDirectedGraph())
1339 enum nodeStates : uint8_t
1345 auto nodeSet = this->getNodeSet();
1346 auto adjMatrix = this->getAdjMatrix();
1355 std::map<unsigned long, nodeStates> state;
1356 for (
auto node : nodeSet)
1358 state[node->getId()] = not_visited;
1360 int stateCounter = 0;
1363 for (
auto node : nodeSet)
1368 if (state[node->getId()] == not_visited)
1371 std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &,
const Node<T> *)> isCyclicDFSHelper;
1372 isCyclicDFSHelper = [
this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states,
const Node<T> *node)
1375 states[node->getId()] = in_stack;
1379 auto const it = adjMatrix.find(node);
1380 if (it != adjMatrix.end())
1382 for (
auto child : it->second)
1386 auto state_of_child = states.at((std::get<0>(child))->getId());
1387 if (state_of_child == not_visited)
1389 if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1394 else if (state_of_child == in_stack)
1406 states[node->getId()] = visited;
1410 if (isCyclicDFSHelper(adjMatrix, state, node))
1422 template <
typename T>
1425 if (!isDirectedGraph())
1429 auto adjMatrix = this->getAdjMatrix();
1430 auto nodeSet = this->getNodeSet();
1432 std::map<unsigned long, unsigned int> indegree;
1433 for (
auto node : nodeSet)
1435 indegree[node->getId()] = 0;
1438 for (
auto const &list : adjMatrix)
1440 auto children = list.second;
1441 for (
auto const &child : children)
1443 indegree[std::get<0>(child)->getId()]++;
1447 std::queue<const Node<T> *> can_be_solved;
1448 for (
auto node : nodeSet)
1452 if (!indegree[node->getId()])
1454 can_be_solved.emplace(&(*node));
1459 auto remain = this->getNodeSet().size();
1461 while (!can_be_solved.empty())
1463 auto solved = can_be_solved.front();
1465 can_be_solved.pop();
1470 auto it = adjMatrix.find(solved);
1471 if (it != adjMatrix.end())
1473 for (
auto child : it->second)
1476 if (--indegree[std::get<0>(child)->getId()] == 0)
1480 can_be_solved.emplace(std::get<0>(child));
1488 return !(remain == 0);
1491 template <
typename T>
1494 auto edgeSet = this->getEdgeSet();
1495 for (
auto edge : edgeSet)
1497 if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1507 template <
typename T>
1510 if (format == InputOutputFormat::STANDARD_CSV)
1512 return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1514 else if (format == InputOutputFormat::STANDARD_TSV)
1516 return writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1525 template <
typename T>
1528 if (format == InputOutputFormat::STANDARD_CSV)
1530 return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1532 else if (format == InputOutputFormat::STANDARD_TSV)
1534 return readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1543 template <
typename T>
1546 PartitionMap<T> partitionMap;
1547 for (
unsigned int i = 0; i < numberOfPartitions; ++i)
1551 if (algorithm == PartitionAlgorithm::GREEDY_VC)
1553 greedyPartition(partitionMap);
1558 partitionMap.clear();
1560 return partitionMap;
1563 template <
typename T>
1570 Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet);
1586 unsigned int partitionId;
1596 template <
typename T>
1597 static PartitioningStats getPartitionStats(
const PartitionMap<T> &partitionMap);
1606 template <
typename T>
1607 static unsigned int getMaxEdgesLoad(
const PartitionMap<T> &partitionMap);
1616 template <
typename T>
1617 static unsigned int getMinEdgesLoad(
const PartitionMap<T> &partitionMap);
1626 template <
typename T>
1627 static unsigned int getMaxNodesLoad(
const PartitionMap<T> &partitionMap);
1636 template <
typename T>
1637 static unsigned int getMinNodesLoad(
const PartitionMap<T> &partitionMap);
1646 template <
typename T>
1647 static unsigned int getNumberOfEdges(
const PartitionMap<T> &partitionMap);
1656 template <
typename T>
1657 static unsigned int getNumberOfNodes(
const PartitionMap<T> &partitionMap);
1666 template <
typename T>
1667 static unsigned int getNumberOfReplicatedEdges(
const PartitionMap<T> &partitionMap);
1676 template <
typename T>
1677 static unsigned int getNumberOfReplicatedNodes(
const PartitionMap<T> &partitionMap);
1679 template <
typename T>
1685 template <
typename T>
1686 Partition<T>::Partition(
unsigned int partitionId) : Graph<T>()
1688 this->partitionId = partitionId;
1691 template <
typename T>
1692 Partition<T>::Partition(
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
1697 template <
typename T>
1698 Partition<T>::Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
1700 this->partitionId = partitionId;
1703 template <
typename T>
1709 template <
typename T>
1712 this->partitionId = partitionId;
1715 template <
typename T>
1719 result.numberOfPartitions = partitionMap.size();
1720 result.numberOfNodes = getNumberOfNodes(partitionMap);
1721 result.numberOfEdges = getNumberOfEdges(partitionMap);
1722 result.replicatedNodesCount = getNumberOfReplicatedNodes(partitionMap);
1723 result.replicatedEdgesCount = getNumberOfReplicatedEdges(partitionMap);
1724 result.maxEdgesLoad = getMaxEdgesLoad(partitionMap);
1725 result.minEdgesLoad = getMinEdgesLoad(partitionMap);
1726 result.maxNodesLoad = getMaxNodesLoad(partitionMap);
1727 result.minNodesLoad = getMinNodesLoad(partitionMap);
1728 result.edgesReplicationFactor = (double)result.replicatedEdgesCount / result.numberOfEdges;
1729 result.nodesReplicationFactor = (
double)result.replicatedNodesCount / result.numberOfNodes;
1730 result.balanceEdgesFactor = (double)(result.maxEdgesLoad - result.minEdgesLoad) / (result.maxEdgesLoad);
1731 result.balanceNodesFactor = (double)(result.maxNodesLoad - result.minNodesLoad) / (result.maxNodesLoad);
1735 template <
typename T>
1736 unsigned int getMaxEdgesLoad(
const PartitionMap<T> &partitionMap)
1738 unsigned int maxLoad = 0;
1739 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1741 if (it->second->getEdgeSet().size() > maxLoad)
1743 maxLoad = it->second->getEdgeSet().size();
1749 template <
typename T>
1750 unsigned int getMinEdgesLoad(
const PartitionMap<T> &partitionMap)
1752 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
1753 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1755 if (it->second->getEdgeSet().size() < minLoad)
1757 minLoad = it->second->getEdgeSet().size();
1763 template <
typename T>
1764 unsigned int getMaxNodesLoad(
const PartitionMap<T> &partitionMap)
1766 unsigned int maxLoad = 0;
1767 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1769 if (it->second->getNodeSet().size() > maxLoad)
1771 maxLoad = it->second->getNodeSet().size();
1777 template <
typename T>
1778 unsigned int getMinNodesLoad(
const PartitionMap<T> &partitionMap)
1780 unsigned int minLoad = std::numeric_limits<unsigned int>::max();
1781 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1783 if (it->second->getNodeSet().size() < minLoad)
1785 minLoad = it->second->getNodeSet().size();
1791 template <
typename T>
1792 unsigned int getNumberOfEdges(
const PartitionMap<T> &partitionMap)
1794 unsigned int numberOfEdges = 0;
1795 std::list<const Edge<T> *> edgeSet;
1797 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1799 const std::list<const Edge<T> *> partitionEdgeSet = it->second->getEdgeSet();
1800 for (
auto it2 = partitionEdgeSet.begin(); it2 != partitionEdgeSet.end(); ++it2)
1802 if (std::find_if(edgeSet.begin(), edgeSet.end(), [it2](
const Edge<T> *edge)
1803 { return (*(*it2) == *edge); }) == edgeSet.end())
1805 edgeSet.push_back(*it2);
1810 return edgeSet.size();
1813 template <
typename T>
1814 unsigned int getNumberOfNodes(
const PartitionMap<T> &partitionMap)
1817 unsigned int numberOfNodes = 0;
1818 std::list<const Node<T> *> nodeSet;
1820 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1822 const std::list<const Node<T> *> partitionNodeSet = it->second->getNodeSet();
1823 for (
auto it2 = partitionNodeSet.begin(); it2 != partitionNodeSet.end(); ++it2)
1825 if (std::find_if(nodeSet.begin(), nodeSet.end(), [it2](
const Node<T> *node)
1826 { return (*(*it2) == *node); }) == nodeSet.end())
1828 nodeSet.push_back(*it2);
1833 return nodeSet.size();
1836 template <
typename T>
1837 unsigned int getNumberOfReplicatedEdges(
const PartitionMap<T> &partitionMap)
1840 unsigned int numberOfEdges = 0;
1841 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1843 numberOfEdges += it->second->getEdgeSet().size();
1845 return numberOfEdges;
1848 template <
typename T>
1849 unsigned int getNumberOfReplicatedNodes(
const PartitionMap<T> &partitionMap)
1851 unsigned int numberOfNodes = 0;
1852 for (
auto it = partitionMap.begin(); it != partitionMap.end(); ++it)
1854 numberOfNodes += it->second->getNodeSet().size();
1856 return numberOfNodes;
1860 template <
typename T>
1861 std::ostream &operator<<(std::ostream &os,
const Node<T> &node)
1864 <<
" Id:\t" << node.id <<
"\n Data:\t" << node.data <<
"\n}";
1868 template <
typename T>
1869 std::ostream &operator<<(std::ostream &os,
const Edge<T> &edge)
1871 os <<
"((Node: " << edge.nodePair.first->getId() <<
")) ?----- |Edge: " << edge.id <<
"|-----? ((Node: " << edge.nodePair.second->getId() <<
"))";
1875 template <
typename T>
1876 std::ostream &operator<<(std::ostream &os,
const DirectedEdge<T> &edge)
1878 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1882 template <
typename T>
1883 std::ostream &operator<<(std::ostream &os,
const UndirectedEdge<T> &edge)
1885 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1889 template <
typename T>
1890 std::ostream &operator<<(std::ostream &os,
const DirectedWeightedEdge<T> &edge)
1892 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1896 template <
typename T>
1897 std::ostream &operator<<(std::ostream &os,
const UndirectedWeightedEdge<T> &edge)
1899 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1903 template <
typename T>
1904 std::ostream &operator<<(std::ostream &os,
const AdjacencyMatrix<T> &adj)
1906 os <<
"Adjacency Matrix:\n";
1907 auto it = adj.begin();
1908 unsigned long max_column = 0;
1909 for (it; it != adj.end(); ++it)
1911 if (it->second.size() > max_column)
1913 max_column = it->second.size();
1916 if (max_column == 0)
1918 os <<
"ERROR in Print\n";
1925 for (
int i = 0; i < max_column; i++)
1930 for (it; it != adj.end(); ++it)
1932 os <<
"|N" << it->first->getId() <<
"|";
1933 auto it2 = it->second.begin();
1934 for (it2; it2 != it->second.end(); ++it2)
1936 os <<
"N" << it2->first->getId() <<
",E" << it2->second->getId() <<
"|";
1939 for (
int i = 0; i < max_column; i++)
Definition: Graph.hpp:277
Definition: Graph.hpp:391
Definition: Graph.hpp:205
Definition: Graph.hpp:513
const std::vector< Node< T > > depth_first_search(const Node< T > &start) const
Function performs the depth first search algorithm over the graph.
Definition: Graph.hpp:1301
E_PartitionAlgorithm
Specify the Partition Algorithm.
Definition: Graph.hpp:536
@ GREEDY_VC
A Greedy Vertex-Cut Algorithm.
Definition: Graph.hpp:537
enum CXXGRAPH::Graph::E_PartitionAlgorithm PartitionAlgorithm
Specify the Partition Algorithm.
enum CXXGRAPH::Graph::E_InputOutputFormat InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
bool isCyclicDirectedGraphBFS() const
This function uses BFS to check for cycle in the graph. Pay Attention, this function work only with d...
Definition: Graph.hpp:1423
int writeToFile(InputOutputFormat format=InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool writeNodeFeat=false, bool writeEdgeWeight=false) const
This function write the graph in an output file.
Definition: Graph.hpp:1508
bool isDirectedGraph() const
This function checks if a graph is directed.
Definition: Graph.hpp:1492
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:1151
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:1333
PartitionMap< T > partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
This function partition a graph in a set of partitions.
Definition: Graph.hpp:1544
int readFromFile(InputOutputFormat format=InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool readNodeFeat=false, bool readEdgeWeight=false)
This function write the graph in an output file.
Definition: Graph.hpp:1526
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:1124
const std::vector< Node< T > > breadth_first_search(const Node< T > &start) const
Function performs the breadth first search algorithm over the graph.
Definition: Graph.hpp:1261
E_InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
Definition: Graph.hpp:527
@ STANDARD_CSV
A standard csv format.
Definition: Graph.hpp:528
@ STANDARD_TSV
A standard tsv format.
Definition: Graph.hpp:529
Definition: Graph.hpp:119
Definition: Graph.hpp:1565
void setPartitionId(unsigned int partitionId)
Set the Partition ID.
Definition: Graph.hpp:1710
unsigned int getPartitionId() const
Get the Partition ID.
Definition: Graph.hpp:1704
Definition: Graph.hpp:334
Definition: Graph.hpp:451
Definition: Graph.hpp:167
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Graph.hpp:50
Struct that contains the information about the partitioning statistics.
Definition: Graph.hpp:59