CXXGraph  0.4.0
CXXGraph is a header only, that manages the Graphs and it's algorithm in C++
Graph.hpp
1 /***********************************************************/
2 /*** ______ ____ ______ _ ***/
3 /*** / ___\ \/ /\ \/ / ___|_ __ __ _ _ __ | |__ ***/
4 /*** | | \ / \ / | _| '__/ _` | '_ \| '_ \ ***/
5 /*** | |___ / \ / \ |_| | | | (_| | |_) | | | | ***/
6 /*** \____/_/\_\/_/\_\____|_| \__,_| .__/|_| |_| ***/
7 /*** |_| ***/
8 /***********************************************************/
9 /*** Header-Only C++ Library for Graph ***/
10 /*** Representation and Algorithms ***/
11 /***********************************************************/
12 /*** Author: ZigRazor ***/
13 /*** E-Mail: zigrazor@gmail.com ***/
14 /***********************************************************/
15 /*** Collaboration: ----------- ***/
16 /***********************************************************/
17 /*** License: MPL v2.0 ***/
18 /***********************************************************/
19 
20 #ifndef __CXXGRAPH_GRAPH_H__
21 #define __CXXGRAPH_GRAPH_H__
22 
23 #pragma once
24 
25 #include <utility>
26 #include <set>
27 #include <unordered_set>
28 #include <map>
29 #include <optional>
30 #include <iostream>
31 #include <limits>
32 #include <list>
33 #include <deque>
34 #include <queue>
35 #include <stack>
36 #include <string>
37 #include <cstring>
38 #include <functional>
39 #include <fstream>
40 #include <limits.h>
41 #include <mutex>
42 #include <set>
43 #include <atomic>
44 #include <thread>
45 #include <cmath>
46 #include "zlib.h"
47 
48 #include "Edge/Weighted.hpp"
49 #include "Node/Node.hpp"
50 #include "Edge/Edge.hpp"
51 #include "Edge/DirectedEdge.hpp"
52 #include "Edge/UndirectedEdge.hpp"
53 #include "Edge/DirectedWeightedEdge.hpp"
54 #include "Edge/UndirectedWeightedEdge.hpp"
55 #include "Utility/ThreadSafe.hpp"
56 #include "Utility/Writer.hpp"
57 #include "Utility/Reader.hpp"
58 #include "Utility/ConstString.hpp"
59 #include "Utility/ConstValue.hpp"
60 #include "Utility/Typedef.hpp"
61 #include "Partitioning/Partition.hpp"
62 #include "Partitioning/PartitionAlgorithm.hpp"
63 #include "Partitioning/Partitioner.hpp"
64 #include "Partitioning/Utility/Globals.hpp"
65 
66 
67 
68 
69 namespace CXXGRAPH
70 {
71  //Typedef for Allocator
72  //typedef size_t DataType;
73  //typedef Moya::Allocator<const Edge<T> *,16* 1024> MemoryPoolAllocator;
74  template<typename T>
75  using T_EdgeSet = std::unordered_set<const Edge<T> *>;
76 
77  namespace PARTITIONING
78  {
79  template <typename T>
80  class Partition;
81  }
82 
83  template <typename T>
84  std::ostream &operator<<(std::ostream &o, const Graph<T> &graph);
85  template <typename T>
86  std::ostream &operator<<(std::ostream &o, const AdjacencyMatrix<T> &adj);
87 
89  template <typename T>
90  class Graph
91  {
92  private:
93  T_EdgeSet<T> edgeSet = {};
94  std::optional<std::pair<std::string, char>> getExtenstionAndSeparator(InputOutputFormat format) const;
95  int writeToStandardFile(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight, InputOutputFormat format) const;
96  int readFromStandardFile(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight, InputOutputFormat format);
97  void recreateGraphFromReadFiles(std::unordered_map<unsigned long long, std::pair<std::string, std::string>> &edgeMap, std::unordered_map<unsigned long long, bool> &edgeDirectedMap, std::unordered_map<std::string, T> &nodeFeatMap, std::unordered_map<unsigned long long, double> &edgeWeightMap);
98  int compressFile(const std::string &inputFile, const std::string &outputFile) const;
99  int decompressFile(const std::string &inputFile, const std::string &outputFile) const;
100 
101  public:
102  Graph() = default;
103  Graph(const T_EdgeSet<T> &edgeSet);
104  virtual ~Graph() = default;
113  virtual const T_EdgeSet<T> &getEdgeSet() const;
122  virtual void setEdgeSet(T_EdgeSet<T> &edgeSet);
131  virtual void addEdge(const Edge<T> *edge);
140  virtual void removeEdge(unsigned long long edgeId);
149  virtual const std::set<const Node<T> *> getNodeSet() const;
159  virtual const std::optional<const Edge<T> *> getEdge(unsigned long long edgeId) const;
165  virtual const AdjacencyMatrix<T> getAdjMatrix() const;
175  virtual unsigned long long setFind(std::unordered_map<unsigned long long, Subset> *, const unsigned long long elem) const;
185  virtual void setUnion(std::unordered_map<unsigned long long, Subset> *, const unsigned long long set1, const unsigned long long elem2) const;
192  virtual std::vector<Node<T>> eulerianPath() const;
205  virtual const DijkstraResult dijkstra(const Node<T> &source, const Node<T> &target) const;
219  virtual const BellmanFordResult bellmanford(const Node<T> &source, const Node<T> &target) const;
227  virtual const FWResult floydWarshall() const;
234  virtual const MstResult prim() const;
245  virtual const MstResult boruvka() const;
256  virtual const MstResult kruskal() const;
267  virtual const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const;
278  virtual const std::vector<Node<T>> depth_first_search(const Node<T> &start) const;
279 
288  virtual bool isCyclicDirectedGraphDFS() const;
289 
298  virtual bool isCyclicDirectedGraphBFS() const;
299 
307  virtual bool containsCycle(const T_EdgeSet<T> *) const;
315  virtual bool containsCycle(const T_EdgeSet<T> *edgeSet, std::unordered_map<unsigned long long, Subset> *) const;
316 
324  virtual bool isDirectedGraph() const;
325 
333  virtual bool isUndirectedGraph() const;
334 
342  virtual bool isConnectedGraph() const;
343 
351  virtual bool isStronglyConnectedGraph() const;
352 
363  virtual std::vector<std::vector<Node<T>>> kosaraju() const;
364 
381  virtual const std::vector<Node<T>> graph_slicing(const Node<T> &start) const;
382 
409  virtual const DialResult dial(const Node<T> &source, int maxWeight) const;
410 
419  virtual double fordFulkersonMaxFlow(const Node<T> &source, const Node<T> &target) const;
420 
434  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;
435 
449  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);
450 
460  virtual PartitionMap<T> partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions, double param1 = 0.0, double param2 = 0.0, double param3 = 0.0, unsigned int numberOfthreads = std::thread::hardware_concurrency()) const;
461 
462  friend std::ostream &operator<<<>(std::ostream &os, const Graph<T> &graph);
463  friend std::ostream &operator<<<>(std::ostream &os, const AdjacencyMatrix<T> &adj);
464  };
465 
466  template <typename T>
467  Graph<T>::Graph(const T_EdgeSet<T> &edgeSet)
468  {
469  for (const auto &edgeSetIt : edgeSet)
470  {
471  /*
472  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
473  { return (*edge == *edgeSetIt); }) == this->edgeSet.end())
474  {
475  this->edgeSet.insert(edgeSetIt);
476  }
477  */
478  this->edgeSet.insert(edgeSetIt);
479  }
480  }
481 
482  template <typename T>
483  const T_EdgeSet<T> &Graph<T>::getEdgeSet() const
484  {
485  return edgeSet;
486  }
487 
488  template <typename T>
489  void Graph<T>::setEdgeSet(T_EdgeSet<T> &edgeSet)
490  {
491  this->edgeSet.clear();
492  for (const auto &edgeSetIt : edgeSet)
493  {
494  /*
495  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
496  { return (*edge == *edgeSetIt); }) == this->edgeSet.end())
497  {
498  this->edgeSet.insert(edgeSetIt);
499  }
500  */
501  this->edgeSet.insert(edgeSetIt);
502  }
503  }
504 
505  template <typename T>
506  void Graph<T>::addEdge(const Edge<T> *edge)
507  {
508  /*
509  if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](const Edge<T> *edge_a)
510  { return (*edge == *edge_a); }) == edgeSet.end())
511  {
512  edgeSet.insert(edge);
513  }
514  */
515  edgeSet.insert(edge);
516  }
517 
518  template <typename T>
519  void Graph<T>::removeEdge(unsigned long long edgeId)
520  {
521  auto edgeOpt = Graph<T>::getEdge(edgeId);
522  if (edgeOpt.has_value())
523  {
524  /*
525  edgeSet.erase(std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeOpt](const Edge<T> *edge)
526  { return (*(edgeOpt.value()) == *edge); }));
527  */
528  edgeSet.erase(edgeSet.find(edgeOpt.value()));
529  }
530  }
531 
532  template <typename T>
533  const std::set<const Node<T> *> Graph<T>::getNodeSet() const
534  {
535  std::set <const Node<T> *> nodeSet;
536  for (const auto &edgeSetIt : edgeSet)
537  {
538  nodeSet.insert(edgeSetIt->getNodePair().first);
539  nodeSet.insert(edgeSetIt->getNodePair().second);
540  }
541  /*
542  std::deque<const Node<T> *> nodeSet;
543  for (const auto &edge : edgeSet)
544  {
545  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
546  { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
547  {
548  nodeSet.push_back(edge->getNodePair().first);
549  }
550  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
551  { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
552  {
553  nodeSet.push_back(edge->getNodePair().second);
554  }
555  }
556  */
557  return nodeSet;
558  }
559 
560  template <typename T>
561  const std::optional<const Edge<T> *> Graph<T>::getEdge(unsigned long long edgeId) const
562  {
563  for (const auto &it : edgeSet)
564  {
565  if (it->getId() == edgeId)
566  {
567  return it;
568  }
569  }
570 
571  return std::nullopt;
572  }
573 
574  template <typename T>
575  std::optional<std::pair<std::string, char>> Graph<T>::getExtenstionAndSeparator(InputOutputFormat format) const
576  {
577  if (format == InputOutputFormat::STANDARD_CSV)
578  {
579  return std::pair<std::string, char>(".csv", ',');
580  }
581  else if (format == InputOutputFormat::STANDARD_TSV)
582  {
583  return std::pair<std::string, char>(".tsv", '\t');
584  }
585  else
586  {
587  return std::nullopt;
588  }
589  }
590 
591  template <typename T>
592  int Graph<T>::writeToStandardFile(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight, InputOutputFormat format) const
593  {
594  auto result = getExtenstionAndSeparator(format);
595  if (!result)
596  {
597  std::cerr << "Unknown format\n";
598  return -1;
599  }
600  auto &[extension, separator] = *result;
601 
602  std::ofstream ofileGraph;
603  std::string completePathToFileGraph = workingDir + "/" + OFileName + extension;
604  ofileGraph.open(completePathToFileGraph);
605  if (!ofileGraph.is_open())
606  {
607  // ERROR File Not Open
608  return -1;
609  }
610 
611  for (const auto &edge : edgeSet)
612  {
613  ofileGraph << edge->getId() << separator
614  << edge->getNodePair().first->getUserId() << separator
615  << edge->getNodePair().second->getUserId() << separator
616  << ((edge->isDirected().has_value() && edge->isDirected().value()) ? 1 : 0)
617  << std::endl;
618  }
619  ofileGraph.close();
620 
621  if (writeNodeFeat)
622  {
623  std::ofstream ofileNodeFeat;
624  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat" + extension;
625  ofileNodeFeat.open(completePathToFileNodeFeat);
626  if (!ofileNodeFeat.is_open())
627  {
628  // ERROR File Not Open
629  return -1;
630  }
631  auto nodeSet = getNodeSet();
632  for (const auto &node : nodeSet)
633  {
634  ofileNodeFeat << node->getUserId() << separator << node->getData() << std::endl;
635  }
636  ofileNodeFeat.close();
637  }
638 
639  if (writeEdgeWeight)
640  {
641  std::ofstream ofileEdgeWeight;
642  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight" + extension;
643  ofileEdgeWeight.open(completePathToFileEdgeWeight);
644  if (!ofileEdgeWeight.is_open())
645  {
646  // ERROR File Not Open
647  std::cout << "ERROR File Not Open" << std::endl;
648  return -1;
649  }
650 
651  for (const auto &edge : edgeSet)
652  {
653  ofileEdgeWeight << edge->getId() << separator
654  << (edge->isWeighted().has_value() && edge->isWeighted().value() ? (dynamic_cast<const Weighted *>(edge))->getWeight() : 0.0) << separator
655  << (edge->isWeighted().has_value() && edge->isWeighted().value() ? 1 : 0)
656  << std::endl;
657  }
658  ofileEdgeWeight.close();
659  }
660  return 0;
661  }
662 
663  // This ctype facet classifies ',' and '\t' as whitespace
664  struct csv_whitespace : std::ctype<char>
665  {
666  static const mask *make_table()
667  {
668  // make a copy of the "C" locale table
669  static std::vector<mask> v(classic_table(), classic_table() + table_size);
670  v[','] |= space; // comma will be classified as whitespace
671  v['\t'] |= space;
672  v[' '] &= ~space; // space will not be classified as whitespace
673  return &v[0];
674  }
675  csv_whitespace(std::size_t refs = 0) : ctype(make_table(), false, refs) {}
676  };
677 
678  template <typename T>
679  int Graph<T>::readFromStandardFile(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight, InputOutputFormat format)
680  {
681  auto result = getExtenstionAndSeparator(format);
682  if (!result)
683  {
684  std::cerr << "Unknown format\n";
685  return -1;
686  }
687  auto &[extension, separator] = *result;
688 
689  std::ifstream ifileGraph;
690  std::ifstream ifileNodeFeat;
691  std::ifstream ifileEdgeWeight;
692 
693  std::unordered_map<unsigned long long, std::pair<std::string, std::string>> edgeMap;
694  std::unordered_map<unsigned long long, bool> edgeDirectedMap;
695  std::unordered_map<std::string, T> nodeFeatMap;
696  std::unordered_map<unsigned long long, double> edgeWeightMap;
697  std::string completePathToFileGraph = workingDir + "/" + OFileName + extension;
698 
699  ifileGraph.open(completePathToFileGraph);
700  if (!ifileGraph.is_open())
701  {
702  // ERROR File Not Open
703  //std::cout << "ERROR File Not Open : " << completePathToFileGraph << std::endl;
704  return -1;
705  }
706 
707  ifileGraph.imbue(std::locale(ifileGraph.getloc(), new csv_whitespace));
708  unsigned long long edgeId;
709  std::string nodeId1;
710  std::string nodeId2;
711  bool directed;
712  while (ifileGraph >> edgeId >> nodeId1 >> nodeId2 >> directed)
713  { /* loop continually */
714  edgeMap[edgeId] = std::pair<std::string, std::string>(nodeId1, nodeId2);
715  edgeDirectedMap[edgeId] = directed;
716  }
717  ifileGraph.close();
718  if (compress)
719  remove(completePathToFileGraph.c_str());
720 
721  if (readNodeFeat)
722  {
723  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat" + extension;
724  ifileNodeFeat.open(completePathToFileNodeFeat);
725  if (!ifileNodeFeat.is_open())
726  {
727  // ERROR File Not Open
728  //std::cout << "ERROR File Not Open" << std::endl;
729  return -1;
730  }
731  ifileNodeFeat.imbue(std::locale(ifileGraph.getloc(), new csv_whitespace));
732  std::string nodeId;
733  T nodeFeat;
734  while (ifileNodeFeat >> nodeId >> nodeFeat)
735  {
736  nodeFeatMap[nodeId] = nodeFeat;
737  }
738  ifileNodeFeat.close();
739  if (compress)
740  remove(completePathToFileNodeFeat.c_str());
741  }
742 
743  if (readEdgeWeight)
744  {
745  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight" + extension;
746  ifileEdgeWeight.open(completePathToFileEdgeWeight);
747  if (!ifileEdgeWeight.is_open())
748  {
749  // ERROR File Not Open
750  //std::cout << "ERROR File Not Open" << std::endl;
751  return -1;
752  }
753  ifileEdgeWeight.imbue(std::locale(ifileGraph.getloc(), new csv_whitespace));
754  unsigned long long edgeId;
755  double weight;
756  bool weighted;
757  while (ifileEdgeWeight >> edgeId >> weight >> weighted)
758  { /* loop continually */
759  if (weighted)
760  {
761  edgeWeightMap[edgeId] = weight;
762  }
763  }
764  ifileEdgeWeight.close();
765  if (compress)
766  remove(completePathToFileEdgeWeight.c_str());
767  }
768  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
769  return 0;
770  }
771 
772  template <typename T>
773  void Graph<T>::recreateGraphFromReadFiles(std::unordered_map<unsigned long long, std::pair<std::string, std::string>> &edgeMap, std::unordered_map<unsigned long long, bool> &edgeDirectedMap, std::unordered_map<std::string, T> &nodeFeatMap, std::unordered_map<unsigned long long, double> &edgeWeightMap)
774  {
775  std::unordered_map<std::string, Node<T> *> nodeMap;
776  for (const auto &edgeIt : edgeMap)
777  {
778  Node<T> *node1 = nullptr;
779  Node<T> *node2 = nullptr;
780  if (nodeMap.find(edgeIt.second.first) == nodeMap.end())
781  {
782  // Create new Node
783  T feat;
784  if (nodeFeatMap.find(edgeIt.second.first) != nodeFeatMap.end())
785  {
786  feat = nodeFeatMap.at(edgeIt.second.first);
787  }
788  node1 = new Node<T>(edgeIt.second.first, feat);
789  nodeMap[edgeIt.second.first] = node1;
790  }
791  else
792  {
793  node1 = nodeMap.at(edgeIt.second.first);
794  }
795  if (nodeMap.find(edgeIt.second.second) == nodeMap.end())
796  {
797  // Create new Node
798  T feat;
799  if (nodeFeatMap.find(edgeIt.second.second) != nodeFeatMap.end())
800  {
801  feat = nodeFeatMap.at(edgeIt.second.second);
802  }
803  node2 = new Node<T>(edgeIt.second.second, feat);
804  nodeMap[edgeIt.second.second] = node2;
805  }
806  else
807  {
808  node2 = nodeMap.at(edgeIt.second.second);
809  }
810 
811  if (edgeWeightMap.find(edgeIt.first) != edgeWeightMap.end())
812  {
813  if (edgeDirectedMap.find(edgeIt.first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt.first))
814  {
815  auto edge = new DirectedWeightedEdge<T>(edgeIt.first, *node1, *node2, edgeWeightMap.at(edgeIt.first));
816  addEdge(edge);
817  }
818  else
819  {
820  auto edge = new UndirectedWeightedEdge<T>(edgeIt.first, *node1, *node2, edgeWeightMap.at(edgeIt.first));
821  addEdge(edge);
822  }
823  }
824  else
825  {
826  if (edgeDirectedMap.find(edgeIt.first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt.first))
827  {
828  auto edge = new DirectedEdge<T>(edgeIt.first, *node1, *node2);
829  addEdge(edge);
830  }
831  else
832  {
833  auto edge = new UndirectedEdge<T>(edgeIt.first, *node1, *node2);
834  addEdge(edge);
835  }
836  }
837  }
838  }
839 
840  template <typename T>
841  int Graph<T>::compressFile(const std::string &inputFile, const std::string &outputFile) const
842  {
843  std::ifstream ifs;
844  ifs.open(inputFile);
845  if (!ifs.is_open())
846  {
847  // ERROR File Not Open
848  return -1;
849  }
850  std::string content((std::istreambuf_iterator<char>(ifs)),
851  (std::istreambuf_iterator<char>()));
852 
853  const char *content_ptr = content.c_str();
854  gzFile outFileZ = gzopen(outputFile.c_str(), "wb");
855  if (outFileZ == NULL)
856  {
857  // printf("Error: Failed to gzopen %s\n", outputFile.c_str());
858  return -1;
859  }
860 
861  unsigned int zippedBytes;
862  zippedBytes = gzwrite(outFileZ, content_ptr, strlen(content_ptr));
863 
864  ifs.close();
865  gzclose(outFileZ);
866  return 0;
867  }
868 
869  template <typename T>
870  int Graph<T>::decompressFile(const std::string &inputFile, const std::string &outputFile) const
871  {
872  gzFile inFileZ = gzopen(inputFile.c_str(), "rb");
873  if (inFileZ == NULL)
874  {
875  // printf("Error: Failed to gzopen %s\n", inputFile.c_str());
876  return -1;
877  }
878  unsigned char unzipBuffer[8192];
879  unsigned int unzippedBytes;
880  std::vector<unsigned char> unzippedData;
881  std::ofstream ofs;
882  ofs.open(outputFile);
883  if (!ofs.is_open())
884  {
885  // ERROR File Not Open
886  return -1;
887  }
888  while (true)
889  {
890  unzippedBytes = gzread(inFileZ, unzipBuffer, 8192);
891  if (unzippedBytes > 0)
892  {
893  unzippedData.insert(unzippedData.end(), unzipBuffer, unzipBuffer + unzippedBytes);
894  }
895  else
896  {
897  break;
898  }
899  }
900  for (const auto &c : unzippedData)
901  {
902  ofs << c;
903  }
904  ofs << std::endl;
905  ofs.close();
906  gzclose(inFileZ);
907  return 0;
908  }
909 
910  template <typename T>
911  unsigned long long Graph<T>::setFind(std::unordered_map<unsigned long long, Subset> *subsets, const unsigned long long nodeId) const
912  {
913  // find root and make root as parent of i
914  // (path compression)
915  if ((*subsets)[nodeId].parent != nodeId)
916  {
917  (*subsets)[nodeId].parent = Graph<T>::setFind(subsets, (*subsets)[nodeId].parent);
918  }
919 
920  return (*subsets)[nodeId].parent;
921  }
922 
923  template <typename T>
924  void Graph<T>::setUnion(std::unordered_map<unsigned long long, Subset> *subsets, const unsigned long long elem1, const unsigned long long elem2) const
925  {
926  // if both sets have same parent
927  // then there's nothing to be done
928  if ((*subsets)[elem1].parent == (*subsets)[elem2].parent)
929  return;
930  auto elem1Parent = Graph<T>::setFind(subsets, elem1);
931  auto elem2Parent = Graph<T>::setFind(subsets, elem2);
932  if ((*subsets)[elem1Parent].rank < (*subsets)[elem2Parent].rank)
933  (*subsets)[elem1].parent = elem2Parent;
934  else if ((*subsets)[elem1Parent].rank > (*subsets)[elem2Parent].rank)
935  (*subsets)[elem2].parent = elem1Parent;
936  else
937  {
938  (*subsets)[elem2].parent = elem1Parent;
939  (*subsets)[elem1Parent].rank++;
940  }
941  }
942 
943  template <typename T>
944  std::vector<Node<T>> Graph<T>::eulerianPath() const
945  {
946  const auto nodeSet = Graph<T>::getNodeSet();
947  auto adj = Graph<T>::getAdjMatrix();
948  std::vector<Node<T>> eulerPath;
949  std::vector<const Node<T> *> currentPath;
950  auto currentNode = *(nodeSet.begin());
951  currentPath.push_back(currentNode);
952  while (currentPath.size() > 0)
953  {
954  auto &edges = adj.at(currentNode);
955  // we keep removing the edges that
956  // have been traversed from the adjacency list
957  if (edges.size())
958  {
959  auto firstEdge = edges.back().second;
960  auto nextNodeId = firstEdge->getNodePair().second;
961  currentPath.push_back(nextNodeId);
962  currentNode = nextNodeId;
963  edges.pop_back();
964  }
965  else
966  {
967  eulerPath.push_back(*currentNode);
968  currentNode = currentPath.back();
969  currentPath.pop_back();
970  }
971  }
972  return eulerPath;
973  }
974 
975  template <typename T>
976  const AdjacencyMatrix<T> Graph<T>::getAdjMatrix() const
977  {
978 
979  AdjacencyMatrix<T> adj;
980  auto addElementToAdjMatrix = [&adj](const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge){
981  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
982  adj[nodeFrom].push_back(std::move(elem));
983  };
984  for (const auto &edgeSetIt : edgeSet)
985  {
986  if (edgeSetIt->isDirected().has_value() && edgeSetIt->isDirected().value())
987  {
988  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(edgeSetIt);
989  addElementToAdjMatrix(&(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
990  }
991  else if (edgeSetIt->isDirected().has_value() && !edgeSetIt->isDirected().value())
992  {
993  const UndirectedEdge<T> *ud_edge = dynamic_cast<const UndirectedEdge<T> *>(edgeSetIt);
994  ;
995  addElementToAdjMatrix(&(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
996  addElementToAdjMatrix(&(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
997  }
998  else
999  { // is a simple edge we cannot create adj matrix
1000  return adj;
1001  }
1002  }
1003  return adj;
1004  }
1005 
1006  template <typename T>
1007  const DijkstraResult Graph<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
1008  {
1009  DijkstraResult result;
1010  auto nodeSet = Graph<T>::getNodeSet();
1011  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1012  {
1013  // check if source node exist in the graph
1014  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1015  return result;
1016  }
1017  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1018  {
1019  // check if target node exist in the graph
1020  result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
1021  return result;
1022  }
1023  const AdjacencyMatrix<T> adj = Graph<T>::getAdjMatrix();
1024  // n denotes the number of vertices in graph
1025  int n = adj.size();
1026 
1027  // setting all the distances initially to INF_DOUBLE
1028  std::unordered_map<const Node<T> *, double> dist;
1029 
1030  for (const auto &node : nodeSet )
1031  {
1032  dist[node] = INF_DOUBLE;
1033  }
1034 
1035  // creating a min heap using priority queue
1036  // first element of pair contains the distance
1037  // second element of pair contains the vertex
1038  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1039  std::greater<std::pair<double, const Node<T> *>>>
1040  pq;
1041 
1042  // pushing the source vertex 's' with 0 distance in min heap
1043  pq.push(std::make_pair(0.0, &source));
1044 
1045  // marking the distance of source as 0
1046  dist[&source] = 0;
1047 
1048  while (!pq.empty())
1049  {
1050  // second element of pair denotes the node / vertex
1051  const Node<T> *currentNode = pq.top().second;
1052 
1053  // first element of pair denotes the distance
1054  double currentDist = pq.top().first;
1055 
1056  pq.pop();
1057 
1058  // for all the reachable vertex from the currently exploring vertex
1059  // we will try to minimize the distance
1060  if (adj.find(currentNode) != adj.end())
1061  {
1062  for (const auto &elem : adj.at(currentNode))
1063  {
1064  // minimizing distances
1065  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1066  {
1067  if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
1068  {
1069  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(elem.second);
1070  if (dw_edge->getWeight() < 0)
1071  {
1072  result.errorMessage = ERR_NEGATIVE_WEIGHTED_EDGE;
1073  return result;
1074  }
1075  else if (currentDist + dw_edge->getWeight() < dist[elem.first])
1076  {
1077  dist[elem.first] = currentDist + dw_edge->getWeight();
1078  pq.push(std::make_pair(dist[elem.first], elem.first));
1079  }
1080  }
1081  else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
1082  {
1083  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
1084  if (udw_edge->getWeight() < 0)
1085  {
1086  result.errorMessage = ERR_NEGATIVE_WEIGHTED_EDGE;
1087  return result;
1088  }
1089  else if (currentDist + udw_edge->getWeight() < dist[elem.first])
1090  {
1091  dist[elem.first] = currentDist + udw_edge->getWeight();
1092  pq.push(std::make_pair(dist[elem.first], elem.first));
1093  }
1094  }
1095  else
1096  {
1097  // ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
1098  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1099  return result;
1100  }
1101  }
1102  else
1103  {
1104  // No Weighted Edge
1105  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1106  return result;
1107  }
1108  }
1109  }
1110  }
1111  if (dist[&target] != INF_DOUBLE)
1112  {
1113  result.success = true;
1114  result.errorMessage = "";
1115  result.result = dist[&target];
1116  return result;
1117  }
1118  result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
1119  return result;
1120  }
1121 
1122  template <typename T>
1123  const BellmanFordResult Graph<T>::bellmanford(const Node<T> &source, const Node<T> &target) const
1124  {
1125  BellmanFordResult result;
1126  result.success = false;
1127  result.errorMessage = "";
1128  result.result = INF_DOUBLE;
1129  auto nodeSet = Graph<T>::getNodeSet();
1130  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1131  {
1132  // check if source node exist in the graph
1133  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1134  return result;
1135  }
1136  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1137  {
1138  // check if target node exist in the graph
1139  result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
1140  return result;
1141  }
1142  // setting all the distances initially to INF_DOUBLE
1143  std::unordered_map<const Node<T> *, double> dist, currentDist;
1144  // n denotes the number of vertices in graph
1145  auto n = nodeSet.size();
1146  for (const auto &elem : nodeSet)
1147  {
1148  dist[elem] = INF_DOUBLE;
1149  currentDist[elem] = INF_DOUBLE;
1150  }
1151 
1152  // marking the distance of source as 0
1153  dist[&source] = 0;
1154  // set if node distances in two consecutive
1155  // iterations remain the same.
1156  auto earlyStopping = false;
1157  // outer loop for vertex relaxation
1158  for (int i = 0; i < n - 1; ++i)
1159  {
1160  auto edgeSet = Graph<T>::getEdgeSet();
1161  // inner loop for distance updates of
1162  // each relaxation
1163  for (const auto &edge : edgeSet)
1164  {
1165  auto elem = edge->getNodePair();
1166  if (edge->isWeighted().has_value() && edge->isWeighted().value())
1167  {
1168  auto edge_weight = (dynamic_cast<const Weighted *>(edge))->getWeight();
1169  if (dist[elem.first] + edge_weight < dist[elem.second])
1170  dist[elem.second] = dist[elem.first] + edge_weight;
1171  }
1172  else
1173  {
1174  // No Weighted Edge
1175  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1176  return result;
1177  }
1178  }
1179  auto flag = true;
1180  for (const auto &[key, value] : dist)
1181  {
1182  if (currentDist[key] != value)
1183  {
1184  flag = false;
1185  break;
1186  }
1187  }
1188  for (const auto &[key, value] : dist)
1189  {
1190  currentDist[key] = value; // update the current distance
1191  }
1192  if (flag)
1193  {
1194  earlyStopping = true;
1195  break;
1196  }
1197  }
1198 
1199  // check if there exists a negative cycle
1200  if (!earlyStopping)
1201  {
1202  auto edgeSet = Graph<T>::getEdgeSet();
1203  for (const auto &edge : edgeSet)
1204  {
1205  auto elem = edge->getNodePair();
1206  auto edge_weight = (dynamic_cast<const Weighted *>(edge))->getWeight();
1207  if (dist[elem.first] + edge_weight < dist[elem.second])
1208  {
1209  result.success = true;
1210  result.negativeCycle = true;
1211  result.errorMessage = "";
1212  return result;
1213  }
1214  }
1215  }
1216 
1217  if (dist[&target] != INF_DOUBLE)
1218  {
1219  result.success = true;
1220  result.errorMessage = "";
1221  result.negativeCycle = false;
1222  result.result = dist[&target];
1223  return result;
1224  }
1225  result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
1226  result.result = -1;
1227  return result;
1228  }
1229 
1230  template <typename T>
1231  const FWResult Graph<T>::floydWarshall() const
1232  {
1233  FWResult result;
1234  result.success = false;
1235  result.errorMessage = "";
1236  std::unordered_map<std::pair<std::string, std::string>, double, CXXGRAPH::pair_hash> pairwise_dist;
1237  const auto &nodeSet = Graph<T>::getNodeSet();
1238  // create a pairwise distance matrix with distance node distances
1239  // set to inf. Distance of node to itself is set as 0.
1240  for (const auto &elem1 : nodeSet)
1241  {
1242  for (const auto &elem2 : nodeSet)
1243  {
1244  auto key = std::make_pair(elem1->getUserId(), elem2->getUserId());
1245  if (elem1 != elem2)
1246  pairwise_dist[key] = INF_DOUBLE;
1247  else
1248  pairwise_dist[key] = 0.0;
1249  }
1250  }
1251 
1252  const auto &edgeSet = Graph<T>::getEdgeSet();
1253  // update the weights of nodes
1254  // connected by edges
1255  for (const auto &edge : edgeSet)
1256  {
1257  const auto &elem = edge->getNodePair();
1258  if (edge->isWeighted().has_value() && edge->isWeighted().value())
1259  {
1260  auto edgeWeight = (dynamic_cast<const Weighted *>(edge))->getWeight();
1261  auto key = std::make_pair(elem.first->getUserId(), elem.second->getUserId());
1262  pairwise_dist[key] = edgeWeight;
1263  }
1264  else
1265  {
1266  // if an edge exists but has no weight associated
1267  // with it, we return an error message
1268  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1269  return result;
1270  }
1271  }
1272 
1273  for (const auto &k : nodeSet)
1274  {
1275  // set all vertices as source one by one
1276  for (const auto &src : nodeSet)
1277  {
1278  // iterate through all vertices as destination for the
1279  // current source
1280  auto src_k = std::make_pair(src->getUserId(), k->getUserId());
1281  for (const auto &dst : nodeSet)
1282  {
1283  // If vertex k provides a shorter path than
1284  // src to dst, update the value of
1285  // pairwise_dist[src_to_dst]
1286  auto src_dst = std::make_pair(src->getUserId(), dst->getUserId());
1287  auto k_dst = std::make_pair(k->getUserId(), dst->getUserId());
1288  if (pairwise_dist[src_dst] > (pairwise_dist[src_k] + pairwise_dist[k_dst]) && (pairwise_dist[k_dst] != INF_DOUBLE && pairwise_dist[src_k] != INF_DOUBLE))
1289  pairwise_dist[src_dst] = pairwise_dist[src_k] + pairwise_dist[k_dst];
1290  }
1291  }
1292  }
1293 
1294  result.success = true;
1295  // presense of negative number in the diagonal indicates
1296  // that that the graph contains a negative cycle
1297  for (const auto &node : nodeSet)
1298  {
1299  auto diag = std::make_pair(node->getUserId(), node->getUserId());
1300  if (pairwise_dist[diag] < 0.)
1301  {
1302  result.negativeCycle = true;
1303  return result;
1304  }
1305  }
1306  result.result = std::move(pairwise_dist);
1307  return result;
1308  }
1309 
1310  template <typename T>
1311  const MstResult Graph<T>::prim() const
1312  {
1313  MstResult result;
1314  result.success = false;
1315  result.errorMessage = "";
1316  result.mstCost = INF_DOUBLE;
1317  if (!isUndirectedGraph())
1318  {
1319  result.errorMessage = ERR_DIR_GRAPH;
1320  return result;
1321  }
1322  if (!isConnectedGraph())
1323  {
1324  result.errorMessage = ERR_NOT_STRONG_CONNECTED;
1325  return result;
1326  }
1327  auto nodeSet = Graph<T>::getNodeSet();
1328  auto n = nodeSet.size();
1329  const AdjacencyMatrix<T> adj = Graph<T>::getAdjMatrix();
1330 
1331  // setting all the distances initially to INF_DOUBLE
1332  std::unordered_map<const Node<T> *, double> dist;
1333  for (const auto &elem : adj)
1334  {
1335  dist[elem.first] = INF_DOUBLE;
1336  }
1337 
1338  // creating a min heap using priority queue
1339  // first element of pair contains the distance
1340  // second element of pair contains the vertex
1341  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1342  std::greater<std::pair<double, const Node<T> *>>>
1343  pq;
1344 
1345  // pushing the source vertex 's' with 0 distance in min heap
1346  auto source = *(nodeSet.begin());
1347  pq.push(std::make_pair(0.0, source));
1348  result.mstCost = 0;
1349  std::vector<unsigned long long> doneNode;
1350  // mark source node as done
1351  // otherwise we get (0, 0) also in mst
1352  doneNode.push_back(source->getId());
1353  // stores the parent and corresponding child node
1354  // of the edges that are part of MST
1355  std::unordered_map<unsigned long long, std::string> parentNode;
1356  while (!pq.empty())
1357  {
1358  // second element of pair denotes the node / vertex
1359  const Node<T> *currentNode = pq.top().second;
1360  auto nodeId = currentNode->getId();
1361  if (std::find(doneNode.begin(), doneNode.end(), nodeId) == doneNode.end())
1362  {
1363  auto pair = std::make_pair(parentNode[nodeId], currentNode->getUserId());
1364  result.mst.push_back(pair);
1365  result.mstCost += pq.top().first;
1366  doneNode.push_back(nodeId);
1367  }
1368 
1369  pq.pop();
1370  // for all the reachable vertex from the currently exploring vertex
1371  // we will try to minimize the distance
1372  if (adj.find(currentNode) != adj.end())
1373  {
1374  for (const auto &elem : adj.at(currentNode))
1375  {
1376  // minimizing distances
1377  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1378  {
1379  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
1380  if (
1381  (udw_edge->getWeight() < dist[elem.first]) &&
1382  (std::find(doneNode.begin(), doneNode.end(), elem.first->getId()) == doneNode.end()))
1383  {
1384  dist[elem.first] = udw_edge->getWeight();
1385  parentNode[elem.first->getId()] = currentNode->getUserId();
1386  pq.push(std::make_pair(dist[elem.first], elem.first));
1387  }
1388  }
1389  else
1390  {
1391  // No Weighted Edge
1392  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1393  return result;
1394  }
1395  }
1396  }
1397  }
1398  result.success = true;
1399  return result;
1400  }
1401 
1402  template <typename T>
1403  const MstResult Graph<T>::boruvka() const
1404  {
1405  MstResult result;
1406  result.success = false;
1407  result.errorMessage = "";
1408  result.mstCost = INF_DOUBLE;
1409  if (!isUndirectedGraph())
1410  {
1411  result.errorMessage = ERR_DIR_GRAPH;
1412  return result;
1413  }
1414  const auto nodeSet = Graph<T>::getNodeSet();
1415  const auto n = nodeSet.size();
1416 
1417  // Use std map for storing n subsets.
1418  std::unordered_map<unsigned long long, Subset> subsets;
1419 
1420  // Initially there are n different trees.
1421  // Finally there will be one tree that will be MST
1422  int numTrees = n;
1423 
1424  // check if all edges are weighted and store the weights
1425  // in a map whose keys are the edge ids and values are the edge weights
1426  const auto edgeSet = Graph<T>::getEdgeSet();
1427  std::unordered_map<unsigned long long, double> edgeWeight;
1428  for (const auto &edge : edgeSet)
1429  {
1430  if (edge->isWeighted().has_value() && edge->isWeighted().value())
1431  edgeWeight[edge->getId()] = (dynamic_cast<const Weighted *>(edge))->getWeight();
1432  else
1433  {
1434  // No Weighted Edge
1435  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1436  return result;
1437  }
1438  }
1439 
1440  for (const auto &node : nodeSet)
1441  {
1442  Subset set{node->getId(), 0};
1443  subsets[node->getId()] = set;
1444  }
1445 
1446  result.mstCost = 0; // we will store the cost here
1447  // exit when only 1 tree i.e. mst
1448  while (numTrees > 1)
1449  {
1450  // Everytime initialize cheapest map
1451  // It stores index of the cheapest edge of subset.
1452  std::unordered_map<unsigned long long, unsigned long long> cheapest;
1453  for (const auto &node : nodeSet)
1454  cheapest[node->getId()] = INT_MAX;
1455 
1456  // Traverse through all edges and update
1457  // cheapest of every component
1458  for (const auto &edge : edgeSet)
1459  {
1460  auto elem = edge->getNodePair();
1461  auto edgeId = edge->getId();
1462  // Find sets of two corners of current edge
1463  auto set1 = Graph<T>::setFind(&subsets, elem.first->getId());
1464  auto set2 = Graph<T>::setFind(&subsets, elem.second->getId());
1465 
1466  // If two corners of current edge belong to
1467  // same set, ignore current edge
1468  if (set1 == set2)
1469  continue;
1470 
1471  // Else check if current edge is closer to previous
1472  // cheapest edges of set1 and set2
1473  if (cheapest[set1] == INT_MAX ||
1474  edgeWeight[cheapest[set1]] > edgeWeight[edgeId])
1475  cheapest[set1] = edgeId;
1476 
1477  if (cheapest[set2] == INT_MAX ||
1478  edgeWeight[cheapest[set2]] > edgeWeight[edgeId])
1479  cheapest[set2] = edgeId;
1480  }
1481 
1482  // iterate over all the vertices and add picked
1483  // cheapest edges to MST
1484  for (const auto &[nodeId, edgeId] : cheapest)
1485  {
1486  // Check if cheapest for current set exists
1487  if (edgeId != INT_MAX)
1488  {
1489  auto cheapestNode = Graph<T>::getEdge(edgeId).value()->getNodePair();
1490  auto set1 = Graph<T>::setFind(&subsets, cheapestNode.first->getId());
1491  auto set2 = Graph<T>::setFind(&subsets, cheapestNode.second->getId());
1492  if (set1 == set2)
1493  continue;
1494  result.mstCost += edgeWeight[edgeId];
1495  auto newEdgeMST = std::make_pair(cheapestNode.first->getUserId(), cheapestNode.second->getUserId());
1496  result.mst.push_back(newEdgeMST);
1497  // take union of set1 and set2 and decrease number of trees
1498  Graph<T>::setUnion(&subsets, set1, set2);
1499  numTrees--;
1500  }
1501  }
1502  }
1503  result.success = true;
1504  return result;
1505  }
1506 
1507  template <typename T>
1508  const MstResult Graph<T>::kruskal() const
1509  {
1510  MstResult result;
1511  result.success = false;
1512  result.errorMessage = "";
1513  result.mstCost = INF_DOUBLE;
1514  if (!isUndirectedGraph())
1515  {
1516  result.errorMessage = ERR_DIR_GRAPH;
1517  return result;
1518  }
1519  auto nodeSet = Graph<T>::getNodeSet();
1520  auto n = nodeSet.size();
1521 
1522  // check if all edges are weighted and store the weights
1523  // in a map whose keys are the edge ids and values are the edge weights
1524  auto edgeSet = Graph<T>::getEdgeSet();
1525  std::priority_queue<std::pair<double, const Edge<T> *>, std::vector<std::pair<double, const Edge<T> *>>,
1526  std::greater<std::pair<double, const Edge<T> *>>>
1527  sortedEdges;
1528  for (const auto &edge : edgeSet)
1529  {
1530  if (edge->isWeighted().has_value() && edge->isWeighted().value())
1531  {
1532  auto weight = (dynamic_cast<const Weighted *>(edge))->getWeight();
1533  sortedEdges.push(std::make_pair(weight, edge));
1534  }
1535  else
1536  {
1537  // No Weighted Edge
1538  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1539  return result;
1540  }
1541  }
1542 
1543  std::unordered_map<unsigned long long, Subset> subset;
1544 
1545  for (const auto &node : nodeSet)
1546  {
1547  Subset set{node->getId(), 0};
1548  subset[node->getId()] = set;
1549  }
1550  result.mstCost = 0;
1551  while ((!sortedEdges.empty()) && (result.mst.size() < n))
1552  {
1553  auto [edgeWeight, cheapestEdge] = sortedEdges.top();
1554  sortedEdges.pop();
1555  auto &[first, second] = cheapestEdge->getNodePair();
1556  auto set1 = Graph<T>::setFind(&subset, first->getId());
1557  auto set2 = Graph<T>::setFind(&subset, second->getId());
1558  if (set1 != set2)
1559  {
1560  result.mst.push_back(std::make_pair(first->getUserId(), second->getUserId()));
1561  result.mstCost += edgeWeight;
1562  }
1563  Graph<T>::setUnion(&subset, set1, set2);
1564  }
1565  result.success = true;
1566  return result;
1567  }
1568 
1569  template <typename T>
1570  const std::vector<Node<T>> Graph<T>::breadth_first_search(const Node<T> &start) const
1571  {
1572  // vector to keep track of visited nodes
1573  std::vector<Node<T>> visited;
1574  auto &nodeSet = Graph<T>::getNodeSet();
1575  // check is exist node in the graph
1576  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1577  {
1578  return visited;
1579  }
1580  const AdjacencyMatrix<T> &adj = Graph<T>::getAdjMatrix();
1581  // queue that stores vertices that need to be further explored
1582  std::queue<const Node<T> *> tracker;
1583 
1584  // mark the starting node as visited
1585  visited.push_back(start);
1586  tracker.push(&start);
1587  while (!tracker.empty())
1588  {
1589  const Node<T> *node = tracker.front();
1590  tracker.pop();
1591  if (adj.find(node) != adj.end())
1592  {
1593  for (const auto &elem : adj.at(node))
1594  {
1595  // if the node is not visited then mark it as visited
1596  // and push it to the queue
1597  if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1598  {
1599  visited.push_back(*(elem.first));
1600  tracker.push(elem.first);
1601  }
1602  }
1603  }
1604  }
1605 
1606  return visited;
1607  }
1608 
1609  template <typename T>
1610  const std::vector<Node<T>> Graph<T>::depth_first_search(const Node<T> &start) const
1611  {
1612  // vector to keep track of visited nodes
1613  std::vector<Node<T>> visited;
1614  auto nodeSet = Graph<T>::getNodeSet();
1615  // check is exist node in the graph
1616  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1617  {
1618  return visited;
1619  }
1620  const AdjacencyMatrix<T> adj = Graph<T>::getAdjMatrix();
1621  std::function<void(const AdjacencyMatrix<T> &, const Node<T> &, std::vector<Node<T>> &)> explore;
1622  explore = [&explore](const AdjacencyMatrix<T> &adj, const Node<T> &node, std::vector<Node<T>> &visited) -> void
1623  {
1624  visited.push_back(node);
1625  if (adj.find(&node) != adj.end())
1626  {
1627  for (const auto &x : adj.at(&node))
1628  {
1629  if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1630  {
1631  explore(adj, *(x.first), visited);
1632  }
1633  }
1634  }
1635  };
1636  explore(adj, start, visited);
1637 
1638  return visited;
1639  }
1640 
1641  template <typename T>
1642  bool Graph<T>::isCyclicDirectedGraphDFS() const
1643  {
1644  if (!isDirectedGraph())
1645  {
1646  return false;
1647  }
1648  enum nodeStates : uint8_t
1649  {
1650  not_visited,
1651  in_stack,
1652  visited
1653  };
1654  auto nodeSet = Graph<T>::getNodeSet();
1655  auto adjMatrix = Graph<T>::getAdjMatrix();
1656 
1657  /* State of the node.
1658  *
1659  * It is a vector of "nodeStates" which represents the state node is in.
1660  * It can take only 3 values: "not_visited", "in_stack", and "visited".
1661  *
1662  * Initially, all nodes are in "not_visited" state.
1663  */
1664  std::unordered_map<unsigned long long, nodeStates> state;
1665  for (const auto &node : nodeSet)
1666  {
1667  state[node->getId()] = not_visited;
1668  }
1669  int stateCounter = 0;
1670 
1671  // Start visiting each node.
1672  for (const auto &node : nodeSet)
1673  {
1674  // If a node is not visited, only then check for presence of cycle.
1675  // There is no need to check for presence of cycle for a visited
1676  // node as it has already been checked for presence of cycle.
1677  if (state[node->getId()] == not_visited)
1678  {
1679  // Check for cycle.
1680  std::function<bool(AdjacencyMatrix<T> &, std::unordered_map<unsigned long long, nodeStates> &, const Node<T> *)> isCyclicDFSHelper;
1681  isCyclicDFSHelper = [this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::unordered_map<unsigned long long, nodeStates> &states, const Node<T> *node)
1682  {
1683  // Add node "in_stack" state.
1684  states[node->getId()] = in_stack;
1685 
1686  // If the node has children, then recursively visit all children of the
1687  // node.
1688  auto const it = adjMatrix.find(node);
1689  if (it != adjMatrix.end())
1690  {
1691  for (const auto &child : it->second)
1692  {
1693  // If state of child node is "not_visited", evaluate that child
1694  // for presence of cycle.
1695  auto state_of_child = states.at((std::get<0>(child))->getId());
1696  if (state_of_child == not_visited)
1697  {
1698  if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1699  {
1700  return true;
1701  }
1702  }
1703  else if (state_of_child == in_stack)
1704  {
1705  // If child node was "in_stack", then that means that there
1706  // is a cycle in the graph. Return true for presence of the
1707  // cycle.
1708  return true;
1709  }
1710  }
1711  }
1712 
1713  // Current node has been evaluated for the presence of cycle and had no
1714  // cycle. Mark current node as "visited".
1715  states[node->getId()] = visited;
1716  // Return that current node didn't result in any cycles.
1717  return false;
1718  };
1719  if (isCyclicDFSHelper(adjMatrix, state, node))
1720  {
1721  return true;
1722  }
1723  }
1724  }
1725 
1726  // All nodes have been safely traversed, that means there is no cycle in
1727  // the graph. Return false.
1728  return false;
1729  }
1730 
1731  template <typename T>
1732  bool Graph<T>::containsCycle(const T_EdgeSet<T> *edgeSet) const
1733  {
1734  std::unordered_map<unsigned long long, Subset> subset;
1735  // initialize the subset parent and rank values
1736  for (const auto &edge : *edgeSet)
1737  {
1738  auto &[first, second] = edge->getNodePair();
1739  std::vector<unsigned long long> nodeId(2);
1740  nodeId.push_back(first->getId());
1741  nodeId.push_back(second->getId());
1742  for (const auto &id : nodeId)
1743  {
1744  auto nodeExists = [id](const auto &it)
1745  { return (id == (it.second).parent); };
1746 
1747  if (std::find_if(subset.begin(), subset.end(), nodeExists) == subset.end())
1748  {
1749  Subset set;
1750  set.parent = id;
1751  set.rank = 0;
1752  subset[id] = set;
1753  }
1754  }
1755  }
1756  return Graph<T>::containsCycle(edgeSet, &subset);
1757  }
1758 
1759  template <typename T>
1760  bool Graph<T>::containsCycle(const T_EdgeSet<T> *edgeSet, std::unordered_map<unsigned long long, Subset> *subset) const
1761  {
1762  for (const auto &edge : *edgeSet)
1763  {
1764  auto &[first, second] = edge->getNodePair();
1765  auto set1 = Graph<T>::setFind(subset, first->getId());
1766  auto set2 = Graph<T>::setFind(subset, second->getId());
1767  if (set1 == set2)
1768  return true;
1769  Graph<T>::setUnion(subset, set1, set2);
1770  }
1771  return false;
1772  }
1773 
1774  template <typename T>
1775  bool Graph<T>::isCyclicDirectedGraphBFS() const
1776  {
1777  if (!isDirectedGraph())
1778  {
1779  return false;
1780  }
1781  auto adjMatrix = Graph<T>::getAdjMatrix();
1782  auto nodeSet = Graph<T>::getNodeSet();
1783 
1784  std::unordered_map<unsigned long, unsigned int> indegree;
1785  for (const auto &node : nodeSet)
1786  {
1787  indegree[node->getId()] = 0;
1788  }
1789  // Calculate the indegree i.e. the number of incident edges to the node.
1790  for (auto const &list : adjMatrix)
1791  {
1792  auto children = list.second;
1793  for (auto const &child : children)
1794  {
1795  indegree[std::get<0>(child)->getId()]++;
1796  }
1797  }
1798 
1799  std::queue<const Node<T> *> can_be_solved;
1800  for (const auto &node : nodeSet)
1801  {
1802  // If a node doesn't have any input edges, then that node will
1803  // definately not result in a cycle and can be visited safely.
1804  if (!indegree[node->getId()])
1805  {
1806  can_be_solved.emplace(&(*node));
1807  }
1808  }
1809 
1810  // Vertices that need to be traversed.
1811  auto remain = Graph<T>::getNodeSet().size();
1812  // While there are safe nodes that we can visit.
1813  while (!can_be_solved.empty())
1814  {
1815  auto solved = can_be_solved.front();
1816  // Visit the node.
1817  can_be_solved.pop();
1818  // Decrease number of nodes that need to be traversed.
1819  remain--;
1820 
1821  // Visit all the children of the visited node.
1822  auto it = adjMatrix.find(solved);
1823  if (it != adjMatrix.end())
1824  {
1825  for (const auto &child : it->second)
1826  {
1827  // Check if we can visited the node safely.
1828  if (--indegree[std::get<0>(child)->getId()] == 0)
1829  {
1830  // if node can be visited safely, then add that node to
1831  // the visit queue.
1832  can_be_solved.emplace(std::get<0>(child));
1833  }
1834  }
1835  }
1836  }
1837 
1838  // If there are still nodes that we can't visit, then it means that
1839  // there is a cycle and return true, else return false.
1840  return !(remain == 0);
1841  }
1842 
1843  template <typename T>
1844  bool Graph<T>::isDirectedGraph() const
1845  {
1846  auto edgeSet = Graph<T>::getEdgeSet();
1847  for (const auto &edge : edgeSet)
1848  {
1849  if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1850  {
1851  // Found Undirected Edge
1852  return false;
1853  }
1854  }
1855  // No Undirected Edge
1856  return true;
1857  }
1858 
1859  template <typename T>
1860  bool Graph<T>::isUndirectedGraph() const
1861  {
1862  auto edgeSet = Graph<T>::getEdgeSet();
1863  for (const auto &edge : edgeSet)
1864  {
1865  if ((edge->isDirected().has_value() && edge->isDirected().value()))
1866  {
1867  // Found Directed Edge
1868  return false;
1869  }
1870  }
1871  // No Directed Edge
1872  return true;
1873  }
1874 
1875  template <typename T>
1876  bool Graph<T>::isConnectedGraph() const
1877  {
1878  if (!isUndirectedGraph())
1879  {
1880  return false;
1881  }
1882  else
1883  {
1884  auto nodeSet = getNodeSet();
1885  auto adjMatrix = getAdjMatrix();
1886  // created visited map
1887  std::unordered_map<unsigned long, bool> visited;
1888  for (const auto &node : nodeSet)
1889  {
1890  visited[node->getId()] = false;
1891  }
1892  std::function<void(const Node<T> *)> dfs_helper = [this, &adjMatrix, &visited, &dfs_helper](const Node<T> *source)
1893  {
1894  // mark the vertex visited
1895  visited[source->getId()] = true;
1896 
1897  // travel the neighbors
1898  for (int i = 0; i < adjMatrix[source].size(); i++)
1899  {
1900  const Node<T> *neighbor = adjMatrix[source].at(i).first;
1901  if (visited[neighbor->getId()] == false)
1902  {
1903  // make recursive call from neighbor
1904  dfs_helper(neighbor);
1905  }
1906  }
1907  };
1908  // call dfs_helper for the first node
1909  dfs_helper(*(nodeSet.begin()));
1910 
1911  // check if all the nodes are visited
1912  for (const auto &node : nodeSet)
1913  {
1914  if (visited[node->getId()] == false)
1915  {
1916  return false;
1917  }
1918  }
1919  return true;
1920  }
1921  }
1922 
1923  template <typename T>
1924  bool Graph<T>::isStronglyConnectedGraph() const
1925  {
1926  if (!isDirectedGraph())
1927  {
1928  return false;
1929  }
1930  else
1931  {
1932  auto nodeSet = getNodeSet();
1933  auto adjMatrix = getAdjMatrix();
1934  for (const auto &start_node : nodeSet)
1935  {
1936  // created visited map
1937  std::unordered_map<unsigned long, bool> visited;
1938  for (const auto &node : nodeSet)
1939  {
1940  visited[node->getId()] = false;
1941  }
1942  std::function<void(const Node<T> *)> dfs_helper = [this, &adjMatrix, &visited, &dfs_helper](const Node<T> *source)
1943  {
1944  // mark the vertex visited
1945  visited[source->getId()] = true;
1946 
1947  // travel the neighbors
1948  for (int i = 0; i < adjMatrix[source].size(); i++)
1949  {
1950  const Node<T> *neighbor = adjMatrix[source].at(i).first;
1951  if (visited[neighbor->getId()] == false)
1952  {
1953  // make recursive call from neighbor
1954  dfs_helper(neighbor);
1955  }
1956  }
1957  };
1958  // call dfs_helper for the first node
1959  dfs_helper(start_node);
1960 
1961  // check if all the nodes are visited
1962  for (const auto &node : nodeSet)
1963  {
1964  if (visited[node->getId()] == false)
1965  {
1966  return false;
1967  }
1968  }
1969  }
1970  return true;
1971  }
1972  }
1973 
1974  template <typename T>
1975  std::vector<std::vector<Node<T>>> Graph<T>::kosaraju() const
1976  {
1977  std::vector<std::vector<Node<T>>> connectedComps;
1978 
1979  if (!isDirectedGraph())
1980  {
1981  return connectedComps;//empty vector since for undirected graph strongly connected components do not exist
1982  }
1983  else
1984  {
1985  auto nodeSet = getNodeSet();
1986  auto adjMatrix = getAdjMatrix();
1987  // created visited map
1988  std::unordered_map<unsigned long, bool> visited;
1989  for (const auto &node : nodeSet)
1990  {
1991  visited[node->getId()] = false;
1992  }
1993 
1994  std::stack<const Node<T> *> st;
1995  std::function<void(const Node<T> *)> dfs_helper = [this, &adjMatrix, &visited, &dfs_helper, &st](const Node<T> *source)
1996  {
1997  // mark the vertex visited
1998  visited[source->getId()] = true;
1999 
2000  // travel the neighbors
2001  for (int i = 0; i < adjMatrix[source].size(); i++)
2002  {
2003  const Node<T> *neighbor = adjMatrix[source].at(i).first;
2004  if (visited[neighbor->getId()] == false)
2005  {
2006  // make recursive call from neighbor
2007  dfs_helper(neighbor);
2008  }
2009  }
2010 
2011  st.push(source);
2012  };
2013 
2014  for (const auto &node : nodeSet)
2015  {
2016  if (visited[node->getId()] == false)
2017  {
2018  dfs_helper(node);
2019  }
2020  }
2021 
2022  //construct the transpose of the given graph
2023  AdjacencyMatrix<T> rev;
2024  auto addElementToAdjMatrix = [&rev](const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge){
2025  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
2026  rev[nodeFrom].push_back(std::move(elem));
2027  };
2028  for (const auto &edgeSetIt : edgeSet)
2029  {
2030  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(edgeSetIt);
2031  //Add the reverse edge to the reverse adjacency matrix
2032  addElementToAdjMatrix(&(d_edge->getTo()), &(d_edge->getFrom()), d_edge);
2033  }
2034 
2035  visited.clear();
2036 
2037  std::function<void(const Node<T> *, std::vector<Node<T>> &)> dfs_helper1 = [this, &rev, &visited, &dfs_helper1](const Node<T> *source, std::vector<Node<T>> &comp)
2038  {
2039  // mark the vertex visited
2040  visited[source->getId()] = true;
2041  //Add the current vertex to the strongly connected component
2042  comp.push_back(*source);
2043 
2044  // travel the neighbors
2045  for (int i = 0; i < rev[source].size(); i++)
2046  {
2047  const Node<T> *neighbor = rev[source].at(i).first;
2048  if (visited[neighbor->getId()] == false)
2049  {
2050  // make recursive call from neighbor
2051  dfs_helper1(neighbor, comp);
2052  }
2053  }
2054  };
2055 
2056  while(st.size()!=0){
2057  auto rem = st.top();
2058  st.pop();
2059  if(visited[rem->getId()] == false){
2060  std::vector<Node<T>> comp;
2061  dfs_helper1(rem, comp);
2062  connectedComps.push_back(comp);
2063  }
2064  }
2065 
2066  return connectedComps;
2067  }
2068  }
2069 
2070  template <typename T>
2071  const DialResult Graph<T>::dial(const Node<T> &source, int maxWeight) const
2072  {
2073  DialResult result;
2074  result.success = false;
2075 
2076  auto adj = Graph<T>::getAdjMatrix();
2077  auto nodeSet = Graph<T>::getNodeSet();
2078 
2079  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
2080  {
2081  // check if source node exist in the graph
2082  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
2083  return result;
2084  }
2085  /* With each distance, iterator to that vertex in
2086  its bucket is stored so that vertex can be deleted
2087  in O(1) at time of updation. So
2088  dist[i].first = distance of ith vertex from src vertex
2089  dits[i].second = vertex i in bucket number */
2090  unsigned int V = nodeSet.size();
2091  std::unordered_map<const Node<T> *, std::pair<long, const Node<T> *>> dist;
2092 
2093  // Initialize all distances as infinite (INF)
2094  for (const auto &node : nodeSet)
2095  {
2096  dist[&(*node)].first = std::numeric_limits<long>::max();
2097  }
2098 
2099  // Create buckets B[].
2100  // B[i] keep vertex of distance label i
2101  std::deque<const Node<T> *> B[maxWeight * V + 1];
2102 
2103  B[0].push_back(&source);
2104  dist[&source].first = 0;
2105 
2106  int idx = 0;
2107  while (1)
2108  {
2109  // Go sequentially through buckets till one non-empty
2110  // bucket is found
2111  while (B[idx].size() == 0 && idx < maxWeight * V)
2112  {
2113  idx++;
2114  }
2115 
2116  // If all buckets are empty, we are done.
2117  if (idx == maxWeight * V)
2118  {
2119  break;
2120  }
2121 
2122  // Take top vertex from bucket and pop it
2123  auto u = B[idx].front();
2124  B[idx].pop_front();
2125 
2126  // Process all adjacents of extracted vertex 'u' and
2127  // update their distanced if required.
2128  for (const auto &i : adj[u])
2129  {
2130  auto v = i.first;
2131  int weight = 0;
2132  if (i.second->isWeighted().has_value() && i.second->isWeighted().value())
2133  {
2134  if (i.second->isDirected().has_value() && i.second->isDirected().value())
2135  {
2136  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(i.second);
2137  weight = dw_edge->getWeight();
2138  }
2139  else if (i.second->isDirected().has_value() && !i.second->isDirected().value())
2140  {
2141  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(i.second);
2142  weight = udw_edge->getWeight();
2143  }
2144  else
2145  {
2146  // ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
2147  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
2148  return result;
2149  }
2150  }
2151  else
2152  {
2153  // No Weighted Edge
2154  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
2155  return result;
2156  }
2157  auto u_i = std::find_if(dist.begin(), dist.end(), [u](std::pair<const Node<T> *, std::pair<long, const Node<T> *>> const &it)
2158  { return (*u == *(it.first)); });
2159 
2160  auto v_i = std::find_if(dist.begin(), dist.end(), [v](std::pair<const Node<T> *, std::pair<long, const Node<T> *>> const &it)
2161  { return (*v == *(it.first)); });
2162  long du = u_i->second.first;
2163  long dv = v_i->second.first;
2164 
2165  // If there is shorted path to v through u.
2166  if (dv > du + weight)
2167  {
2168  // If dv is not INF then it must be in B[dv]
2169  // bucket, so erase its entry using iterator
2170  // in O(1)
2171  if (dv != std::numeric_limits<long>::max())
2172  {
2173  auto findIter = std::find(B[dv].begin(), B[dv].end(), dist[v].second);
2174  B[dv].erase(findIter);
2175  }
2176 
2177  // updating the distance
2178  dist[v].first = du + weight;
2179  dv = dist[v].first;
2180 
2181  // pushing vertex v into updated distance's bucket
2182  B[dv].push_front(v);
2183 
2184  // storing updated iterator in dist[v].second
2185  dist[v].second = *(B[dv].begin());
2186  }
2187  }
2188  }
2189  for (const auto &dist_i : dist)
2190  {
2191  result.minDistanceMap[dist_i.first->getId()] = dist_i.second.first;
2192  }
2193  result.success = true;
2194 
2195  return result;
2196  }
2197 
2198  template <typename T>
2199  double Graph<T>::fordFulkersonMaxFlow(const Node<T> &source, const Node<T> &target) const
2200  {
2201  if (!isDirectedGraph())
2202  {
2203  return -1;
2204  }
2205  double maxFlow = 0;
2206  std::unordered_map<const Node<T> *, const Node<T> *> parent;
2207  std::map<const Node<T> *, std::map<const Node<T> *, double>> weightMap;
2208  // build weight map
2209  auto edgeSet = this->getEdgeSet();
2210  for (const auto &edge : edgeSet)
2211  {
2212  // The Edge are all Directed at this point because is checked at the start
2213  if (edge->isWeighted().value_or(false))
2214  {
2215  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(edge);
2216  weightMap[edge->getNodePair().first][edge->getNodePair().second] = dw_edge->getWeight();
2217  }
2218  else
2219  {
2220  weightMap[edge->getNodePair().first][edge->getNodePair().second] = 0; // No Weighted Edge are assumed to be 0 weigthed
2221  }
2222  }
2223 
2224  auto bfs_helper = [this, &source, &target, &parent, &weightMap]() -> bool
2225  {
2226  std::unordered_map<const Node<T> *, bool> visited;
2227  std::queue<const Node<T> *> queue;
2228  queue.push(&source);
2229  visited[&source] = true;
2230  parent[&source] = nullptr;
2231  while (!queue.empty())
2232  {
2233  auto u = queue.front();
2234  queue.pop();
2235  for (auto &v : weightMap[u])
2236  {
2237  if (!visited[v.first] && v.second > 0)
2238  {
2239  queue.push(v.first);
2240  visited[v.first] = true;
2241  parent[v.first] = u;
2242  }
2243  }
2244  }
2245 
2246  return (visited[&target]);
2247  };
2248  // Updating the residual values of edges
2249  while (bfs_helper())
2250  {
2251  double pathFlow = std::numeric_limits<double>::max();
2252  for (auto v = &target; v != &source; v = parent[v])
2253  {
2254  auto u = parent[v];
2255  pathFlow = std::min(pathFlow, weightMap[u][v]);
2256  }
2257  for (auto v = &target; v != &source; v = parent[v])
2258  {
2259  auto u = parent[v];
2260  weightMap[u][v] -= pathFlow;
2261  weightMap[v][u] += pathFlow;
2262  }
2263  // Adding the path flows
2264  maxFlow += pathFlow;
2265  }
2266 
2267  return maxFlow;
2268  }
2269 
2270  template <typename T>
2271  const std::vector<Node<T>> Graph<T>::graph_slicing(const Node<T> &start) const
2272  {
2273  std::vector<Node<T>> result;
2274 
2275  auto nodeSet = Graph<T>::getNodeSet();
2276  // check if start node in the graph
2277  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
2278  {
2279  return result;
2280  }
2281  std::vector<Node<T>> C = Graph<T>::depth_first_search(start);
2282  std::deque<const Node<T> *> C1; // complement of C i.e. nodeSet - C
2283  for (auto const &node : nodeSet)
2284  {
2285  // from the set of all nodes, remove nodes that exist in C
2286  if (std::find_if(C.begin(), C.end(), [node](const Node<T> nodeC)
2287  { return (*node == nodeC); }) == C.end())
2288  C1.push_back(node);
2289  }
2290 
2291  // For all nodes in C', apply DFS
2292  // and get the list of reachable nodes and store in M
2293  std::vector<Node<T>> M;
2294  for (auto const &node : C1)
2295  {
2296  std::vector<Node<T>> reachableNodes = Graph<T>::depth_first_search(*node);
2297  M.insert(M.end(), reachableNodes.begin(), reachableNodes.end());
2298  }
2299  // removes nodes from C that are reachable from M.
2300  for (const auto &nodeC : C)
2301  {
2302  if (std::find_if(M.begin(), M.end(), [nodeC](const Node<T> nodeM)
2303  { return (nodeM == nodeC); }) == M.end())
2304  result.push_back(nodeC);
2305  }
2306  return result;
2307  }
2308 
2309  template <typename T>
2310  int Graph<T>::writeToFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
2311  {
2312  int result = 0;
2313  result = writeToStandardFile(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight, format);
2314  if (result == 0 && compress)
2315  {
2316  auto _compress = [this, &workingDir, &OFileName, &writeNodeFeat, &writeEdgeWeight](const std::string &extension)
2317  {
2318  std::string completePathToFileGraph = workingDir + "/" + OFileName + extension;
2319  std::string completePathToFileGraphCompressed = workingDir + "/" + OFileName + extension + ".gz";
2320  int _result = compressFile(completePathToFileGraph, completePathToFileGraphCompressed);
2321  if (_result == 0)
2322  {
2323  _result = remove(completePathToFileGraph.c_str());
2324  }
2325  if (_result == 0)
2326  {
2327  if (writeNodeFeat)
2328  {
2329  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat" + extension;
2330  std::string completePathToFileNodeFeatCompressed = workingDir + "/" + OFileName + "_NodeFeat" + extension + ".gz";
2331  _result = compressFile(completePathToFileNodeFeat, completePathToFileNodeFeatCompressed);
2332  if (_result == 0)
2333  {
2334  _result = remove(completePathToFileNodeFeat.c_str());
2335  }
2336  }
2337  }
2338  if (_result == 0)
2339  {
2340  if (writeEdgeWeight)
2341  {
2342  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight" + extension;
2343  std::string completePathToFileEdgeWeightCompressed = workingDir + "/" + OFileName + "_EdgeWeight" + extension + ".gz";
2344  _result = compressFile(completePathToFileEdgeWeight, completePathToFileEdgeWeightCompressed);
2345  if (_result == 0)
2346  {
2347  _result = remove(completePathToFileEdgeWeight.c_str());
2348  }
2349  }
2350  }
2351  return _result;
2352  };
2353  if (format == InputOutputFormat::STANDARD_CSV)
2354  {
2355  auto result = _compress(".csv");
2356  }
2357  else if (format == InputOutputFormat::STANDARD_TSV)
2358  {
2359  auto result = _compress(".tsv");
2360  }
2361  else
2362  {
2363  // OUTPUT FORMAT NOT RECOGNIZED
2364  result = -1;
2365  }
2366  }
2367  return result;
2368  }
2369 
2370  template <typename T>
2371  int Graph<T>::readFromFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
2372  {
2373  int result = 0;
2374  if (compress)
2375  {
2376  auto decompress = [this, &workingDir, &OFileName, &readNodeFeat, &readEdgeWeight](const std::string &extension)
2377  {
2378  std::string completePathToFileGraph = workingDir + "/" + OFileName + extension;
2379  std::string completePathToFileGraphCompressed = workingDir + "/" + OFileName + extension + ".gz";
2380  int _result = decompressFile(completePathToFileGraphCompressed, completePathToFileGraph);
2381  if (_result == 0)
2382  {
2383  if (readNodeFeat)
2384  {
2385  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat" + extension;
2386  std::string completePathToFileNodeFeatCompressed = workingDir + "/" + OFileName + "_NodeFeat" + extension + ".gz";
2387  _result = decompressFile(completePathToFileNodeFeatCompressed, completePathToFileNodeFeat);
2388  }
2389  }
2390  if (_result == 0)
2391  {
2392  if (readEdgeWeight)
2393  {
2394  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight" + extension;
2395  std::string completePathToFileEdgeWeightCompressed = workingDir + "/" + OFileName + "_EdgeWeight" + extension + ".gz";
2396  _result = decompressFile(completePathToFileEdgeWeightCompressed, completePathToFileEdgeWeight);
2397  }
2398  }
2399  return _result;
2400  };
2401  if (format == InputOutputFormat::STANDARD_CSV)
2402  {
2403  result = decompress(".csv");
2404  }
2405  else if (format == InputOutputFormat::STANDARD_TSV)
2406  {
2407  result = decompress(".tsv");
2408  }
2409  else
2410  {
2411  // INPUT FORMAT NOT RECOGNIZED
2412  result = -1;
2413  }
2414  }
2415  if (result == 0)
2416  {
2417  result = readFromStandardFile(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight, format);
2418  }
2419  return result;
2420  }
2421 
2422  template <typename T>
2423  PartitionMap<T> Graph<T>::partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions, double param1, double param2, double param3, unsigned int numberOfthreads) const
2424  {
2425  PartitionMap<T> partitionMap;
2426  PARTITIONING::Globals globals(numberOfPartitions, algorithm, param1, param2, param3, numberOfthreads);
2427  const T_EdgeSet<T> & edgeSet = getEdgeSet();
2428  globals.edgeCardinality = edgeSet.size();
2429  globals.vertexCardinality = this->getNodeSet().size();
2430  PARTITIONING::Partitioner<T> partitioner(&edgeSet, globals);
2431  PARTITIONING::CoordinatedPartitionState<T> partitionState = partitioner.performCoordinatedPartition();
2432  partitionMap = partitionState.getPartitionMap();
2433  return partitionMap;
2434  }
2435 
2436  template <typename T>
2437  std::ostream &operator<<(std::ostream &os, const Graph<T> &graph)
2438  {
2439  os << "Graph:\n";
2440  auto edgeList = graph.getEdgeSet();
2441  auto it = edgeList.begin();
2442  for (it; it != edgeList.end(); ++it)
2443  {
2444  if (!(*it)->isDirected().has_value() && !(*it)->isWeighted().has_value())
2445  {
2446  // Edge Case
2447  os << **it << "\n";
2448  }
2449  else if (((*it)->isDirected().has_value() && (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
2450  {
2451  os << dynamic_cast<const DirectedWeightedEdge<T> &>(*it) << "\n";
2452  }
2453  else if (((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
2454  {
2455  os << dynamic_cast<const DirectedEdge<T> &>(*it) << "\n";
2456  }
2457  else if (!(it->isDirected().has_value() && it->isDirected().value()) && (it->isWeighted().has_value() && it->isWeighted().value()))
2458  {
2459  os << dynamic_cast<const UndirectedWeightedEdge<T> &>(*it) << "\n";
2460  }
2461  else if (!(it->isDirected().has_value() && it->isDirected().value()) && !(it->isWeighted().has_value() && it->isWeighted().value()))
2462  {
2463  os << dynamic_cast<const UndirectedEdge<T> &>(*it) << "\n";
2464  }
2465  else
2466  {
2467  os << *it << "\n";
2468  }
2469  }
2470  return os;
2471  }
2472 
2473  template <typename T>
2474  std::ostream &operator<<(std::ostream &os, const AdjacencyMatrix<T> &adj)
2475  {
2476  os << "Adjacency Matrix:\n";
2477  unsigned long max_column = 0;
2478  for (const auto &it : adj)
2479  {
2480  if (it.second.size() > max_column)
2481  {
2482  max_column = it.second.size();
2483  }
2484  }
2485  if (max_column == 0)
2486  {
2487  os << "ERROR in Print\n";
2488  return os;
2489  }
2490  else
2491  {
2492  os << "|--|";
2493  for (int i = 0; i < max_column; ++i)
2494  {
2495  os << "-----|";
2496  }
2497  os << "\n";
2498  for (const auto &it : adj)
2499  {
2500  os << "|N" << it.first->getId() << "|";
2501  for (const auto &it2 : it.second)
2502  {
2503  os << "N" << it2.first->getId() << ",E" << it2.second->getId() << "|";
2504  }
2505  os << "\n|--|";
2506  for (int i = 0; i < max_column; ++i)
2507  {
2508  os << "-----|";
2509  }
2510  os << "\n";
2511  }
2512  }
2513  return os;
2514  }
2515 
2516 } // namespace CXXGRAPH
2517 #endif // __CXXGRAPH_GRAPH_H__
CXXGRAPH::DirectedEdge
Definition: DirectedEdge.hpp:39
CXXGRAPH::DirectedWeightedEdge
Definition: DirectedWeightedEdge.hpp:42
CXXGRAPH::Edge
Definition: Edge.hpp:39
CXXGRAPH::Graph
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:91
CXXGRAPH::Graph::floydWarshall
virtual const FWResult floydWarshall() const
Function runs the floyd-warshall algorithm and returns the shortest distance of all pair of nodes....
Definition: Graph.hpp:1231
CXXGRAPH::Graph::depth_first_search
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:1610
CXXGRAPH::Graph::setFind
virtual unsigned long long setFind(std::unordered_map< unsigned long long, Subset > *, const unsigned long long elem) const
This function finds the subset of given a nodeId Subset is stored in a map where keys are the hash-id...
Definition: Graph.hpp:911
CXXGRAPH::Graph::isUndirectedGraph
virtual bool isUndirectedGraph() const
This function checks if a graph is undirected Note: No Thread Safe.
Definition: Graph.hpp:1860
CXXGRAPH::Graph::isConnectedGraph
virtual bool isConnectedGraph() const
This function checks if the graph is connected or not Applicable for Undirected Graph,...
Definition: Graph.hpp:1876
CXXGRAPH::Graph::prim
virtual const MstResult prim() const
Function runs the prim algorithm and returns the minimum spanning tree if the graph is undirected....
Definition: Graph.hpp:1311
CXXGRAPH::Graph::isStronglyConnectedGraph
virtual bool isStronglyConnectedGraph() const
This function checks if the graph is strongly connected or not Applicable for Directed Graph,...
Definition: Graph.hpp:1924
CXXGRAPH::Graph::eulerianPath
virtual std::vector< Node< T > > eulerianPath() const
This function finds the eulerian path of a directed graph using hierholzers algorithm.
Definition: Graph.hpp:944
CXXGRAPH::Graph::fordFulkersonMaxFlow
virtual double fordFulkersonMaxFlow(const Node< T > &source, const Node< T > &target) const
Function runs the Ford-Fulkerson algorithm for some source node and target node in the graph and retu...
Definition: Graph.hpp:2199
CXXGRAPH::Graph::isCyclicDirectedGraphBFS
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:1775
CXXGRAPH::Graph::containsCycle
virtual bool containsCycle(const T_EdgeSet< T > *) const
This function checks if the given set of edges forms a cycle or not using union-find method.
Definition: Graph.hpp:1732
CXXGRAPH::Graph::kosaraju
virtual std::vector< std::vector< Node< T > > > kosaraju() const
This function performs performs the kosaraju algorthm on the graph to find the strongly connected com...
Definition: Graph.hpp:1975
CXXGRAPH::Graph::writeToFile
virtual int writeToFile(InputOutputFormat format=InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool writeNodeFeat=false, bool writeEdgeWeight=false) const
This function write the graph in an output file Note: No Thread Safe.
Definition: Graph.hpp:2310
CXXGRAPH::Graph::isDirectedGraph
virtual bool isDirectedGraph() const
This function checks if a graph is directed Note: No Thread Safe.
Definition: Graph.hpp:1844
CXXGRAPH::Graph::getEdge
virtual const std::optional< const Edge< T > * > getEdge(unsigned long long edgeId) const
Function that return an Edge with specific ID if Exist in the Graph Note: No Thread Safe.
Definition: Graph.hpp:561
CXXGRAPH::Graph::setUnion
virtual void setUnion(std::unordered_map< unsigned long long, Subset > *, const unsigned long long set1, const unsigned long long elem2) const
This function modifies the original subset array such that it the union of two sets a and b.
Definition: Graph.hpp:924
CXXGRAPH::Graph::dial
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:2071
CXXGRAPH::Graph::partitionGraph
virtual PartitionMap< T > partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions, double param1=0.0, double param2=0.0, double param3=0.0, unsigned int numberOfthreads=std::thread::hardware_concurrency()) const
This function partition a graph in a set of partitions Note: No Thread Safe.
Definition: Graph.hpp:2423
CXXGRAPH::Graph::graph_slicing
virtual const std::vector< Node< T > > graph_slicing(const Node< T > &start) const
This function performs Graph Slicing based on connectivity.
Definition: Graph.hpp:2271
CXXGRAPH::Graph::setEdgeSet
virtual void setEdgeSet(T_EdgeSet< T > &edgeSet)
Function set the Edge Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:489
CXXGRAPH::Graph::getEdgeSet
virtual const T_EdgeSet< T > & getEdgeSet() const
Function that return the Edge set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:483
CXXGRAPH::Graph::dijkstra
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:1007
CXXGRAPH::Graph::boruvka
virtual const MstResult boruvka() const
Function runs the boruvka algorithm and returns the minimum spanning tree & cost if the graph is undi...
Definition: Graph.hpp:1403
CXXGRAPH::Graph::isCyclicDirectedGraphDFS
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:1642
CXXGRAPH::Graph::addEdge
virtual void addEdge(const Edge< T > *edge)
Function add an Edge to the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:506
CXXGRAPH::Graph::readFromFile
virtual int readFromFile(InputOutputFormat format=InputOutputFormat::STANDARD_CSV, const std::string &workingDir=".", const std::string &OFileName="graph", bool compress=false, bool readNodeFeat=false, bool readEdgeWeight=false)
This function read the graph from an input file Note: No Thread Safe.
Definition: Graph.hpp:2371
CXXGRAPH::Graph::removeEdge
virtual void removeEdge(unsigned long long edgeId)
Function remove an Edge from the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:519
CXXGRAPH::Graph::kruskal
virtual const MstResult kruskal() const
Function runs the kruskal algorithm and returns the minimum spanning tree if the graph is undirected....
Definition: Graph.hpp:1508
CXXGRAPH::Graph::getAdjMatrix
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:976
CXXGRAPH::Graph::bellmanford
virtual const BellmanFordResult bellmanford(const Node< T > &source, const Node< T > &target) const
Function runs the bellman-ford algorithm for some source node and target node in the graph and return...
Definition: Graph.hpp:1123
CXXGRAPH::Graph::breadth_first_search
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:1570
CXXGRAPH::Graph::getNodeSet
virtual const std::set< const Node< T > * > getNodeSet() const
Function that return the Node Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:533
CXXGRAPH::Node
Definition: Node.hpp:38
CXXGRAPH::PARTITIONING::CoordinatedPartitionState
Definition: CoordinatedPartitionState.hpp:41
CXXGRAPH::PARTITIONING::Globals
Definition: Globals.hpp:32
CXXGRAPH::PARTITIONING::Partitioner
Definition: Partitioner.hpp:43
CXXGRAPH::UndirectedEdge
Definition: UndirectedEdge.hpp:39
CXXGRAPH::UndirectedWeightedEdge
Definition: UndirectedWeightedEdge.hpp:43
CXXGRAPH::Weighted
Definition: Weighted.hpp:28
CXXGRAPH::BellmanFordResult_struct
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:79
CXXGRAPH::DialResult_struct
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:130
CXXGRAPH::DijkstraResult_struct
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:70
CXXGRAPH::FWResult_struct
Struct that contains the information about Floyd-Warshall Algorithm results.
Definition: Typedef.hpp:110
CXXGRAPH::MstResult_struct
Struct that contains the information about Prim, Boruvka & Kruskal Algorithm results.
Definition: Typedef.hpp:120
CXXGRAPH::Subset_struct
Struct useful for union-find operations.
Definition: Typedef.hpp:62
CXXGRAPH::csv_whitespace
Definition: Graph.hpp:665
CXXGRAPH::pair_hash
Definition: Typedef.hpp:99
Generated by doxygen 1.9.1