CXXGraph  0.2.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: AGPL v3.0 ***/
18 /***********************************************************/
19 
20 #ifndef __GRAPH_H__
21 #define __GRAPH_H__
22 
23 #pragma once
24 
25 #include <utility>
26 #include <set>
27 #include <map>
28 #include <optional>
29 #include <iostream>
30 #include <limits>
31 #include <list>
32 #include <queue>
33 #include <string>
34 #include <cstring>
35 #include <functional>
36 #include <fstream>
37 #include <limits.h>
38 #include <mutex>
39 #include <set>
40 #include <atomic>
41 #include <thread>
42 #include <cmath>
43 #include "zlib.h"
44 
45 #include "Edge/Weighted.hpp"
46 #include "Node/Node.hpp"
47 #include "Edge/Edge.hpp"
48 #include "Edge/DirectedEdge.hpp"
49 #include "Edge/UndirectedEdge.hpp"
50 #include "Edge/DirectedWeightedEdge.hpp"
51 #include "Edge/UndirectedWeightedEdge.hpp"
52 #include "Utility/ThreadSafe.hpp"
53 #include "Utility/Writer.hpp"
54 #include "Utility/Reader.hpp"
55 #include "Utility/ConstString.hpp"
56 #include "Utility/ConstValue.hpp"
57 #include "Utility/Typedef.hpp"
58 #include "Partitioning/Partition.hpp"
59 #include "Partitioning/PartitionAlgorithm.hpp"
60 #include "Partitioning/Partitioner.hpp"
61 #include "Partitioning/Utility/Globals.hpp"
62 
63 namespace CXXGRAPH
64 {
65  namespace PARTITIONING{
66  template<typename T>
67  class Partition;
68  }
69 
70  template <typename T>
71  std::ostream &operator<<(std::ostream &o, const Graph<T> &graph);
72  template <typename T>
73  std::ostream &operator<<(std::ostream &o, const AdjacencyMatrix<T> &adj);
74 
76  template <typename T>
77  class Graph
78  {
79  private:
80  std::list<const Edge<T> *> edgeSet;
81  void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const;
82  int writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
83  int readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
84  int writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
85  int readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
86  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);
87  int compressFile(const std::string &inputFile, const std::string &outputFile) const;
88  int decompressFile(const std::string &inputFile, const std::string &outputFile) const;
89 
90  public:
91  Graph() = default;
92  Graph(const std::list<const Edge<T> *> &edgeSet);
93  ~Graph() = default;
102  virtual const std::list<const Edge<T> *> &getEdgeSet() const;
111  virtual void setEdgeSet(std::list<const Edge<T> *> &edgeSet);
120  virtual void addEdge(const Edge<T> *edge);
129  virtual void removeEdge(unsigned long edgeId);
138  virtual const std::list<const Node<T> *> getNodeSet() const;
148  virtual const std::optional<const Edge<T> *> getEdge(unsigned long edgeId) const;
154  virtual const AdjacencyMatrix<T> getAdjMatrix() const;
167  virtual const DijkstraResult dijkstra(const Node<T> &source, const Node<T> &target) const;
181  virtual const BellmanFordResult bellmanford(const Node<T> &source, const Node<T> &target) const;
189  virtual const FWResult floydWarshall() const;
196  virtual const PrimResult prim() const;
207  virtual const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const;
218  virtual const std::vector<Node<T>> depth_first_search(const Node<T> &start) const;
219 
228  virtual bool isCyclicDirectedGraphDFS() const;
229 
238  virtual bool isCyclicDirectedGraphBFS() const;
239 
247  virtual bool isDirectedGraph() const;
248 
256  virtual bool isUndirectedGraph() const;
257 
274  virtual const std::vector<Node<T>> graph_slicing(const Node<T> &start) const;
275 
302  virtual const DialResult dial(const Node<T> &source, int maxWeight) const;
303 
317  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;
318 
332  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);
333 
343  virtual PartitionMap<T> partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const;
344 
345  friend std::ostream &operator<<<>(std::ostream &os, const Graph<T> &graph);
346  friend std::ostream &operator<<<>(std::ostream &os, const AdjacencyMatrix<T> &adj);
347  };
348 
349  template <typename T>
350  Graph<T>::Graph(const std::list<const Edge<T> *> &edgeSet)
351  {
352  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
353  {
354  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
355  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
356  {
357  this->edgeSet.push_back(*edgeSetIt);
358  }
359  }
360  }
361 
362  template <typename T>
363  const std::list<const Edge<T> *> &Graph<T>::getEdgeSet() const
364  {
365  return edgeSet;
366  }
367 
368  template <typename T>
369  void Graph<T>::setEdgeSet(std::list<const Edge<T> *> &edgeSet)
370  {
371  this->edgeSet.clear();
372  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
373  {
374  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
375  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
376  {
377  this->edgeSet.push_back(*edgeSetIt);
378  }
379  }
380  }
381 
382  template <typename T>
383  void Graph<T>::addEdge(const Edge<T> *edge)
384  {
385  if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](const Edge<T> *edge_a)
386  { return (*edge == *edge_a); }) == edgeSet.end())
387  {
388  edgeSet.push_back(edge);
389  }
390  }
391 
392  template <typename T>
393  void Graph<T>::removeEdge(unsigned long edgeId)
394  {
395  auto edgeOpt = Graph<T>::getEdge(edgeId);
396  if (edgeOpt.has_value())
397  {
398  edgeSet.erase(std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeOpt](const Edge<T> *edge)
399  { return (*(edgeOpt.value()) == *edge); }));
400  }
401  }
402 
403  template <typename T>
404  const std::list<const Node<T> *> Graph<T>::getNodeSet() const
405  {
406  std::list<const Node<T> *> nodeSet;
407  for (auto edge : edgeSet)
408  {
409  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
410  { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
411  {
412  nodeSet.push_back(edge->getNodePair().first);
413  }
414  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
415  { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
416  {
417  nodeSet.push_back(edge->getNodePair().second);
418  }
419  }
420  return nodeSet;
421  }
422 
423  template <typename T>
424  const std::optional<const Edge<T> *> Graph<T>::getEdge(unsigned long edgeId) const
425  {
426 
427  auto it = edgeSet.begin();
428  for (it; it != edgeSet.end(); ++it)
429  {
430  if ((*it)->getId() == edgeId)
431  {
432  return *it;
433  }
434  }
435 
436  return std::nullopt;
437  }
438 
439  template <typename T>
440  void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const
441  {
442  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
443  adjMatrix[nodeFrom].push_back(elem);
444 
445  //adjMatrix[nodeFrom.getId()].push_back(std::make_pair<const Node<T>,const Edge<T>>(nodeTo, edge));
446  }
447 
448  template <typename T>
449  int Graph<T>::writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
450  {
451  std::ofstream ofileGraph;
452  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
453  ofileGraph.open(completePathToFileGraph);
454  if (!ofileGraph.is_open())
455  {
456  // ERROR File Not Open
457  return -1;
458  }
459  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
460  { ofileGraph << e->getId() << "," << e->getNodePair().first->getId() << "," << e->getNodePair().second->getId() << "," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
461  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
462  ofileGraph.close();
463 
464  if (writeNodeFeat)
465  {
466  std::ofstream ofileNodeFeat;
467  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
468  ".csv";
469  ofileNodeFeat.open(completePathToFileNodeFeat);
470  if (!ofileNodeFeat.is_open())
471  {
472  // ERROR File Not Open
473  return -1;
474  }
475  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
476  { ofileNodeFeat << node->getId() << "," << node->getData() << std::endl; };
477  auto nodeSet = getNodeSet();
478  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
479  ofileNodeFeat.close();
480  }
481 
482  if (writeEdgeWeight)
483  {
484  std::ofstream ofileEdgeWeight;
485  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
486  ".csv";
487  ofileEdgeWeight.open(completePathToFileEdgeWeight);
488  if (!ofileEdgeWeight.is_open())
489  {
490  // ERROR File Not Open
491  return -1;
492  }
493  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
494  { 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; };
495 
496  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
497  ofileEdgeWeight.close();
498  }
499  return 0;
500  }
501 
502  template <typename T>
503  int Graph<T>::readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
504  {
505  std::ifstream ifileGraph;
506  std::ifstream ifileNodeFeat;
507  std::ifstream ifileEdgeWeight;
508  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
509  std::map<unsigned long, bool> edgeDirectedMap;
510  std::map<unsigned long, T> nodeFeatMap;
511  std::map<unsigned long, double> edgeWeightMap;
512  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
513  ifileGraph.open(completePathToFileGraph);
514  if (!ifileGraph.is_open())
515  {
516  // ERROR File Not Open
517  return -1;
518  }
519  char comma;
520  for (;;)
521  { /* loop continually */
522  unsigned long edgeId;
523  unsigned long nodeId1;
524  unsigned long nodeId2;
525  bool directed;
526  ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
527  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
528  edgeDirectedMap[edgeId] = directed;
529  if (ifileGraph.fail() || ifileGraph.eof())
530  break;
531  ifileGraph.ignore(128, '\n');
532  }
533  ifileGraph.close();
534 
535  if (readNodeFeat)
536  {
537  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
538  ".csv";
539  ifileNodeFeat.open(completePathToFileNodeFeat);
540  if (!ifileNodeFeat.is_open())
541  {
542  // ERROR File Not Open
543  return -1;
544  }
545  for (;;)
546  { /* loop continually */
547  unsigned long nodeId;
548  T nodeFeat;
549  ifileNodeFeat >> nodeId >> comma >> nodeFeat;
550  nodeFeatMap[nodeId] = nodeFeat;
551  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
552  break;
553  ifileNodeFeat.ignore(128, '\n');
554  }
555  ifileNodeFeat.close();
556  }
557 
558  if (readEdgeWeight)
559  {
560  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
561  ".csv";
562  ifileEdgeWeight.open(completePathToFileEdgeWeight);
563  if (!ifileEdgeWeight.is_open())
564  {
565  // ERROR File Not Open
566  return -1;
567  }
568  for (;;)
569  { /* loop continually */
570  unsigned long edgeId;
571  double weight;
572  bool weighted;
573  ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
574  if (weighted)
575  {
576  edgeWeightMap[edgeId] = weight;
577  }
578  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
579  break;
580  ifileEdgeWeight.ignore(128, '\n');
581  }
582  ifileEdgeWeight.close();
583  }
584  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
585  return 0;
586  }
587 
588  template <typename T>
589  int Graph<T>::writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
590  {
591  std::ofstream ofileGraph;
592  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
593  ofileGraph.open(completePathToFileGraph);
594  if (!ofileGraph.is_open())
595  {
596  // ERROR File Not Open
597  return -1;
598  }
599  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
600  { 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; };
601  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
602  ofileGraph.close();
603 
604  if (writeNodeFeat)
605  {
606  std::ofstream ofileNodeFeat;
607  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
608  ".tsv";
609  ofileNodeFeat.open(completePathToFileNodeFeat);
610  if (!ofileNodeFeat.is_open())
611  {
612  // ERROR File Not Open
613  return -1;
614  }
615  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
616  { ofileNodeFeat << node->getId() << "\t" << node->getData() << std::endl; };
617  auto nodeSet = getNodeSet();
618  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
619  ofileNodeFeat.close();
620  }
621 
622  if (writeEdgeWeight)
623  {
624  std::ofstream ofileEdgeWeight;
625  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
626  ".tsv";
627  ofileEdgeWeight.open(completePathToFileEdgeWeight);
628  if (!ofileEdgeWeight.is_open())
629  {
630  // ERROR File Not Open
631  return -1;
632  }
633  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
634  { 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; };
635 
636  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
637  ofileEdgeWeight.close();
638  }
639  return 0;
640  }
641 
642  template <typename T>
643  int Graph<T>::readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
644  {
645  std::ifstream ifileGraph;
646  std::ifstream ifileNodeFeat;
647  std::ifstream ifileEdgeWeight;
648  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
649  std::map<unsigned long, bool> edgeDirectedMap;
650  std::map<unsigned long, T> nodeFeatMap;
651  std::map<unsigned long, double> edgeWeightMap;
652  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
653  ifileGraph.open(completePathToFileGraph);
654  if (!ifileGraph.is_open())
655  {
656  // ERROR File Not Open
657  return -1;
658  }
659  for (;;)
660  { /* loop continually */
661  unsigned long edgeId;
662  unsigned long nodeId1;
663  unsigned long nodeId2;
664  bool directed;
665  ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
666  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
667  edgeDirectedMap[edgeId] = directed;
668  if (ifileGraph.fail() || ifileGraph.eof())
669  break;
670  ifileGraph.ignore(128, '\n');
671  }
672  ifileGraph.close();
673 
674  if (readNodeFeat)
675  {
676  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
677  ".tsv";
678  ifileNodeFeat.open(completePathToFileNodeFeat);
679  if (!ifileNodeFeat.is_open())
680  {
681  // ERROR File Not Open
682  return -1;
683  }
684  for (;;)
685  { /* loop continually */
686  unsigned long nodeId;
687  T nodeFeat;
688  ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
689  nodeFeatMap[nodeId] = nodeFeat;
690  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
691  break;
692  ifileNodeFeat.ignore(128, '\n');
693  }
694  ifileNodeFeat.close();
695  }
696 
697  if (readEdgeWeight)
698  {
699  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
700  ".tsv";
701  ifileEdgeWeight.open(completePathToFileEdgeWeight);
702  if (!ifileEdgeWeight.is_open())
703  {
704  // ERROR File Not Open
705  return -1;
706  }
707  for (;;)
708  { /* loop continually */
709  unsigned long edgeId;
710  double weight;
711  bool weighted;
712  ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
713  if (weighted)
714  {
715  edgeWeightMap[edgeId] = weight;
716  }
717  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
718  break;
719  ifileEdgeWeight.ignore(128, '\n');
720  }
721  ifileEdgeWeight.close();
722  }
723  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
724  return 0;
725  }
726 
727  template <typename T>
728  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)
729  {
730  std::map<unsigned long, Node<T> *> nodeMap;
731  for (auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
732  {
733  Node<T> *node1 = nullptr;
734  Node<T> *node2 = nullptr;
735  if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
736  {
737  //Create new Node
738  T feat;
739  if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
740  {
741  feat = nodeFeatMap.at(edgeIt->second.first);
742  }
743  node1 = new Node<T>(edgeIt->second.first, feat);
744  nodeMap[edgeIt->second.first] = node1;
745  }
746  else
747  {
748  node1 = nodeMap.at(edgeIt->second.first);
749  }
750  if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
751  {
752  //Create new Node
753  T feat;
754  if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
755  {
756  feat = nodeFeatMap.at(edgeIt->second.second);
757  }
758  node2 = new Node<T>(edgeIt->second.second, feat);
759  nodeMap[edgeIt->second.second] = node2;
760  }
761  else
762  {
763  node2 = nodeMap.at(edgeIt->second.second);
764  }
765 
766  if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
767  {
768  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
769  {
770  auto edge = new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
771  addEdge(edge);
772  }
773  else
774  {
775  auto edge = new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
776  addEdge(edge);
777  }
778  }
779  else
780  {
781  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
782  {
783  auto edge = new DirectedEdge<T>(edgeIt->first, *node1, *node2);
784  addEdge(edge);
785  }
786  else
787  {
788  auto edge = new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
789  addEdge(edge);
790  }
791  }
792  }
793  }
794 
795  template <typename T>
796  int Graph<T>::compressFile(const std::string &inputFile, const std::string &outputFile) const
797  {
798 
799  std::ifstream ifs;
800  ifs.open(inputFile);
801  if (!ifs.is_open())
802  {
803  // ERROR File Not Open
804  return -1;
805  }
806  std::string content((std::istreambuf_iterator<char>(ifs)),
807  (std::istreambuf_iterator<char>()));
808 
809  const char *content_ptr = content.c_str();
810  gzFile outFileZ = gzopen(outputFile.c_str(), "wb");
811  if (outFileZ == NULL)
812  {
813  //printf("Error: Failed to gzopen %s\n", outputFile.c_str());
814  return -1;
815  }
816 
817  unsigned int zippedBytes;
818  zippedBytes = gzwrite(outFileZ, content_ptr, strlen(content_ptr));
819 
820  ifs.close();
821  gzclose(outFileZ);
822  return 0;
823  }
824 
825  template <typename T>
826  int Graph<T>::decompressFile(const std::string &inputFile, const std::string &outputFile) const
827  {
828 
829  gzFile inFileZ = gzopen(inputFile.c_str(), "rb");
830  if (inFileZ == NULL)
831  {
832  //printf("Error: Failed to gzopen %s\n", inputFile.c_str());
833  return -1;
834  }
835  unsigned char unzipBuffer[8192];
836  unsigned int unzippedBytes;
837  std::vector<unsigned char> unzippedData;
838  std::ofstream ofs;
839  ofs.open(outputFile);
840  if (!ofs.is_open())
841  {
842  // ERROR File Not Open
843  return -1;
844  }
845  while (true)
846  {
847  unzippedBytes = gzread(inFileZ, unzipBuffer, 8192);
848  if (unzippedBytes > 0)
849  {
850  unzippedData.insert(unzippedData.end(), unzipBuffer, unzipBuffer + unzippedBytes);
851  }
852  else
853  {
854  break;
855  }
856  }
857  for (auto c : unzippedData)
858  {
859  ofs << c;
860  }
861  ofs << std::endl;
862  ofs.close();
863  gzclose(inFileZ);
864  return 0;
865  }
866 
867  template <typename T>
868  const AdjacencyMatrix<T> Graph<T>::getAdjMatrix() const
869  {
870  AdjacencyMatrix<T> adj;
871  auto edgeSetIt = edgeSet.begin();
872  for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
873  {
874  if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
875  {
876  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(*edgeSetIt);
877  addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
878  }
879  else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
880  {
881  const UndirectedEdge<T> *ud_edge = dynamic_cast<const UndirectedEdge<T> *>(*edgeSetIt);
882  ;
883  addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
884  addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
885  }
886  else
887  { //is a simple edge we cannot create adj matrix
888  return adj;
889  }
890  }
891  return adj;
892  }
893 
894  template <typename T>
895  const DijkstraResult Graph<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
896  {
897  DijkstraResult result;
898  result.success = false;
899  result.errorMessage = "";
900  result.result = INF_DOUBLE;
901  auto nodeSet = Graph<T>::getNodeSet();
902  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
903  {
904  // check if source node exist in the graph
905  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
906  return result;
907  }
908  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
909  {
910  // check if target node exist in the graph
911  result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
912  return result;
913  }
914  const AdjacencyMatrix<T> adj = Graph<T>::getAdjMatrix();
915  // n denotes the number of vertices in graph
916  int n = adj.size();
917 
918  // setting all the distances initially to INF_DOUBLE
919  std::map<const Node<T> *, double> dist;
920 
921  for (auto elem : adj)
922  {
923  dist[elem.first] = INF_DOUBLE;
924  }
925 
926  // creating a min heap using priority queue
927  // first element of pair contains the distance
928  // second element of pair contains the vertex
929  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
930  std::greater<std::pair<double, const Node<T> *>>>
931  pq;
932 
933  // pushing the source vertex 's' with 0 distance in min heap
934  pq.push(std::make_pair(0.0, &source));
935 
936  // marking the distance of source as 0
937  dist[&source] = 0;
938 
939  while (!pq.empty())
940  {
941  // second element of pair denotes the node / vertex
942  const Node<T> *currentNode = pq.top().second;
943 
944  // first element of pair denotes the distance
945  double currentDist = pq.top().first;
946 
947  pq.pop();
948 
949  // for all the reachable vertex from the currently exploring vertex
950  // we will try to minimize the distance
951  if (adj.find(currentNode) != adj.end())
952  {
953  for (std::pair<const Node<T> *, const Edge<T> *> elem : adj.at(currentNode))
954  {
955  // minimizing distances
956  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
957  {
958  if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
959  {
960  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(elem.second);
961  if (currentDist + dw_edge->getWeight() < dist[elem.first])
962  {
963  dist[elem.first] = currentDist + dw_edge->getWeight();
964  pq.push(std::make_pair(dist[elem.first], elem.first));
965  }
966  }
967  else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
968  {
969  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
970  if (currentDist + udw_edge->getWeight() < dist[elem.first])
971  {
972  dist[elem.first] = currentDist + udw_edge->getWeight();
973  pq.push(std::make_pair(dist[elem.first], elem.first));
974  }
975  }
976  else
977  {
978  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
979  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
980  return result;
981  }
982  }
983  else
984  {
985  // No Weighted Edge
986  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
987  return result;
988  }
989  }
990  }
991  }
992  if (dist[&target] != INF_DOUBLE)
993  {
994  result.success = true;
995  result.errorMessage = "";
996  result.result = dist[&target];
997  return result;
998  }
999  result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
1000  result.result = -1;
1001  return result;
1002  }
1003 
1004  template <typename T>
1005  const BellmanFordResult Graph<T>::bellmanford(const Node<T> &source, const Node<T> &target) const
1006  {
1007  BellmanFordResult result;
1008  result.success = false;
1009  result.errorMessage = "";
1010  result.result = INF_DOUBLE;
1011  auto nodeSet = Graph<T>::getNodeSet();
1012  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1013  {
1014  // check if source node exist in the graph
1015  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1016  return result;
1017  }
1018  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
1019  {
1020  // check if target node exist in the graph
1021  result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
1022  return result;
1023  }
1024  // setting all the distances initially to INF_DOUBLE
1025  std::map<const Node<T> *, double> dist, currentDist;
1026  // n denotes the number of vertices in graph
1027  auto n = nodeSet.size();
1028  for (auto elem : nodeSet)
1029  {
1030  dist[elem] = INF_DOUBLE;
1031  currentDist[elem] = INF_DOUBLE;
1032  }
1033 
1034  // marking the distance of source as 0
1035  dist[&source] = 0;
1036  // set if node distances in two consecutive
1037  // iterations remain the same.
1038  auto earlyStopping = false;
1039  // outer loop for vertex relaxation
1040  for (int i=0; i<n-1; i++)
1041  {
1042  auto edgeSet = Graph<T>::getEdgeSet();
1043  // inner loop for distance updates of
1044  // each relaxation
1045  for (auto edge : edgeSet)
1046  {
1047  auto elem = edge->getNodePair();
1048  if (edge->isWeighted().has_value() && edge->isWeighted().value())
1049  {
1050  auto edge_weight = (dynamic_cast<const Weighted *>(edge))->getWeight();
1051  if (dist[elem.first] + edge_weight < dist[elem.second])
1052  dist[elem.second] = dist[elem.first] + edge_weight;
1053  }
1054  else
1055  {
1056  // No Weighted Edge
1057  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1058  return result;
1059  }
1060  }
1061  auto flag = true;
1062  for (const auto& [key, value] : dist) {
1063  if (currentDist[key]!=value)
1064  {
1065  flag = false;
1066  break;
1067  }
1068  }
1069  for (const auto& [key, value] : dist) {
1070  currentDist[key] = value; //update the current distance
1071  }
1072  if (flag)
1073  {
1074  earlyStopping = true;
1075  break;
1076  }
1077  }
1078 
1079  // check if there exists a negative cycle
1080  if (!earlyStopping)
1081  {
1082  auto edgeSet = Graph<T>::getEdgeSet();
1083  for (auto edge : edgeSet)
1084  {
1085  auto elem = edge->getNodePair();
1086  auto edge_weight = (dynamic_cast<const Weighted *>(edge))->getWeight();
1087  if (dist[elem.first] + edge_weight < dist[elem.second])
1088  {
1089  result.success = true;
1090  result.negativeCycle = true;
1091  result.errorMessage = "";
1092  return result;
1093  }
1094  }
1095  }
1096 
1097  if (dist[&target] != INF_DOUBLE)
1098  {
1099  result.success = true;
1100  result.errorMessage = "";
1101  result.negativeCycle = false;
1102  result.result = dist[&target];
1103  return result;
1104  }
1105  result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
1106  result.result = -1;
1107  return result;
1108  }
1109 
1110  template <typename T>
1112  {
1113  FWResult result;
1114  result.success = false;
1115  result.errorMessage = "";
1116  std::map<std::pair<unsigned long, unsigned long>, double> pairwise_dist;
1117  auto nodeSet = Graph<T>::getNodeSet();
1118  // create a pairwise distance matrix with distance node distances
1119  // set to inf. Distance of node to itself is set as 0.
1120  for (auto elem1 : nodeSet)
1121  {
1122  for (auto elem2 : nodeSet)
1123  {
1124  auto key = std::make_pair(elem1->getId(), elem2->getId());
1125  if (elem1 != elem2)
1126  pairwise_dist[key] = INF_DOUBLE;
1127  else
1128  pairwise_dist[key] = 0.0;
1129  }
1130  }
1131 
1132  auto edgeSet = Graph<T>::getEdgeSet();
1133  // update the weights of nodes
1134  // connected by edges
1135  for (auto edge : edgeSet)
1136  {
1137  auto elem = edge->getNodePair();
1138  if (edge->isWeighted().has_value() && edge->isWeighted().value())
1139  {
1140  auto edgeWeight = (dynamic_cast<const Weighted *>(edge))->getWeight();
1141  auto key = std::make_pair(elem.first->getId(), elem.second->getId());
1142  pairwise_dist[key] = edgeWeight;
1143  }
1144  else
1145  {
1146  // if an edge exists but has no weight associated
1147  // with it, we return an error message
1148  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1149  return result;
1150  }
1151  }
1152 
1153  for (auto k : nodeSet)
1154  {
1155  // set all vertices as source one by one
1156  for (auto src : nodeSet)
1157  {
1158  // iterate through all vertices as destination for the
1159  // current source
1160  auto src_k = std::make_pair(src->getId(), k->getId());
1161  for (auto dst : nodeSet)
1162  {
1163  // If vertex k provides a shorter path than
1164  // src to dst, update the value of
1165  // pairwise_dist[src_to_dst]
1166  auto src_dst = std::make_pair(src->getId(), dst->getId());
1167  auto k_dst = std::make_pair(k->getId(), dst->getId());
1168  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))
1169  pairwise_dist[src_dst] = pairwise_dist[src_k] + pairwise_dist[k_dst];
1170  }
1171  }
1172  }
1173 
1174  result.success = true;
1175  // presense of negative number in the diagonal indicates
1176  // that that the graph contains a negative cycle
1177  for (auto node : nodeSet)
1178  {
1179  auto diag = std::make_pair(node->getId(), node->getId());
1180  if (pairwise_dist[diag] < 0.)
1181  {
1182  result.negativeCycle = true;
1183  return result;
1184  }
1185  }
1186  result.result = std::move(pairwise_dist);
1187  return result;
1188  }
1189 
1190  template <typename T>
1192  {
1193  PrimResult result;
1194  result.success = false;
1195  result.errorMessage = "";
1196  result.mstCost = INF_DOUBLE;
1197  if (!isUndirectedGraph())
1198  {
1199  result.errorMessage = ERR_DIR_GRAPH;
1200  return result;
1201  }
1202  auto nodeSet = Graph<T>::getNodeSet();
1203  auto n = nodeSet.size();
1204  const AdjacencyMatrix<T> adj = Graph<T>::getAdjMatrix();
1205 
1206  // setting all the distances initially to INF_DOUBLE
1207  std::map<const Node<T> *, double> dist;
1208  for (auto elem : adj)
1209  {
1210  dist[elem.first] = INF_DOUBLE;
1211  }
1212 
1213  // creating a min heap using priority queue
1214  // first element of pair contains the distance
1215  // second element of pair contains the vertex
1216  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
1217  std::greater<std::pair<double, const Node<T> *>>>
1218  pq;
1219 
1220  // pushing the source vertex 's' with 0 distance in min heap
1221  auto source = nodeSet.front();
1222  pq.push(std::make_pair(0.0, source));
1223  // initialize cost and start node of mst
1224  result.result.push_back(source->getId());
1225  result.mstCost = 0;
1226  while (!pq.empty())
1227  {
1228  // second element of pair denotes the node / vertex
1229  const Node<T> *currentNode = pq.top().second;
1230  auto nodeId = currentNode->getId();
1231  if (std::find(result.result.begin(), result.result.end(), nodeId) == result.result.end())
1232  {
1233  result.result.push_back(nodeId);
1234  result.mstCost += pq.top().first;
1235  }
1236 
1237  pq.pop();
1238  // for all the reachable vertex from the currently exploring vertex
1239  // we will try to minimize the distance
1240  if (adj.find(currentNode) != adj.end())
1241  {
1242  for (std::pair<const Node<T> *, const Edge<T> *> elem : adj.at(currentNode))
1243  {
1244  // minimizing distances
1245  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
1246  {
1247  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
1248  if (
1249  (udw_edge->getWeight() < dist[elem.first]) &&
1250  (std::find(result.result.begin(), result.result.end(), elem.first->getId()) == result.result.end())
1251  )
1252 
1253  {
1254  dist[elem.first] = udw_edge->getWeight();
1255  pq.push(std::make_pair(dist[elem.first], elem.first));
1256  }
1257  }
1258  else
1259  {
1260  // No Weighted Edge
1261  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1262  return result;
1263  }
1264  }
1265  }
1266  }
1267  result.success = true;
1268  return result;
1269  }
1270 
1271  template <typename T>
1272  const std::vector<Node<T>> Graph<T>::breadth_first_search(const Node<T> &start) const
1273  {
1274  // vector to keep track of visited nodes
1275  std::vector<Node<T>> visited;
1276  auto nodeSet = Graph<T>::getNodeSet();
1277  //check is exist node in the graph
1278  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1279  {
1280  return visited;
1281  }
1282  const AdjacencyMatrix<T> adj = Graph<T>::getAdjMatrix();
1283  // queue that stores vertices that need to be further explored
1284  std::queue<const Node<T> *> tracker;
1285 
1286  // mark the starting node as visited
1287  visited.push_back(start);
1288  tracker.push(&start);
1289  while (!tracker.empty())
1290  {
1291  const Node<T> *node = tracker.front();
1292  tracker.pop();
1293  if (adj.find(node) != adj.end())
1294  {
1295  for (auto elem : adj.at(node))
1296  {
1297  // if the node is not visited then mark it as visited
1298  // and push it to the queue
1299  if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1300  {
1301  visited.push_back(*(elem.first));
1302  tracker.push(elem.first);
1303  }
1304  }
1305  }
1306  }
1307 
1308  return visited;
1309  }
1310 
1311  template <typename T>
1312  const std::vector<Node<T>> Graph<T>::depth_first_search(const Node<T> &start) const
1313  {
1314  // vector to keep track of visited nodes
1315  std::vector<Node<T>> visited;
1316  auto nodeSet = Graph<T>::getNodeSet();
1317  //check is exist node in the graph
1318  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1319  {
1320  return visited;
1321  }
1322  const AdjacencyMatrix<T> adj = Graph<T>::getAdjMatrix();
1323  std::function<void(const AdjacencyMatrix<T> &, const Node<T> &, std::vector<Node<T>> &)> explore;
1324  explore = [&explore](const AdjacencyMatrix<T> &adj, const Node<T> &node, std::vector<Node<T>> &visited) -> void
1325  {
1326  visited.push_back(node);
1327  if (adj.find(&node) != adj.end())
1328  {
1329  for (auto x : adj.at(&node))
1330  {
1331  if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1332  {
1333  explore(adj, *(x.first), visited);
1334  }
1335  }
1336  }
1337  };
1338  explore(adj, start, visited);
1339 
1340  return visited;
1341  }
1342 
1343  template <typename T>
1345  {
1346  if (!isDirectedGraph())
1347  {
1348  return false;
1349  }
1350  enum nodeStates : uint8_t
1351  {
1352  not_visited,
1353  in_stack,
1354  visited
1355  };
1356  auto nodeSet = Graph<T>::getNodeSet();
1357  auto adjMatrix = Graph<T>::getAdjMatrix();
1358 
1359  /* State of the node.
1360  *
1361  * It is a vector of "nodeStates" which represents the state node is in.
1362  * It can take only 3 values: "not_visited", "in_stack", and "visited".
1363  *
1364  * Initially, all nodes are in "not_visited" state.
1365  */
1366  std::map<unsigned long, nodeStates> state;
1367  for (auto node : nodeSet)
1368  {
1369  state[node->getId()] = not_visited;
1370  }
1371  int stateCounter = 0;
1372 
1373  // Start visiting each node.
1374  for (auto node : nodeSet)
1375  {
1376  // If a node is not visited, only then check for presence of cycle.
1377  // There is no need to check for presence of cycle for a visited
1378  // node as it has already been checked for presence of cycle.
1379  if (state[node->getId()] == not_visited)
1380  {
1381  // Check for cycle.
1382  std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &, const Node<T> *)> isCyclicDFSHelper;
1383  isCyclicDFSHelper = [this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states, const Node<T> *node)
1384  {
1385  // Add node "in_stack" state.
1386  states[node->getId()] = in_stack;
1387 
1388  // If the node has children, then recursively visit all children of the
1389  // node.
1390  auto const it = adjMatrix.find(node);
1391  if (it != adjMatrix.end())
1392  {
1393  for (auto child : it->second)
1394  {
1395  // If state of child node is "not_visited", evaluate that child
1396  // for presence of cycle.
1397  auto state_of_child = states.at((std::get<0>(child))->getId());
1398  if (state_of_child == not_visited)
1399  {
1400  if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1401  {
1402  return true;
1403  }
1404  }
1405  else if (state_of_child == in_stack)
1406  {
1407  // If child node was "in_stack", then that means that there
1408  // is a cycle in the graph. Return true for presence of the
1409  // cycle.
1410  return true;
1411  }
1412  }
1413  }
1414 
1415  // Current node has been evaluated for the presence of cycle and had no
1416  // cycle. Mark current node as "visited".
1417  states[node->getId()] = visited;
1418  // Return that current node didn't result in any cycles.
1419  return false;
1420  };
1421  if (isCyclicDFSHelper(adjMatrix, state, node))
1422  {
1423  return true;
1424  }
1425  }
1426  }
1427 
1428  // All nodes have been safely traversed, that means there is no cycle in
1429  // the graph. Return false.
1430  return false;
1431  }
1432 
1433  template <typename T>
1435  {
1436  if (!isDirectedGraph())
1437  {
1438  return false;
1439  }
1440  auto adjMatrix = Graph<T>::getAdjMatrix();
1441  auto nodeSet = Graph<T>::getNodeSet();
1442 
1443  std::map<unsigned long, unsigned int> indegree;
1444  for (auto node : nodeSet)
1445  {
1446  indegree[node->getId()] = 0;
1447  }
1448  // Calculate the indegree i.e. the number of incident edges to the node.
1449  for (auto const &list : adjMatrix)
1450  {
1451  auto children = list.second;
1452  for (auto const &child : children)
1453  {
1454  indegree[std::get<0>(child)->getId()]++;
1455  }
1456  }
1457 
1458  std::queue<const Node<T> *> can_be_solved;
1459  for (auto node : nodeSet)
1460  {
1461  // If a node doesn't have any input edges, then that node will
1462  // definately not result in a cycle and can be visited safely.
1463  if (!indegree[node->getId()])
1464  {
1465  can_be_solved.emplace(&(*node));
1466  }
1467  }
1468 
1469  // Vertices that need to be traversed.
1470  auto remain = Graph<T>::getNodeSet().size();
1471  // While there are safe nodes that we can visit.
1472  while (!can_be_solved.empty())
1473  {
1474  auto solved = can_be_solved.front();
1475  // Visit the node.
1476  can_be_solved.pop();
1477  // Decrease number of nodes that need to be traversed.
1478  remain--;
1479 
1480  // Visit all the children of the visited node.
1481  auto it = adjMatrix.find(solved);
1482  if (it != adjMatrix.end())
1483  {
1484  for (auto child : it->second)
1485  {
1486  // Check if we can visited the node safely.
1487  if (--indegree[std::get<0>(child)->getId()] == 0)
1488  {
1489  // if node can be visited safely, then add that node to
1490  // the visit queue.
1491  can_be_solved.emplace(std::get<0>(child));
1492  }
1493  }
1494  }
1495  }
1496 
1497  // If there are still nodes that we can't visit, then it means that
1498  // there is a cycle and return true, else return false.
1499  return !(remain == 0);
1500  }
1501 
1502  template <typename T>
1504  {
1505  auto edgeSet = Graph<T>::getEdgeSet();
1506  for (auto edge : edgeSet)
1507  {
1508  if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1509  {
1510  //Found Undirected Edge
1511  return false;
1512  }
1513  }
1514  //No Undirected Edge
1515  return true;
1516  }
1517 
1518  template <typename T>
1520  {
1521  auto edgeSet = Graph<T>::getEdgeSet();
1522  for (auto edge : edgeSet)
1523  {
1524  if ((edge->isDirected().has_value() && edge->isDirected().value()))
1525  {
1526  //Found Directed Edge
1527  return false;
1528  }
1529  }
1530  //No Directed Edge
1531  return true;
1532  }
1533 
1534  template <typename T>
1535  const DialResult Graph<T>::dial(const Node<T> &source, int maxWeight) const
1536  {
1537  DialResult result;
1538  result.success = false;
1539 
1540  auto adj = Graph<T>::getAdjMatrix();
1541  auto nodeSet = Graph<T>::getNodeSet();
1542 
1543  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1544  {
1545  // check if source node exist in the graph
1546  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1547  return result;
1548  }
1549  /* With each distance, iterator to that vertex in
1550  its bucket is stored so that vertex can be deleted
1551  in O(1) at time of updation. So
1552  dist[i].first = distance of ith vertex from src vertex
1553  dits[i].second = vertex i in bucket number */
1554  unsigned int V = nodeSet.size();
1555  std::map<const Node<T> *, std::pair<long, const Node<T> *>> dist;
1556 
1557  // Initialize all distances as infinite (INF)
1558  for (auto node : nodeSet)
1559  {
1560  dist[&(*node)].first = std::numeric_limits<long>::max();
1561  }
1562 
1563  // Create buckets B[].
1564  // B[i] keep vertex of distance label i
1565  std::list<const Node<T> *> B[maxWeight * V + 1];
1566 
1567  B[0].push_back(&source);
1568  dist[&source].first = 0;
1569 
1570  int idx = 0;
1571  while (1)
1572  {
1573  // Go sequentially through buckets till one non-empty
1574  // bucket is found
1575  while (B[idx].size() == 0 && idx < maxWeight * V)
1576  {
1577  idx++;
1578  }
1579 
1580  // If all buckets are empty, we are done.
1581  if (idx == maxWeight * V)
1582  {
1583  break;
1584  }
1585 
1586  // Take top vertex from bucket and pop it
1587  auto u = B[idx].front();
1588  B[idx].pop_front();
1589 
1590  // Process all adjacents of extracted vertex 'u' and
1591  // update their distanced if required.
1592  for (auto i = adj[u].begin(); i != adj[u].end(); ++i)
1593  {
1594  auto v = (*i).first;
1595  int weight = 0;
1596  if ((*i).second->isWeighted().has_value() && (*i).second->isWeighted().value())
1597  {
1598  if ((*i).second->isDirected().has_value() && (*i).second->isDirected().value())
1599  {
1600  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>((*i).second);
1601  weight = dw_edge->getWeight();
1602  }
1603  else if ((*i).second->isDirected().has_value() && !(*i).second->isDirected().value())
1604  {
1605  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>((*i).second);
1606  weight = udw_edge->getWeight();
1607  }
1608  else
1609  {
1610  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
1611  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1612  return result;
1613  }
1614  }
1615  else
1616  {
1617  // No Weighted Edge
1618  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1619  return result;
1620  }
1621  auto u_i = std::find_if(dist.begin(), dist.end(), [u](std::pair<const Node<T> *, std::pair<long, const Node<T> *>> const &it)
1622  { return (*u == *(it.first)); });
1623 
1624  auto v_i = std::find_if(dist.begin(), dist.end(), [v](std::pair<const Node<T> *, std::pair<long, const Node<T> *>> const &it)
1625  { return (*v == *(it.first)); });
1626  long du = u_i->second.first;
1627  long dv = v_i->second.first;
1628 
1629  // If there is shorted path to v through u.
1630  if (dv > du + weight)
1631  {
1632  // If dv is not INF then it must be in B[dv]
1633  // bucket, so erase its entry using iterator
1634  // in O(1)
1635  if (dv != std::numeric_limits<long>::max())
1636  {
1637  auto findIter = std::find(B[dv].begin(), B[dv].end(), dist[v].second);
1638  B[dv].erase(findIter);
1639  }
1640 
1641  // updating the distance
1642  dist[v].first = du + weight;
1643  dv = dist[v].first;
1644 
1645  // pushing vertex v into updated distance's bucket
1646  B[dv].push_front(v);
1647 
1648  // storing updated iterator in dist[v].second
1649  dist[v].second = *(B[dv].begin());
1650  }
1651  }
1652  }
1653  for (auto dist_i : dist)
1654  {
1655  result.minDistanceMap[dist_i.first->getId()] = dist_i.second.first;
1656  }
1657  result.success = true;
1658 
1659  return result;
1660  }
1661 
1662  template <typename T>
1663  const std::vector<Node<T>> Graph<T>::graph_slicing(const Node<T> &start) const
1664  {
1665  std::vector<Node<T>> result;
1666 
1667  std::list<const Node<T> *> nodeSet = Graph<T>::getNodeSet();
1668  //check if start node in the graph
1669  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1670  {
1671  return result;
1672  }
1673  std::vector<Node<T>> C = Graph<T>::depth_first_search(start);
1674  std::list<const Node<T> *> C1; //complement of C i.e. nodeSet - C
1675  for (auto const node : nodeSet)
1676  {
1677  // from the set of all nodes, remove nodes that exist in C
1678  if (std::find_if(C.begin(), C.end(), [node](const Node<T> nodeC)
1679  { return (*node == nodeC); }) == C.end())
1680  C1.push_back(node);
1681  }
1682 
1683  // For all nodes in C', apply DFS
1684  // and get the list of reachable nodes and store in M
1685  std::vector<Node<T>> M;
1686  for (auto const node : C1)
1687  {
1688  std::vector<Node<T>> reachableNodes = Graph<T>::depth_first_search(*node);
1689  M.insert(M.end(),reachableNodes.begin(),reachableNodes.end());
1690  }
1691  // removes nodes from C that are reachable from M.
1692  for (const Node<T> nodeC : C)
1693  {
1694  if (std::find_if(M.begin(), M.end(), [nodeC](const Node<T> nodeM)
1695  { return (nodeM == nodeC); }) == M.end())
1696  result.push_back(nodeC);
1697  }
1698  return result;
1699  }
1700 
1701  template <typename T>
1702  int Graph<T>::writeToFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
1703  {
1704  int result = 0;
1705  if (format == InputOutputFormat::STANDARD_CSV)
1706  {
1707  result = writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1708  }
1709  else if (format == InputOutputFormat::STANDARD_TSV)
1710  {
1711  result = writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1712  }
1713  else
1714  {
1715  //OUTPUT FORMAT NOT RECOGNIZED
1716  return -1;
1717  }
1718  if (result == 0 && compress)
1719  {
1720  auto compress = [this, &workingDir, &OFileName, &writeNodeFeat, &writeEdgeWeight](const std::string &extension)
1721  {
1722  std::string completePathToFileGraph = workingDir + "/" + OFileName + extension;
1723  std::string completePathToFileGraphCompressed = workingDir + "/" + OFileName + extension + ".gz";
1724  int _result = compressFile(completePathToFileGraph, completePathToFileGraphCompressed);
1725  if (_result == 0)
1726  {
1727  _result = remove(completePathToFileGraph.c_str());
1728  }
1729  if (_result == 0)
1730  {
1731  if (writeNodeFeat)
1732  {
1733  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat" + extension;
1734  std::string completePathToFileNodeFeatCompressed = workingDir + "/" + OFileName + "_NodeFeat" + extension + ".gz";
1735  _result = compressFile(completePathToFileNodeFeat, completePathToFileNodeFeatCompressed);
1736  if (_result == 0)
1737  {
1738  _result = remove(completePathToFileNodeFeat.c_str());
1739  }
1740  }
1741  }
1742  if (_result == 0)
1743  {
1744  if (writeEdgeWeight)
1745  {
1746  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight" + extension;
1747  std::string completePathToFileEdgeWeightCompressed = workingDir + "/" + OFileName + "_EdgeWeight" + extension + ".gz";
1748  _result = compressFile(completePathToFileEdgeWeight, completePathToFileEdgeWeightCompressed);
1749  if (_result == 0)
1750  {
1751  _result = remove(completePathToFileEdgeWeight.c_str());
1752  }
1753  }
1754  }
1755  return _result;
1756  };
1757  if (format == InputOutputFormat::STANDARD_CSV)
1758  {
1759  auto result = compress(".csv");
1760  }
1761  else if (format == InputOutputFormat::STANDARD_TSV)
1762  {
1763  auto result = compress(".tsv");
1764  }
1765  else
1766  {
1767  //OUTPUT FORMAT NOT RECOGNIZED
1768  result = -1;
1769  }
1770  }
1771  return result;
1772  }
1773 
1774  template <typename T>
1775  int Graph<T>::readFromFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
1776  {
1777  int result = 0;
1778  if (compress)
1779  {
1780  auto decompress = [this, &workingDir, &OFileName, &readNodeFeat, &readEdgeWeight](const std::string &extension)
1781  {
1782  std::string completePathToFileGraph = workingDir + "/" + OFileName + extension;
1783  std::string completePathToFileGraphCompressed = workingDir + "/" + OFileName + extension + ".gz";
1784  int _result = decompressFile(completePathToFileGraphCompressed, completePathToFileGraph);
1785  if (_result == 0)
1786  {
1787  if (readNodeFeat)
1788  {
1789  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat" + extension;
1790  std::string completePathToFileNodeFeatCompressed = workingDir + "/" + OFileName + "_NodeFeat" + extension + ".gz";
1791  _result = decompressFile(completePathToFileNodeFeatCompressed, completePathToFileNodeFeat);
1792  }
1793  }
1794  if (_result == 0)
1795  {
1796  if (readEdgeWeight)
1797  {
1798  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight" + extension;
1799  std::string completePathToFileEdgeWeightCompressed = workingDir + "/" + OFileName + "_EdgeWeight" + extension + ".gz";
1800  _result = decompressFile(completePathToFileEdgeWeightCompressed, completePathToFileEdgeWeight);
1801  }
1802  }
1803  return _result;
1804  };
1805  if (format == InputOutputFormat::STANDARD_CSV)
1806  {
1807  result = decompress(".csv");
1808  }
1809  else if (format == InputOutputFormat::STANDARD_TSV)
1810  {
1811  result = decompress(".tsv");
1812  }
1813  else
1814  {
1815  //OUTPUT FORMAT NOT RECOGNIZED
1816  result = -1;
1817  }
1818  }
1819  if (result == 0)
1820  {
1821  if (format == InputOutputFormat::STANDARD_CSV)
1822  {
1823  result = readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1824  }
1825  else if (format == InputOutputFormat::STANDARD_TSV)
1826  {
1827  result = readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1828  }
1829  else
1830  {
1831  //OUTPUT FORMAT NOT RECOGNIZED
1832  result = -1;
1833  }
1834  }
1835  return result;
1836  }
1837 
1838  template <typename T>
1839  PartitionMap<T> Graph<T>::partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
1840  {
1841  PartitionMap<T> partitionMap;
1842  PARTITIONING::Globals globals(numberOfPartitions,algorithm);
1843 
1844  PARTITIONING::Partitioner<T> partitioner(getEdgeSet(), globals);
1845  PARTITIONING::CoordinatedPartitionState<T> partitionState = partitioner.performCoordinatedPartition();
1846  partitionMap = partitionState.getPartitionMap();
1847 
1848  return partitionMap;
1849 
1850  }
1851 
1852  template <typename T>
1853  std::ostream &operator<<(std::ostream &os, const Graph<T> &graph){
1854  os << "Graph:\n";
1855  auto edgeList = graph.getEdgeSet();
1856  auto it = edgeList.begin();
1857  for(it; it != edgeList.end(); ++it){
1858  if (((*it)->isDirected().has_value()&& (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
1859  {
1860  os << dynamic_cast<const DirectedWeightedEdge<T> &>(**it) << "\n";
1861  }
1862  else if (((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
1863  {
1864  os << dynamic_cast<const DirectedEdge<T> &>(**it) << "\n";
1865  }
1866  else if (!((*it)->isDirected().has_value() && (*it)->isDirected().value()) && ((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
1867  {
1868  os << dynamic_cast<const UndirectedWeightedEdge<T> &>(**it) << "\n";
1869  }
1870  else if (!((*it)->isDirected().has_value() && (*it)->isDirected().value()) && !((*it)->isWeighted().has_value() && (*it)->isWeighted().value()))
1871  {
1872  os << dynamic_cast<const UndirectedEdge<T> &>(**it) << "\n";
1873  }
1874  else
1875  {
1876  os << **it << "\n";
1877  }
1878  }
1879  return os;
1880  }
1881 
1882  template <typename T>
1883  std::ostream &operator<<(std::ostream &os, const AdjacencyMatrix<T> &adj)
1884  {
1885  os << "Adjacency Matrix:\n";
1886  auto it = adj.begin();
1887  unsigned long max_column = 0;
1888  for (it; it != adj.end(); ++it)
1889  {
1890  if (it->second.size() > max_column)
1891  {
1892  max_column = it->second.size();
1893  }
1894  }
1895  if (max_column == 0)
1896  {
1897  os << "ERROR in Print\n";
1898  return os;
1899  }
1900  else
1901  {
1902  it = adj.begin();
1903  os << "|--|";
1904  for (int i = 0; i < max_column; i++)
1905  {
1906  os << "-----|";
1907  }
1908  os << "\n";
1909  for (it; it != adj.end(); ++it)
1910  {
1911  os << "|N" << it->first->getId() << "|";
1912  auto it2 = it->second.begin();
1913  for (it2; it2 != it->second.end(); ++it2)
1914  {
1915  os << "N" << it2->first->getId() << ",E" << it2->second->getId() << "|";
1916  }
1917  os << "\n|--|";
1918  for (int i = 0; i < max_column; i++)
1919  {
1920  os << "-----|";
1921  }
1922  os << "\n";
1923  }
1924  }
1925  return os;
1926  }
1927 
1928 } // namespace CXXGRAPH
1929 #endif // __GRAPH_H__
Definition: DirectedEdge.hpp:39
Definition: DirectedWeightedEdge.hpp:42
Definition: Edge.hpp:39
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:78
virtual const FWResult floydWarshall() const
Function runs the floyd-warshall algorithm and returns the shortest distance of all pair of nodes....
Definition: Graph.hpp:1111
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:1312
virtual bool isUndirectedGraph() const
This function checks if a graph is undirected Note: No Thread Safe.
Definition: Graph.hpp:1519
virtual const std::list< const Edge< T > * > & getEdgeSet() const
Function that return the Edge set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:363
virtual const std::optional< const Edge< T > * > getEdge(unsigned long edgeId) const
Function that return an Edge with specific ID if Exist in the Graph Note: No Thread Safe.
Definition: Graph.hpp:424
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:1434
virtual void removeEdge(unsigned long edgeId)
Function remove an Edge from the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:393
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:1702
virtual bool isDirectedGraph() const
This function checks if a graph is directed Note: No Thread Safe.
Definition: Graph.hpp:1503
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:1535
virtual const std::vector< Node< T > > graph_slicing(const Node< T > &start) const
This function performs Graph Slicing based on connectivity.
Definition: Graph.hpp:1663
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:895
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:1344
virtual void addEdge(const Edge< T > *edge)
Function add an Edge to the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:383
virtual const PrimResult prim() const
Function runs the prim algorithm and returns the minimum spanning tree if the graph is undirected....
Definition: Graph.hpp:1191
virtual PartitionMap< T > partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
This function partition a graph in a set of partitions Note: No Thread Safe.
Definition: Graph.hpp:1839
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:1775
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:868
virtual const std::list< const Node< T > * > getNodeSet() const
Function that return the Node Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:404
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:1005
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:1272
virtual void setEdgeSet(std::list< const Edge< T > * > &edgeSet)
Function set the Edge Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:369
Definition: Node.hpp:35
Definition: CoordinatedPartitionState.hpp:40
Definition: Globals.hpp:32
Definition: Partitioner.hpp:40
Definition: UndirectedEdge.hpp:39
Definition: UndirectedWeightedEdge.hpp:43
Definition: Weighted.hpp:28
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:71
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:101
Struct that contains the information about Dijsktra's Algorithm results.
Definition: Typedef.hpp:62
Struct that contains the information about Floyd-Warshall Algorithm results.
Definition: Typedef.hpp:81
Struct that contains the information about Prim Algorithm results.
Definition: Typedef.hpp:91