21 constexpr
char ERR_NO_DIR_OR_UNDIR_EDGE[] =
"Edge are neither Directed neither Undirected";
22 constexpr
char ERR_NO_WEIGHTED_EDGE[] =
"Edge are not Weighted";
23 constexpr
char ERR_DIJ_TARGET_NODE_NOT_REACHABLE[] =
"Target Node not Reachable";
24 constexpr
char ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH[] =
"Target Node not inside Graph";
25 constexpr
char ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH[] =
"Source Node not inside Graph";
27 constexpr
double INF_DOUBLE = std::numeric_limits<double>::max();
37 class DirectedWeightedEdge;
39 class UndirectedWeightedEdge;
46 using AdjacencyMatrix = std::map<const Node<T> *, std::vector<std::pair<const Node<T> *,
const Edge<T> *>>>;
49 std::ostream &operator<<(std::ostream &o,
const Node<T> &node);
51 std::ostream &operator<<(std::ostream &o,
const Edge<T> &edge);
53 std::ostream &operator<<(std::ostream &o,
const DirectedEdge<T> &edge);
55 std::ostream &operator<<(std::ostream &o,
const UndirectedEdge<T> &edge);
57 std::ostream &operator<<(std::ostream &o,
const DirectedWeightedEdge<T> &edge);
59 std::ostream &operator<<(std::ostream &o,
const UndirectedWeightedEdge<T> &edge);
61 std::ostream &operator<<(std::ostream &o,
const Graph<T> &graph);
63 std::ostream &operator<<(std::ostream &o,
const AdjacencyMatrix<T> &adj);
68 std::string errorMessage;
80 Node(
const unsigned long id,
const T &data);
82 const unsigned long &getId()
const;
83 const T &getData()
const;
85 bool operator==(
const Node<T> &b)
const;
86 bool operator<(
const Node<T> &b)
const;
87 friend std::ostream &operator<<<>(std::ostream &os,
const Node<T> &node);
98 const unsigned long &Node<T>::getId()
const
103 template <
typename T>
104 const T &Node<T>::getData()
const
109 template <
typename T>
110 bool Node<T>::operator==(
const Node<T> &b)
const
112 return (this->
id == b.id && this->data == b.data);
115 template <
typename T>
116 bool Node<T>::operator<(
const Node<T> &b)
const
118 return (this->
id < b.id);
130 double getWeight()
const;
131 void setWeight(
const double weight);
135 inline Weighted::Weighted()
141 inline Weighted::Weighted(
const double weight)
143 this->weight = weight;
147 inline double Weighted::getWeight()
const
153 inline void Weighted::setWeight(
const double weight)
155 this->weight = weight;
158 template <
typename T>
163 std::pair<const Node<T> *,
const Node<T> *> nodePair;
167 Edge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair);
168 virtual ~
Edge() =
default;
169 const unsigned long &getId()
const;
170 const std::pair<const Node<T> *,
const Node<T> *> &getNodePair()
const;
171 virtual const std::optional<bool> isDirected()
const;
172 virtual const std::optional<bool> isWeighted()
const;
174 virtual bool operator==(
const Edge<T> &b)
const;
175 bool operator<(
const Edge<T> &b)
const;
179 friend std::ostream &operator<<<>(std::ostream &os,
const Edge<T> &edge);
182 template <
typename T>
188 template <
typename T>
189 Edge<T>::Edge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : nodePair(nodepair)
194 template <
typename T>
195 const unsigned long &Edge<T>::getId()
const
200 template <
typename T>
201 const std::pair<const Node<T> *,
const Node<T> *> &Edge<T>::getNodePair()
const
206 template <
typename T>
207 const std::optional<bool> Edge<T>::isDirected()
const
212 template <
typename T>
213 const std::optional<bool> Edge<T>::isWeighted()
const
218 template <
typename T>
219 bool Edge<T>::operator==(
const Edge<T> &b)
const
221 return (this->
id == b.id && this->nodePair == b.nodePair);
224 template <
typename T>
225 bool Edge<T>::operator<(
const Edge<T> &b)
const
227 return (this->
id < b.id);
230 template <
typename T>
238 const Node<T> &getFrom()
const;
240 const std::optional<bool> isDirected()
const override;
241 virtual const std::optional<bool> isWeighted()
const override;
245 friend std::ostream &operator<<<>(std::ostream &os,
const DirectedEdge<T> &edge);
248 template <
typename T>
253 template <
typename T>
254 DirectedEdge<T>::DirectedEdge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
258 template <
typename T>
259 DirectedEdge<T>::DirectedEdge(
const Edge<T> &edge) : DirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
263 template <
typename T>
264 const Node<T> &DirectedEdge<T>::getFrom()
const
266 return *(Edge<T>::getNodePair().first);
269 template <
typename T>
270 const Node<T> &DirectedEdge<T>::getTo()
const
272 return *(Edge<T>::getNodePair().second);
275 template <
typename T>
276 const std::optional<bool> DirectedEdge<T>::isDirected()
const
281 template <
typename T>
282 const std::optional<bool> DirectedEdge<T>::isWeighted()
const
287 template <
typename T>
295 const Node<T> &getNode1()
const;
296 const Node<T> &getNode2()
const;
297 const std::optional<bool> isDirected()
const override;
298 const std::optional<bool> isWeighted()
const override;
302 friend std::ostream &operator<<<>(std::ostream &os,
const UndirectedEdge<T> &edge);
305 template <
typename T>
310 template <
typename T>
311 UndirectedEdge<T>::UndirectedEdge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair) : Edge<T>(id, nodepair)
315 template <
typename T>
316 UndirectedEdge<T>::UndirectedEdge(
const Edge<T> &edge) : UndirectedEdge(edge.getId(), *(edge.getNodePair().first), *(edge.getNodePair().second))
320 template <
typename T>
321 const Node<T> &UndirectedEdge<T>::getNode1()
const
323 return *(Edge<T>::getNodePair().first);
326 template <
typename T>
327 const Node<T> &UndirectedEdge<T>::getNode2()
const
329 return *(Edge<T>::getNodePair().second);
332 template <
typename T>
333 const std::optional<bool> UndirectedEdge<T>::isDirected()
const
338 template <
typename T>
339 const std::optional<bool> UndirectedEdge<T>::isWeighted()
const
344 template <
typename T>
356 const std::optional<bool> isWeighted()
const override;
363 template <
typename T>
368 template <
typename T>
369 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair,
const double weight) : DirectedEdge<T>(id, nodepair), Weighted(weight)
373 template <
typename T>
374 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
378 template <
typename T>
379 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : DirectedEdge<T>(edge), Weighted(weight)
383 template <
typename T>
384 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const DirectedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted()
388 template <
typename T>
389 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const Edge<T> &edge) : DirectedEdge<T>(edge), Weighted()
393 template <
typename T>
394 DirectedWeightedEdge<T>::DirectedWeightedEdge(
const UndirectedWeightedEdge<T> &edge) : DirectedEdge<T>(edge), Weighted(edge.getWeight())
398 template <
typename T>
399 const std::optional<bool> DirectedWeightedEdge<T>::isWeighted()
const
404 template <
typename T>
416 const std::optional<bool> isWeighted()
const override;
423 template <
typename T>
428 template <
typename T>
429 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const unsigned long id,
const std::pair<
const Node<T> *,
const Node<T> *> &nodepair,
const double weight) : UndirectedEdge<T>(id, nodepair), Weighted(weight)
433 template <
typename T>
434 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
438 template <
typename T>
439 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge,
const double weight) : UndirectedEdge<T>(edge), Weighted(weight)
443 template <
typename T>
444 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const UndirectedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
448 template <
typename T>
449 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const Edge<T> &edge) : UndirectedEdge<T>(edge), Weighted()
453 template <
typename T>
454 UndirectedWeightedEdge<T>::UndirectedWeightedEdge(
const DirectedWeightedEdge<T> &edge) : UndirectedEdge<T>(edge), Weighted(edge.getWeight())
458 template <
typename T>
459 const std::optional<bool> UndirectedWeightedEdge<T>::isWeighted()
const
464 template <
typename T>
466 template <
typename T>
470 std::list<const Edge<T> *> edgeSet;
471 void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix,
const Node<T> *nodeFrom,
const Node<T> *nodeTo,
const Edge<T> *edge)
const;
472 int writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
473 int readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
474 int writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const;
475 int readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight);
476 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);
477 void greedyPartition(std::map<
unsigned int,
Partition<T> *> &partitionMap)
const;
494 } PartitionAlgorithm;
499 const std::list<const Edge<T> *> &getEdgeSet()
const;
500 void setEdgeSet(std::list<
const Edge<T> *> &edgeSet);
501 void addEdge(
const Edge<T> *edge);
502 void removeEdge(
unsigned long edgeId);
503 const std::list<const Node<T> *> getNodeSet()
const;
504 const std::optional<const Edge<T> *> getEdge(
unsigned long edgeId)
const;
508 const AdjacencyMatrix<T> getAdjMatrix()
const;
580 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;
594 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);
604 std::map<unsigned int, Partition<T> *>
partitionGraph(PartitionAlgorithm algorithm,
unsigned int numberOfPartitions)
const;
606 friend std::ostream &operator<<<>(std::ostream &os,
const Graph<T> &graph);
607 friend std::ostream &operator<<<>(std::ostream &os,
const AdjacencyMatrix<T> &adj);
610 template <
typename T>
611 Graph<T>::Graph(
const std::list<
const Edge<T> *> &edgeSet)
613 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
615 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
616 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
618 this->edgeSet.push_back(*edgeSetIt);
623 template <
typename T>
624 const std::list<const Edge<T> *> &Graph<T>::getEdgeSet()
const
629 template <
typename T>
630 void Graph<T>::setEdgeSet(std::list<
const Edge<T> *> &edgeSet)
632 this->edgeSet.clear();
633 for (
auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
635 if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](
const Edge<T> *edge)
636 { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
638 this->edgeSet.push_back(*edgeSetIt);
643 template <
typename T>
644 void Graph<T>::addEdge(
const Edge<T> *edge)
646 if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](
const Edge<T> *edge_a)
647 { return (*edge == *edge_a); }) == edgeSet.end())
649 edgeSet.push_back(edge);
653 template <
typename T>
654 void Graph<T>::removeEdge(
unsigned long edgeId)
656 auto edgeOpt = getEdge(edgeId);
657 if (edgeOpt.has_value())
659 edgeSet.erase(edgeSet.find(edgeOpt.value()));
663 template <
typename T>
664 const std::list<const Node<T> *> Graph<T>::getNodeSet()
const
666 std::list<const Node<T> *> nodeSet;
667 for (
auto edge : edgeSet)
669 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
670 { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
672 nodeSet.push_back(edge->getNodePair().first);
674 if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](
const Node<T> *node)
675 { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
677 nodeSet.push_back(edge->getNodePair().second);
683 template <
typename T>
684 const std::optional<const Edge<T> *> Graph<T>::getEdge(
unsigned long edgeId)
const
687 auto it = edgeSet.begin();
688 for (it; it != edgeSet.end(); ++it)
690 if ((*it)->getId() == edgeId)
699 template <
typename T>
700 void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix,
const Node<T> *nodeFrom,
const Node<T> *nodeTo,
const Edge<T> *edge)
const
702 std::pair<const Node<T> *,
const Edge<T> *> elem = {nodeTo, edge};
703 adjMatrix[nodeFrom].push_back(elem);
708 template <
typename T>
709 int Graph<T>::writeToStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
711 std::ofstream ofileGraph;
712 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
713 ofileGraph.open(completePathToFileGraph);
714 if (!ofileGraph.is_open())
719 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
720 { ofileGraph << e->getId() <<
"," << e->getNodePair().first->getId() <<
"," << e->getNodePair().second->getId() <<
"," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
721 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
726 std::ofstream ofileNodeFeat;
727 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
729 ofileNodeFeat.open(completePathToFileNodeFeat);
730 if (!ofileNodeFeat.is_open())
735 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
736 { ofileNodeFeat << node->getId() <<
"," << node->getData() << std::endl; };
737 auto nodeSet = getNodeSet();
738 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
739 ofileNodeFeat.close();
744 std::ofstream ofileEdgeWeight;
745 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
747 ofileEdgeWeight.open(completePathToFileEdgeWeight);
748 if (!ofileEdgeWeight.is_open())
753 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
754 { 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; };
756 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
757 ofileEdgeWeight.close();
762 template <
typename T>
763 int Graph<T>::readFromStandardFile_csv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
765 std::ifstream ifileGraph;
766 std::ifstream ifileNodeFeat;
767 std::ifstream ifileEdgeWeight;
768 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
769 std::map<unsigned long, bool> edgeDirectedMap;
770 std::map<unsigned long, T> nodeFeatMap;
771 std::map<unsigned long, double> edgeWeightMap;
772 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".csv";
773 ifileGraph.open(completePathToFileGraph);
774 if (!ifileGraph.is_open())
782 unsigned long edgeId;
783 unsigned long nodeId1;
784 unsigned long nodeId2;
786 ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
787 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
788 edgeDirectedMap[edgeId] = directed;
789 if (ifileGraph.fail() || ifileGraph.eof())
791 ifileGraph.ignore(128,
'\n');
797 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
799 ifileNodeFeat.open(completePathToFileNodeFeat);
800 if (!ifileNodeFeat.is_open())
807 unsigned long nodeId;
809 ifileNodeFeat >> nodeId >> comma >> nodeFeat;
810 nodeFeatMap[nodeId] = nodeFeat;
811 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
813 ifileNodeFeat.ignore(128,
'\n');
815 ifileNodeFeat.close();
821 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
823 ifileEdgeWeight.open(completePathToFileEdgeWeight);
824 if (!ifileEdgeWeight.is_open())
831 unsigned long edgeId;
834 ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
837 edgeWeightMap[edgeId] = weight;
839 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
841 ifileEdgeWeight.ignore(128,
'\n');
843 ifileEdgeWeight.close();
845 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
849 template <
typename T>
850 int Graph<T>::writeToStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool writeNodeFeat,
bool writeEdgeWeight)
const
852 std::ofstream ofileGraph;
853 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
854 ofileGraph.open(completePathToFileGraph);
855 if (!ofileGraph.is_open())
860 auto printOutGraph = [&ofileGraph](
const Edge<T> *e)
861 { 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; };
862 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
867 std::ofstream ofileNodeFeat;
868 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
870 ofileNodeFeat.open(completePathToFileNodeFeat);
871 if (!ofileNodeFeat.is_open())
876 auto printOutNodeFeat = [&ofileNodeFeat](
const Node<T> *node)
877 { ofileNodeFeat << node->getId() <<
"\t" << node->getData() << std::endl; };
878 auto nodeSet = getNodeSet();
879 std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
880 ofileNodeFeat.close();
885 std::ofstream ofileEdgeWeight;
886 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
888 ofileEdgeWeight.open(completePathToFileEdgeWeight);
889 if (!ofileEdgeWeight.is_open())
894 auto printOutEdgeWeight = [&ofileEdgeWeight](
const Edge<T> *e)
895 { 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; };
897 std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
898 ofileEdgeWeight.close();
903 template <
typename T>
904 int Graph<T>::readFromStandardFile_tsv(
const std::string &workingDir,
const std::string &OFileName,
bool compress,
bool readNodeFeat,
bool readEdgeWeight)
906 std::ifstream ifileGraph;
907 std::ifstream ifileNodeFeat;
908 std::ifstream ifileEdgeWeight;
909 std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
910 std::map<unsigned long, bool> edgeDirectedMap;
911 std::map<unsigned long, T> nodeFeatMap;
912 std::map<unsigned long, double> edgeWeightMap;
913 std::string completePathToFileGraph = workingDir +
"/" + OFileName +
".tsv";
914 ifileGraph.open(completePathToFileGraph);
915 if (!ifileGraph.is_open())
922 unsigned long edgeId;
923 unsigned long nodeId1;
924 unsigned long nodeId2;
926 ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
927 edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
928 edgeDirectedMap[edgeId] = directed;
929 if (ifileGraph.fail() || ifileGraph.eof())
931 ifileGraph.ignore(128,
'\n');
937 std::string completePathToFileNodeFeat = workingDir +
"/" + OFileName +
"_NodeFeat"
939 ifileNodeFeat.open(completePathToFileNodeFeat);
940 if (!ifileNodeFeat.is_open())
947 unsigned long nodeId;
949 ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
950 nodeFeatMap[nodeId] = nodeFeat;
951 if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
953 ifileNodeFeat.ignore(128,
'\n');
955 ifileNodeFeat.close();
961 std::string completePathToFileEdgeWeight = workingDir +
"/" + OFileName +
"_EdgeWeight"
963 ifileEdgeWeight.open(completePathToFileEdgeWeight);
964 if (!ifileEdgeWeight.is_open())
971 unsigned long edgeId;
974 ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
977 edgeWeightMap[edgeId] = weight;
979 if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
981 ifileEdgeWeight.ignore(128,
'\n');
983 ifileEdgeWeight.close();
985 recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
989 template <
typename T>
990 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)
992 std::map<unsigned long, Node<T> *> nodeMap;
993 for (
auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
995 Node<T> *node1 =
nullptr;
996 Node<T> *node2 =
nullptr;
997 if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
1001 if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
1003 feat = nodeFeatMap.at(edgeIt->second.first);
1005 node1 =
new Node<T>(edgeIt->second.first, feat);
1006 nodeMap[edgeIt->second.first] = node1;
1010 node1 = nodeMap.at(edgeIt->second.first);
1012 if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
1016 if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
1018 feat = nodeFeatMap.at(edgeIt->second.second);
1020 node2 =
new Node<T>(edgeIt->second.second, feat);
1021 nodeMap[edgeIt->second.second] = node2;
1025 node2 = nodeMap.at(edgeIt->second.second);
1028 if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
1030 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1032 auto edge =
new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1037 auto edge =
new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
1043 if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
1045 auto edge =
new DirectedEdge<T>(edgeIt->first, *node1, *node2);
1050 auto edge =
new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
1057 template <
typename T>
1058 void Graph<T>::greedyPartition(std::map<
unsigned int, Partition<T> *> &partitionMap)
const
1060 unsigned int index = 0;
1061 unsigned int numberOfPartitions = partitionMap.size();
1062 if (index == numberOfPartitions)
1067 auto edgeSet = getEdgeSet();
1068 for (
auto edge : edgeSet)
1070 partitionMap.at(index)->addEdge(edge);
1072 index = index % numberOfPartitions;
1076 template <
typename T>
1077 const AdjacencyMatrix<T> Graph<T>::getAdjMatrix()
const
1079 AdjacencyMatrix<T> adj;
1080 auto edgeSetIt = edgeSet.begin();
1081 for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
1083 if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
1085 const DirectedEdge<T> *d_edge =
dynamic_cast<const DirectedEdge<T> *
>(*edgeSetIt);
1086 addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
1088 else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
1090 const UndirectedEdge<T> *ud_edge =
dynamic_cast<const UndirectedEdge<T> *
>(*edgeSetIt);
1092 addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
1093 addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
1103 template <
typename T>
1107 result.success =
false;
1108 result.errorMessage =
"";
1109 result.result = INF_DOUBLE;
1110 auto nodeSet = getNodeSet();
1111 if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1114 result.errorMessage = ERR_DIJ_SOURCE_NODE_NOT_IN_GRAPH;
1117 if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1120 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_IN_GRAPH;
1123 const AdjacencyMatrix<T> adj = getAdjMatrix();
1128 std::map<const Node<T> *,
double> dist;
1130 for (
auto elem : adj)
1132 dist[elem.first] = INF_DOUBLE;
1138 std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1139 std::greater<std::pair<double, const Node<T> *>>>
1143 pq.push(std::make_pair(0.0, &source));
1151 const Node<T> *currentNode = pq.top().second;
1154 double currentDist = pq.top().first;
1160 if (adj.find(currentNode) != adj.end())
1162 for (std::pair<
const Node<T> *,
const Edge<T> *> elem : adj.at(currentNode))
1165 if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1167 if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1170 if (currentDist + dw_edge->getWeight() < dist[elem.first])
1172 dist[elem.first] = currentDist + dw_edge->getWeight();
1173 pq.push(std::make_pair(dist[elem.first], elem.first));
1176 else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1179 if (currentDist + udw_edge->getWeight() < dist[elem.first])
1181 dist[elem.first] = currentDist + udw_edge->getWeight();
1182 pq.push(std::make_pair(dist[elem.first], elem.first));
1188 result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1195 result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1201 if (dist[&target] != INF_DOUBLE)
1203 result.success =
true;
1204 result.errorMessage =
"";
1205 result.result = dist[&target];
1208 result.errorMessage = ERR_DIJ_TARGET_NODE_NOT_REACHABLE;
1213 template <
typename T>
1217 std::vector<Node<T>> visited;
1218 auto nodeSet = getNodeSet();
1220 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1224 const AdjacencyMatrix<T> adj = getAdjMatrix();
1226 std::queue<const Node<T> *> tracker;
1229 visited.push_back(start);
1230 tracker.push(&start);
1231 while (!tracker.empty())
1233 const Node<T> *node = tracker.front();
1235 if (adj.find(node) != adj.end())
1237 for (
auto elem : adj.at(node))
1241 if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1243 visited.push_back(*(elem.first));
1244 tracker.push(elem.first);
1253 template <
typename T>
1257 std::vector<Node<T>> visited;
1258 auto nodeSet = getNodeSet();
1260 if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1264 const AdjacencyMatrix<T> adj = getAdjMatrix();
1265 std::function<void(
const AdjacencyMatrix<T> &,
const Node<T> &, std::vector<
Node<T>> &)> explore;
1266 explore = [&explore](
const AdjacencyMatrix<T> &adj,
const Node<T> &node, std::vector<Node<T>> &visited) ->
void
1268 visited.push_back(node);
1269 if (adj.find(&node) != adj.end())
1271 for (
auto x : adj.at(&node))
1273 if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1275 explore(adj, *(x.first), visited);
1280 explore(adj, start, visited);
1285 template <
typename T>
1288 if (!isDirectedGraph())
1292 enum nodeStates : uint8_t
1298 auto nodeSet = this->getNodeSet();
1299 auto adjMatrix = this->getAdjMatrix();
1308 std::map<unsigned long, nodeStates> state;
1309 for (
auto node : nodeSet)
1311 state[node->getId()] = not_visited;
1313 int stateCounter = 0;
1316 for (
auto node : nodeSet)
1321 if (state[node->getId()] == not_visited)
1324 std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &,
const Node<T> *)> isCyclicDFSHelper;
1325 isCyclicDFSHelper = [
this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states,
const Node<T> *node)
1328 states[node->getId()] = in_stack;
1332 auto const it = adjMatrix.find(node);
1333 if (it != adjMatrix.end())
1335 for (
auto child : it->second)
1339 auto state_of_child = states.at((std::get<0>(child))->getId());
1340 if (state_of_child == not_visited)
1342 if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1347 else if (state_of_child == in_stack)
1359 states[node->getId()] = visited;
1363 if (isCyclicDFSHelper(adjMatrix, state, node))
1375 template <
typename T>
1378 if (!isDirectedGraph())
1382 auto adjMatrix = this->getAdjMatrix();
1383 auto nodeSet = this->getNodeSet();
1385 std::map<unsigned long, unsigned int> indegree;
1386 for (
auto node : nodeSet)
1388 indegree[node->getId()] = 0;
1391 for (
auto const &list : adjMatrix)
1393 auto children = list.second;
1394 for (
auto const &child : children)
1396 indegree[std::get<0>(child)->getId()]++;
1400 std::queue<const Node<T> *> can_be_solved;
1401 for (
auto node : nodeSet)
1405 if (!indegree[node->getId()])
1407 can_be_solved.emplace(&(*node));
1412 auto remain = this->getNodeSet().size();
1414 while (!can_be_solved.empty())
1416 auto solved = can_be_solved.front();
1418 can_be_solved.pop();
1423 auto it = adjMatrix.find(solved);
1424 if (it != adjMatrix.end())
1426 for (
auto child : it->second)
1429 if (--indegree[std::get<0>(child)->getId()] == 0)
1433 can_be_solved.emplace(std::get<0>(child));
1441 return !(remain == 0);
1444 template <
typename T>
1447 auto edgeSet = this->getEdgeSet();
1448 for (
auto edge : edgeSet)
1450 if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1460 template <
typename T>
1463 if (format == InputOutputFormat::STANDARD_CSV)
1465 return writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1467 else if (format == InputOutputFormat::STANDARD_TSV)
1469 return writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1478 template <
typename T>
1481 if (format == InputOutputFormat::STANDARD_CSV)
1483 return readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1485 else if (format == InputOutputFormat::STANDARD_TSV)
1487 return readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1496 template <
typename T>
1499 std::map<unsigned int, Partition<T> *> partitionMap;
1500 for (
unsigned int i = 0; i < numberOfPartitions; ++i)
1504 if (algorithm == PartitionAlgorithm::GREEDY_VC)
1506 greedyPartition(partitionMap);
1511 partitionMap.clear();
1513 return partitionMap;
1516 template <
typename T>
1523 Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet);
1526 unsigned int getPartitionId()
const;
1527 void setPartitionId(
unsigned int partitionId);
1530 unsigned int partitionId;
1533 template <
typename T>
1539 template <
typename T>
1540 Partition<T>::Partition(
unsigned int partitionId) : Graph<T>()
1542 this->partitionId = partitionId;
1545 template <
typename T>
1546 Partition<T>::Partition(
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
1551 template <
typename T>
1552 Partition<T>::Partition(
unsigned int partitionId,
const std::list<
const Edge<T> *> &edgeSet) : Graph<T>(edgeSet)
1554 this->partitionId = partitionId;
1557 template <
typename T>
1558 unsigned int Partition<T>::getPartitionId()
const
1563 template <
typename T>
1564 void Partition<T>::setPartitionId(
unsigned int partitionId)
1566 this->partitionId = partitionId;
1570 template <
typename T>
1571 std::ostream &operator<<(std::ostream &os,
const Node<T> &node)
1574 <<
" Id:\t" << node.id <<
"\n Data:\t" << node.data <<
"\n}";
1578 template <
typename T>
1579 std::ostream &operator<<(std::ostream &os,
const Edge<T> &edge)
1581 os <<
"((Node: " << edge.nodePair.first->getId() <<
")) ?----- |Edge: " << edge.id <<
"|-----? ((Node: " << edge.nodePair.second->getId() <<
"))";
1585 template <
typename T>
1586 std::ostream &operator<<(std::ostream &os,
const DirectedEdge<T> &edge)
1588 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1592 template <
typename T>
1593 std::ostream &operator<<(std::ostream &os,
const UndirectedEdge<T> &edge)
1595 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1599 template <
typename T>
1600 std::ostream &operator<<(std::ostream &os,
const DirectedWeightedEdge<T> &edge)
1602 os <<
"((Node: " << edge.getFrom().getId() <<
")) +----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getTo().getId() <<
"))";
1606 template <
typename T>
1607 std::ostream &operator<<(std::ostream &os,
const UndirectedWeightedEdge<T> &edge)
1609 os <<
"((Node: " << edge.getNode1().getId() <<
")) <----- |Edge: #" << edge.getId() <<
" W:" << edge.getWeight() <<
"|-----> ((Node: " << edge.getNode2().getId() <<
"))";
1613 template <
typename T>
1614 std::ostream &operator<<(std::ostream &os,
const AdjacencyMatrix<T> &adj)
1616 os <<
"Adjacency Matrix:\n";
1617 auto it = adj.begin();
1618 unsigned long max_column = 0;
1619 for (it; it != adj.end(); ++it)
1621 if (it->second.size() > max_column)
1623 max_column = it->second.size();
1626 if (max_column == 0)
1628 os <<
"ERROR in Print\n";
1635 for (
int i = 0; i < max_column; i++)
1640 for (it; it != adj.end(); ++it)
1642 os <<
"|N" << it->first->getId() <<
"|";
1643 auto it2 = it->second.begin();
1644 for (it2; it2 != it->second.end(); ++it2)
1646 os <<
"N" << it2->first->getId() <<
",E" << it2->second->getId() <<
"|";
1649 for (
int i = 0; i < max_column; i++)
Definition: Graph.hpp:232
Definition: Graph.hpp:346
Definition: Graph.hpp:160
Definition: Graph.hpp:468
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:1254
E_PartitionAlgorithm
Definition: Graph.hpp:490
@ GREEDY_VC
A Greedy Vertex-Cut Algorithm.
Definition: Graph.hpp:491
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:1376
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:1461
bool isDirectedGraph() const
This function checks if a graph is directed.
Definition: Graph.hpp:1445
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:1104
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:1286
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:1479
std::map< unsigned int, Partition< T > * > partitionGraph(PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
This function partition a graph in a set of partitions.
Definition: Graph.hpp:1497
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:1214
E_InputOutputFormat
Specify the Input/Output format of the Graph for Import/Export functions.
Definition: Graph.hpp:482
@ STANDARD_CSV
A standard csv format.
Definition: Graph.hpp:483
@ STANDARD_TSV
A standard tsv format.
Definition: Graph.hpp:484
Definition: Graph.hpp:1518
Definition: Graph.hpp:289
Definition: Graph.hpp:406
Definition: Graph.hpp:122