CXXGraph  0.1.6
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 
61 namespace CXXGRAPH
62 {
63  namespace PARTITIONING{
64  template<typename T>
65  class Partition;
66  }
67 
68  template <typename T>
69  std::ostream &operator<<(std::ostream &o, const Graph<T> &graph);
70  template <typename T>
71  std::ostream &operator<<(std::ostream &o, const AdjacencyMatrix<T> &adj);
72 
74  template <typename T>
75  class Graph
76  {
77  private:
78  std::list<const Edge<T> *> edgeSet;
79  void addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const;
80  int writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
81  int readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
82  int writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const;
83  int readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight);
84  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);
85  int compressFile(const std::string &inputFile, const std::string &outputFile) const;
86  int decompressFile(const std::string &inputFile, const std::string &outputFile) const;
87  void greedyPartition(PartitionMap<T> &partitionMap) const;
88  void HDRFPartition(PartitionMap<T> &partitionMap) 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;
178  virtual const std::vector<Node<T>> breadth_first_search(const Node<T> &start) const;
189  virtual const std::vector<Node<T>> depth_first_search(const Node<T> &start) const;
190 
199  virtual bool isCyclicDirectedGraphDFS() const;
200 
209  virtual bool isCyclicDirectedGraphBFS() const;
210 
218  virtual bool isDirectedGraph() const;
219 
246  virtual const DialResult dial(const Node<T> &source, int maxWeight) const;
247 
261  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;
262 
276  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);
277 
287  virtual PartitionMap<T> partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const;
288 
289  friend std::ostream &operator<<<>(std::ostream &os, const Graph<T> &graph);
290  friend std::ostream &operator<<<>(std::ostream &os, const AdjacencyMatrix<T> &adj);
291  };
292 
293  template <typename T>
294  Graph<T>::Graph(const std::list<const Edge<T> *> &edgeSet)
295  {
296  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
297  {
298  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
299  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
300  {
301  this->edgeSet.push_back(*edgeSetIt);
302  }
303  }
304  }
305 
306  template <typename T>
307  const std::list<const Edge<T> *> &Graph<T>::getEdgeSet() const
308  {
309  return edgeSet;
310  }
311 
312  template <typename T>
313  void Graph<T>::setEdgeSet(std::list<const Edge<T> *> &edgeSet)
314  {
315  this->edgeSet.clear();
316  for (auto edgeSetIt = edgeSet.begin(); edgeSetIt != edgeSet.end(); ++edgeSetIt)
317  {
318  if (std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeSetIt](const Edge<T> *edge)
319  { return (*edge == **edgeSetIt); }) == this->edgeSet.end())
320  {
321  this->edgeSet.push_back(*edgeSetIt);
322  }
323  }
324  }
325 
326  template <typename T>
327  void Graph<T>::addEdge(const Edge<T> *edge)
328  {
329  if (std::find_if(edgeSet.begin(), edgeSet.end(), [edge](const Edge<T> *edge_a)
330  { return (*edge == *edge_a); }) == edgeSet.end())
331  {
332  edgeSet.push_back(edge);
333  }
334  }
335 
336  template <typename T>
337  void Graph<T>::removeEdge(unsigned long edgeId)
338  {
339  auto edgeOpt = Graph<T>::getEdge(edgeId);
340  if (edgeOpt.has_value())
341  {
342  edgeSet.erase(std::find_if(this->edgeSet.begin(), this->edgeSet.end(), [edgeOpt](const Edge<T> *edge)
343  { return (*(edgeOpt.value()) == *edge); }));
344  }
345  }
346 
347  template <typename T>
348  const std::list<const Node<T> *> Graph<T>::getNodeSet() const
349  {
350  std::list<const Node<T> *> nodeSet;
351  for (auto edge : edgeSet)
352  {
353  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
354  { return (*edge->getNodePair().first == *node); }) == nodeSet.end())
355  {
356  nodeSet.push_back(edge->getNodePair().first);
357  }
358  if (std::find_if(nodeSet.begin(), nodeSet.end(), [edge](const Node<T> *node)
359  { return (*edge->getNodePair().second == *node); }) == nodeSet.end())
360  {
361  nodeSet.push_back(edge->getNodePair().second);
362  }
363  }
364  return nodeSet;
365  }
366 
367  template <typename T>
368  const std::optional<const Edge<T> *> Graph<T>::getEdge(unsigned long edgeId) const
369  {
370 
371  auto it = edgeSet.begin();
372  for (it; it != edgeSet.end(); ++it)
373  {
374  if ((*it)->getId() == edgeId)
375  {
376  return *it;
377  }
378  }
379 
380  return std::nullopt;
381  }
382 
383  template <typename T>
384  void Graph<T>::addElementToAdjMatrix(AdjacencyMatrix<T> &adjMatrix, const Node<T> *nodeFrom, const Node<T> *nodeTo, const Edge<T> *edge) const
385  {
386  std::pair<const Node<T> *, const Edge<T> *> elem = {nodeTo, edge};
387  adjMatrix[nodeFrom].push_back(elem);
388 
389  //adjMatrix[nodeFrom.getId()].push_back(std::make_pair<const Node<T>,const Edge<T>>(nodeTo, edge));
390  }
391 
392  template <typename T>
393  int Graph<T>::writeToStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
394  {
395  std::ofstream ofileGraph;
396  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
397  ofileGraph.open(completePathToFileGraph);
398  if (!ofileGraph.is_open())
399  {
400  // ERROR File Not Open
401  return -1;
402  }
403  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
404  { ofileGraph << e->getId() << "," << e->getNodePair().first->getId() << "," << e->getNodePair().second->getId() << "," << ((e->isDirected().has_value() && e->isDirected().value()) ? 1 : 0) << std::endl; };
405  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
406  ofileGraph.close();
407 
408  if (writeNodeFeat)
409  {
410  std::ofstream ofileNodeFeat;
411  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
412  ".csv";
413  ofileNodeFeat.open(completePathToFileNodeFeat);
414  if (!ofileNodeFeat.is_open())
415  {
416  // ERROR File Not Open
417  return -1;
418  }
419  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
420  { ofileNodeFeat << node->getId() << "," << node->getData() << std::endl; };
421  auto nodeSet = getNodeSet();
422  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
423  ofileNodeFeat.close();
424  }
425 
426  if (writeEdgeWeight)
427  {
428  std::ofstream ofileEdgeWeight;
429  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
430  ".csv";
431  ofileEdgeWeight.open(completePathToFileEdgeWeight);
432  if (!ofileEdgeWeight.is_open())
433  {
434  // ERROR File Not Open
435  return -1;
436  }
437  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
438  { 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; };
439 
440  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
441  ofileEdgeWeight.close();
442  }
443  return 0;
444  }
445 
446  template <typename T>
447  int Graph<T>::readFromStandardFile_csv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
448  {
449  std::ifstream ifileGraph;
450  std::ifstream ifileNodeFeat;
451  std::ifstream ifileEdgeWeight;
452  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
453  std::map<unsigned long, bool> edgeDirectedMap;
454  std::map<unsigned long, T> nodeFeatMap;
455  std::map<unsigned long, double> edgeWeightMap;
456  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".csv";
457  ifileGraph.open(completePathToFileGraph);
458  if (!ifileGraph.is_open())
459  {
460  // ERROR File Not Open
461  return -1;
462  }
463  char comma;
464  for (;;)
465  { /* loop continually */
466  unsigned long edgeId;
467  unsigned long nodeId1;
468  unsigned long nodeId2;
469  bool directed;
470  ifileGraph >> edgeId >> comma >> nodeId1 >> comma >> nodeId2 >> comma >> directed;
471  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
472  edgeDirectedMap[edgeId] = directed;
473  if (ifileGraph.fail() || ifileGraph.eof())
474  break;
475  ifileGraph.ignore(128, '\n');
476  }
477  ifileGraph.close();
478 
479  if (readNodeFeat)
480  {
481  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
482  ".csv";
483  ifileNodeFeat.open(completePathToFileNodeFeat);
484  if (!ifileNodeFeat.is_open())
485  {
486  // ERROR File Not Open
487  return -1;
488  }
489  for (;;)
490  { /* loop continually */
491  unsigned long nodeId;
492  T nodeFeat;
493  ifileNodeFeat >> nodeId >> comma >> nodeFeat;
494  nodeFeatMap[nodeId] = nodeFeat;
495  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
496  break;
497  ifileNodeFeat.ignore(128, '\n');
498  }
499  ifileNodeFeat.close();
500  }
501 
502  if (readEdgeWeight)
503  {
504  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
505  ".csv";
506  ifileEdgeWeight.open(completePathToFileEdgeWeight);
507  if (!ifileEdgeWeight.is_open())
508  {
509  // ERROR File Not Open
510  return -1;
511  }
512  for (;;)
513  { /* loop continually */
514  unsigned long edgeId;
515  double weight;
516  bool weighted;
517  ifileEdgeWeight >> edgeId >> comma >> weight >> comma >> weighted;
518  if (weighted)
519  {
520  edgeWeightMap[edgeId] = weight;
521  }
522  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
523  break;
524  ifileEdgeWeight.ignore(128, '\n');
525  }
526  ifileEdgeWeight.close();
527  }
528  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
529  return 0;
530  }
531 
532  template <typename T>
533  int Graph<T>::writeToStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
534  {
535  std::ofstream ofileGraph;
536  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
537  ofileGraph.open(completePathToFileGraph);
538  if (!ofileGraph.is_open())
539  {
540  // ERROR File Not Open
541  return -1;
542  }
543  auto printOutGraph = [&ofileGraph](const Edge<T> *e)
544  { 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; };
545  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutGraph);
546  ofileGraph.close();
547 
548  if (writeNodeFeat)
549  {
550  std::ofstream ofileNodeFeat;
551  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
552  ".tsv";
553  ofileNodeFeat.open(completePathToFileNodeFeat);
554  if (!ofileNodeFeat.is_open())
555  {
556  // ERROR File Not Open
557  return -1;
558  }
559  auto printOutNodeFeat = [&ofileNodeFeat](const Node<T> *node)
560  { ofileNodeFeat << node->getId() << "\t" << node->getData() << std::endl; };
561  auto nodeSet = getNodeSet();
562  std::for_each(nodeSet.cbegin(), nodeSet.cend(), printOutNodeFeat);
563  ofileNodeFeat.close();
564  }
565 
566  if (writeEdgeWeight)
567  {
568  std::ofstream ofileEdgeWeight;
569  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
570  ".tsv";
571  ofileEdgeWeight.open(completePathToFileEdgeWeight);
572  if (!ofileEdgeWeight.is_open())
573  {
574  // ERROR File Not Open
575  return -1;
576  }
577  auto printOutEdgeWeight = [&ofileEdgeWeight](const Edge<T> *e)
578  { 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; };
579 
580  std::for_each(edgeSet.cbegin(), edgeSet.cend(), printOutEdgeWeight);
581  ofileEdgeWeight.close();
582  }
583  return 0;
584  }
585 
586  template <typename T>
587  int Graph<T>::readFromStandardFile_tsv(const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
588  {
589  std::ifstream ifileGraph;
590  std::ifstream ifileNodeFeat;
591  std::ifstream ifileEdgeWeight;
592  std::map<unsigned long, std::pair<unsigned long, unsigned long>> edgeMap;
593  std::map<unsigned long, bool> edgeDirectedMap;
594  std::map<unsigned long, T> nodeFeatMap;
595  std::map<unsigned long, double> edgeWeightMap;
596  std::string completePathToFileGraph = workingDir + "/" + OFileName + ".tsv";
597  ifileGraph.open(completePathToFileGraph);
598  if (!ifileGraph.is_open())
599  {
600  // ERROR File Not Open
601  return -1;
602  }
603  for (;;)
604  { /* loop continually */
605  unsigned long edgeId;
606  unsigned long nodeId1;
607  unsigned long nodeId2;
608  bool directed;
609  ifileGraph >> edgeId >> std::ws >> nodeId1 >> std::ws >> nodeId2 >> std::ws >> directed;
610  edgeMap[edgeId] = std::pair<unsigned long, unsigned long>(nodeId1, nodeId2);
611  edgeDirectedMap[edgeId] = directed;
612  if (ifileGraph.fail() || ifileGraph.eof())
613  break;
614  ifileGraph.ignore(128, '\n');
615  }
616  ifileGraph.close();
617 
618  if (readNodeFeat)
619  {
620  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat"
621  ".tsv";
622  ifileNodeFeat.open(completePathToFileNodeFeat);
623  if (!ifileNodeFeat.is_open())
624  {
625  // ERROR File Not Open
626  return -1;
627  }
628  for (;;)
629  { /* loop continually */
630  unsigned long nodeId;
631  T nodeFeat;
632  ifileNodeFeat >> nodeId >> std::ws >> nodeFeat;
633  nodeFeatMap[nodeId] = nodeFeat;
634  if (ifileNodeFeat.fail() || ifileNodeFeat.eof())
635  break;
636  ifileNodeFeat.ignore(128, '\n');
637  }
638  ifileNodeFeat.close();
639  }
640 
641  if (readEdgeWeight)
642  {
643  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight"
644  ".tsv";
645  ifileEdgeWeight.open(completePathToFileEdgeWeight);
646  if (!ifileEdgeWeight.is_open())
647  {
648  // ERROR File Not Open
649  return -1;
650  }
651  for (;;)
652  { /* loop continually */
653  unsigned long edgeId;
654  double weight;
655  bool weighted;
656  ifileEdgeWeight >> edgeId >> std::ws >> weight >> std::ws >> weighted;
657  if (weighted)
658  {
659  edgeWeightMap[edgeId] = weight;
660  }
661  if (ifileEdgeWeight.fail() || ifileEdgeWeight.eof())
662  break;
663  ifileEdgeWeight.ignore(128, '\n');
664  }
665  ifileEdgeWeight.close();
666  }
667  recreateGraphFromReadFiles(edgeMap, edgeDirectedMap, nodeFeatMap, edgeWeightMap);
668  return 0;
669  }
670 
671  template <typename T>
672  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)
673  {
674  std::map<unsigned long, Node<T> *> nodeMap;
675  for (auto edgeIt = edgeMap.begin(); edgeIt != edgeMap.end(); ++edgeIt)
676  {
677  Node<T> *node1 = nullptr;
678  Node<T> *node2 = nullptr;
679  if (nodeMap.find(edgeIt->second.first) == nodeMap.end())
680  {
681  //Create new Node
682  T feat;
683  if (nodeFeatMap.find(edgeIt->second.first) != nodeFeatMap.end())
684  {
685  feat = nodeFeatMap.at(edgeIt->second.first);
686  }
687  node1 = new Node<T>(edgeIt->second.first, feat);
688  nodeMap[edgeIt->second.first] = node1;
689  }
690  else
691  {
692  node1 = nodeMap.at(edgeIt->second.first);
693  }
694  if (nodeMap.find(edgeIt->second.second) == nodeMap.end())
695  {
696  //Create new Node
697  T feat;
698  if (nodeFeatMap.find(edgeIt->second.second) != nodeFeatMap.end())
699  {
700  feat = nodeFeatMap.at(edgeIt->second.second);
701  }
702  node2 = new Node<T>(edgeIt->second.second, feat);
703  nodeMap[edgeIt->second.second] = node2;
704  }
705  else
706  {
707  node2 = nodeMap.at(edgeIt->second.second);
708  }
709 
710  if (edgeWeightMap.find(edgeIt->first) != edgeWeightMap.end())
711  {
712  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
713  {
714  auto edge = new DirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
715  addEdge(edge);
716  }
717  else
718  {
719  auto edge = new UndirectedWeightedEdge<T>(edgeIt->first, *node1, *node2, edgeWeightMap.at(edgeIt->first));
720  addEdge(edge);
721  }
722  }
723  else
724  {
725  if (edgeDirectedMap.find(edgeIt->first) != edgeDirectedMap.end() && edgeDirectedMap.at(edgeIt->first))
726  {
727  auto edge = new DirectedEdge<T>(edgeIt->first, *node1, *node2);
728  addEdge(edge);
729  }
730  else
731  {
732  auto edge = new UndirectedEdge<T>(edgeIt->first, *node1, *node2);
733  addEdge(edge);
734  }
735  }
736  }
737  }
738 
739  template <typename T>
740  int Graph<T>::compressFile(const std::string &inputFile, const std::string &outputFile) const
741  {
742 
743  std::ifstream ifs;
744  ifs.open(inputFile);
745  if (!ifs.is_open())
746  {
747  // ERROR File Not Open
748  return -1;
749  }
750  std::string content((std::istreambuf_iterator<char>(ifs)),
751  (std::istreambuf_iterator<char>()));
752 
753  const char *content_ptr = content.c_str();
754  gzFile outFileZ = gzopen(outputFile.c_str(), "wb");
755  if (outFileZ == NULL)
756  {
757  //printf("Error: Failed to gzopen %s\n", outputFile.c_str());
758  return -1;
759  }
760 
761  unsigned int zippedBytes;
762  zippedBytes = gzwrite(outFileZ, content_ptr, strlen(content_ptr));
763 
764  ifs.close();
765  gzclose(outFileZ);
766  return 0;
767  }
768 
769  template <typename T>
770  int Graph<T>::decompressFile(const std::string &inputFile, const std::string &outputFile) const
771  {
772 
773  gzFile inFileZ = gzopen(inputFile.c_str(), "rb");
774  if (inFileZ == NULL)
775  {
776  //printf("Error: Failed to gzopen %s\n", inputFile.c_str());
777  return -1;
778  }
779  unsigned char unzipBuffer[8192];
780  unsigned int unzippedBytes;
781  std::vector<unsigned char> unzippedData;
782  std::ofstream ofs;
783  ofs.open(outputFile);
784  if (!ofs.is_open())
785  {
786  // ERROR File Not Open
787  return -1;
788  }
789  while (true)
790  {
791  unzippedBytes = gzread(inFileZ, unzipBuffer, 8192);
792  if (unzippedBytes > 0)
793  {
794  unzippedData.insert(unzippedData.end(), unzipBuffer, unzipBuffer + unzippedBytes);
795  }
796  else
797  {
798  break;
799  }
800  }
801  for (auto c : unzippedData)
802  {
803  ofs << c;
804  }
805  ofs << std::endl;
806  ofs.close();
807  gzclose(inFileZ);
808  return 0;
809  }
810 
811  template <typename T>
812  void Graph<T>::greedyPartition(PartitionMap<T> &partitionMap) const
813  {
814  unsigned int index = 0;
815  unsigned int numberOfPartitions = partitionMap.size();
816  if (index == numberOfPartitions)
817  {
818  //ERROR partition map of zero element
819  return;
820  }
821  auto edgeSet = getEdgeSet();
822  for (auto edge : edgeSet)
823  {
824  partitionMap.at(index)->addEdge(edge);
825  index++;
826  index = index % numberOfPartitions;
827  }
828  }
829 
830  template <typename T>
831  void Graph<T>::HDRFPartition(PartitionMap<T> &partitionMap) const
832  {
833  }
834 
835  template <typename T>
836  const AdjacencyMatrix<T> Graph<T>::getAdjMatrix() const
837  {
838  AdjacencyMatrix<T> adj;
839  auto edgeSetIt = edgeSet.begin();
840  for (edgeSetIt; edgeSetIt != edgeSet.end(); ++edgeSetIt)
841  {
842  if ((*edgeSetIt)->isDirected().has_value() && (*edgeSetIt)->isDirected().value())
843  {
844  const DirectedEdge<T> *d_edge = dynamic_cast<const DirectedEdge<T> *>(*edgeSetIt);
845  addElementToAdjMatrix(adj, &(d_edge->getFrom()), &(d_edge->getTo()), d_edge);
846  }
847  else if ((*edgeSetIt)->isDirected().has_value() && !(*edgeSetIt)->isDirected().value())
848  {
849  const UndirectedEdge<T> *ud_edge = dynamic_cast<const UndirectedEdge<T> *>(*edgeSetIt);
850  ;
851  addElementToAdjMatrix(adj, &(ud_edge->getNode1()), &(ud_edge->getNode2()), ud_edge);
852  addElementToAdjMatrix(adj, &(ud_edge->getNode2()), &(ud_edge->getNode1()), ud_edge);
853  }
854  else
855  { //is a simple edge we cannot create adj matrix
856  return adj;
857  }
858  }
859  return adj;
860  }
861 
862  template <typename T>
863  const DijkstraResult Graph<T>::dijkstra(const Node<T> &source, const Node<T> &target) const
864  {
865  DijkstraResult result;
866  result.success = false;
867  result.errorMessage = "";
868  result.result = INF_DOUBLE;
869  auto nodeSet = getNodeSet();
870  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
871  {
872  // check if source node exist in the graph
873  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
874  return result;
875  }
876  if (std::find(nodeSet.begin(), nodeSet.end(), &target) == nodeSet.end())
877  {
878  // check if target node exist in the graph
879  result.errorMessage = ERR_TARGET_NODE_NOT_IN_GRAPH;
880  return result;
881  }
882  const AdjacencyMatrix<T> adj = getAdjMatrix();
883  // n denotes the number of vertices in graph
884  int n = adj.size();
885 
886  // setting all the distances initially to INF_DOUBLE
887  std::map<const Node<T> *, double> dist;
888 
889  for (auto elem : adj)
890  {
891  dist[elem.first] = INF_DOUBLE;
892  }
893 
894  // creating a min heap using priority queue
895  // first element of pair contains the distance
896  // second element of pair contains the vertex
897  std::priority_queue<std::pair<double, const Node<T> *>, std::vector<std::pair<double, const Node<T> *>>,
898  std::greater<std::pair<double, const Node<T> *>>>
899  pq;
900 
901  // pushing the source vertex 's' with 0 distance in min heap
902  pq.push(std::make_pair(0.0, &source));
903 
904  // marking the distance of source as 0
905  dist[&source] = 0;
906 
907  while (!pq.empty())
908  {
909  // second element of pair denotes the node / vertex
910  const Node<T> *currentNode = pq.top().second;
911 
912  // first element of pair denotes the distance
913  double currentDist = pq.top().first;
914 
915  pq.pop();
916 
917  // for all the reachable vertex from the currently exploring vertex
918  // we will try to minimize the distance
919  if (adj.find(currentNode) != adj.end())
920  {
921  for (std::pair<const Node<T> *, const Edge<T> *> elem : adj.at(currentNode))
922  {
923  // minimizing distances
924  if (elem.second->isWeighted().has_value() && elem.second->isWeighted().value())
925  {
926  if (elem.second->isDirected().has_value() && elem.second->isDirected().value())
927  {
928  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>(elem.second);
929  if (currentDist + dw_edge->getWeight() < dist[elem.first])
930  {
931  dist[elem.first] = currentDist + dw_edge->getWeight();
932  pq.push(std::make_pair(dist[elem.first], elem.first));
933  }
934  }
935  else if (elem.second->isDirected().has_value() && !elem.second->isDirected().value())
936  {
937  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>(elem.second);
938  if (currentDist + udw_edge->getWeight() < dist[elem.first])
939  {
940  dist[elem.first] = currentDist + udw_edge->getWeight();
941  pq.push(std::make_pair(dist[elem.first], elem.first));
942  }
943  }
944  else
945  {
946  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
947  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
948  return result;
949  }
950  }
951  else
952  {
953  // No Weighted Edge
954  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
955  return result;
956  }
957  }
958  }
959  }
960  if (dist[&target] != INF_DOUBLE)
961  {
962  result.success = true;
963  result.errorMessage = "";
964  result.result = dist[&target];
965  return result;
966  }
967  result.errorMessage = ERR_TARGET_NODE_NOT_REACHABLE;
968  result.result = -1;
969  return result;
970  }
971 
972  template <typename T>
973  const std::vector<Node<T>> Graph<T>::breadth_first_search(const Node<T> &start) const
974  {
975  // vector to keep track of visited nodes
976  std::vector<Node<T>> visited;
977  auto nodeSet = getNodeSet();
978  //check is exist node in the graph
979  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
980  {
981  return visited;
982  }
983  const AdjacencyMatrix<T> adj = getAdjMatrix();
984  // queue that stores vertices that need to be further explored
985  std::queue<const Node<T> *> tracker;
986 
987  // mark the starting node as visited
988  visited.push_back(start);
989  tracker.push(&start);
990  while (!tracker.empty())
991  {
992  const Node<T> *node = tracker.front();
993  tracker.pop();
994  if (adj.find(node) != adj.end())
995  {
996  for (auto elem : adj.at(node))
997  {
998  // if the node is not visited then mark it as visited
999  // and push it to the queue
1000  if (std::find(visited.begin(), visited.end(), *(elem.first)) == visited.end())
1001  {
1002  visited.push_back(*(elem.first));
1003  tracker.push(elem.first);
1004  }
1005  }
1006  }
1007  }
1008 
1009  return visited;
1010  }
1011 
1012  template <typename T>
1013  const std::vector<Node<T>> Graph<T>::depth_first_search(const Node<T> &start) const
1014  {
1015  // vector to keep track of visited nodes
1016  std::vector<Node<T>> visited;
1017  auto nodeSet = getNodeSet();
1018  //check is exist node in the graph
1019  if (std::find(nodeSet.begin(), nodeSet.end(), &start) == nodeSet.end())
1020  {
1021  return visited;
1022  }
1023  const AdjacencyMatrix<T> adj = getAdjMatrix();
1024  std::function<void(const AdjacencyMatrix<T> &, const Node<T> &, std::vector<Node<T>> &)> explore;
1025  explore = [&explore](const AdjacencyMatrix<T> &adj, const Node<T> &node, std::vector<Node<T>> &visited) -> void
1026  {
1027  visited.push_back(node);
1028  if (adj.find(&node) != adj.end())
1029  {
1030  for (auto x : adj.at(&node))
1031  {
1032  if (std::find(visited.begin(), visited.end(), *(x.first)) == visited.end())
1033  {
1034  explore(adj, *(x.first), visited);
1035  }
1036  }
1037  }
1038  };
1039  explore(adj, start, visited);
1040 
1041  return visited;
1042  }
1043 
1044  template <typename T>
1046  {
1047  if (!isDirectedGraph())
1048  {
1049  return false;
1050  }
1051  enum nodeStates : uint8_t
1052  {
1053  not_visited,
1054  in_stack,
1055  visited
1056  };
1057  auto nodeSet = this->getNodeSet();
1058  auto adjMatrix = this->getAdjMatrix();
1059 
1060  /* State of the node.
1061  *
1062  * It is a vector of "nodeStates" which represents the state node is in.
1063  * It can take only 3 values: "not_visited", "in_stack", and "visited".
1064  *
1065  * Initially, all nodes are in "not_visited" state.
1066  */
1067  std::map<unsigned long, nodeStates> state;
1068  for (auto node : nodeSet)
1069  {
1070  state[node->getId()] = not_visited;
1071  }
1072  int stateCounter = 0;
1073 
1074  // Start visiting each node.
1075  for (auto node : nodeSet)
1076  {
1077  // If a node is not visited, only then check for presence of cycle.
1078  // There is no need to check for presence of cycle for a visited
1079  // node as it has already been checked for presence of cycle.
1080  if (state[node->getId()] == not_visited)
1081  {
1082  // Check for cycle.
1083  std::function<bool(AdjacencyMatrix<T> &, std::map<unsigned long, nodeStates> &, const Node<T> *)> isCyclicDFSHelper;
1084  isCyclicDFSHelper = [this, &isCyclicDFSHelper](AdjacencyMatrix<T> &adjMatrix, std::map<unsigned long, nodeStates> &states, const Node<T> *node)
1085  {
1086  // Add node "in_stack" state.
1087  states[node->getId()] = in_stack;
1088 
1089  // If the node has children, then recursively visit all children of the
1090  // node.
1091  auto const it = adjMatrix.find(node);
1092  if (it != adjMatrix.end())
1093  {
1094  for (auto child : it->second)
1095  {
1096  // If state of child node is "not_visited", evaluate that child
1097  // for presence of cycle.
1098  auto state_of_child = states.at((std::get<0>(child))->getId());
1099  if (state_of_child == not_visited)
1100  {
1101  if (isCyclicDFSHelper(adjMatrix, states, std::get<0>(child)))
1102  {
1103  return true;
1104  }
1105  }
1106  else if (state_of_child == in_stack)
1107  {
1108  // If child node was "in_stack", then that means that there
1109  // is a cycle in the graph. Return true for presence of the
1110  // cycle.
1111  return true;
1112  }
1113  }
1114  }
1115 
1116  // Current node has been evaluated for the presence of cycle and had no
1117  // cycle. Mark current node as "visited".
1118  states[node->getId()] = visited;
1119  // Return that current node didn't result in any cycles.
1120  return false;
1121  };
1122  if (isCyclicDFSHelper(adjMatrix, state, node))
1123  {
1124  return true;
1125  }
1126  }
1127  }
1128 
1129  // All nodes have been safely traversed, that means there is no cycle in
1130  // the graph. Return false.
1131  return false;
1132  }
1133 
1134  template <typename T>
1136  {
1137  if (!isDirectedGraph())
1138  {
1139  return false;
1140  }
1141  auto adjMatrix = this->getAdjMatrix();
1142  auto nodeSet = this->getNodeSet();
1143 
1144  std::map<unsigned long, unsigned int> indegree;
1145  for (auto node : nodeSet)
1146  {
1147  indegree[node->getId()] = 0;
1148  }
1149  // Calculate the indegree i.e. the number of incident edges to the node.
1150  for (auto const &list : adjMatrix)
1151  {
1152  auto children = list.second;
1153  for (auto const &child : children)
1154  {
1155  indegree[std::get<0>(child)->getId()]++;
1156  }
1157  }
1158 
1159  std::queue<const Node<T> *> can_be_solved;
1160  for (auto node : nodeSet)
1161  {
1162  // If a node doesn't have any input edges, then that node will
1163  // definately not result in a cycle and can be visited safely.
1164  if (!indegree[node->getId()])
1165  {
1166  can_be_solved.emplace(&(*node));
1167  }
1168  }
1169 
1170  // Vertices that need to be traversed.
1171  auto remain = this->getNodeSet().size();
1172  // While there are safe nodes that we can visit.
1173  while (!can_be_solved.empty())
1174  {
1175  auto solved = can_be_solved.front();
1176  // Visit the node.
1177  can_be_solved.pop();
1178  // Decrease number of nodes that need to be traversed.
1179  remain--;
1180 
1181  // Visit all the children of the visited node.
1182  auto it = adjMatrix.find(solved);
1183  if (it != adjMatrix.end())
1184  {
1185  for (auto child : it->second)
1186  {
1187  // Check if we can visited the node safely.
1188  if (--indegree[std::get<0>(child)->getId()] == 0)
1189  {
1190  // if node can be visited safely, then add that node to
1191  // the visit queue.
1192  can_be_solved.emplace(std::get<0>(child));
1193  }
1194  }
1195  }
1196  }
1197 
1198  // If there are still nodes that we can't visit, then it means that
1199  // there is a cycle and return true, else return false.
1200  return !(remain == 0);
1201  }
1202 
1203  template <typename T>
1205  {
1206  auto edgeSet = this->getEdgeSet();
1207  for (auto edge : edgeSet)
1208  {
1209  if (!(edge->isDirected().has_value() && edge->isDirected().value()))
1210  {
1211  //Found Undirected Edge
1212  return false;
1213  }
1214  }
1215  //No Undirected Edge
1216  return true;
1217  }
1218 
1219  template <typename T>
1220  const DialResult Graph<T>::dial(const Node<T> &source, int maxWeight) const
1221  {
1222  DialResult result;
1223  result.success = false;
1224 
1225  auto adj = getAdjMatrix();
1226  auto nodeSet = getNodeSet();
1227 
1228  if (std::find(nodeSet.begin(), nodeSet.end(), &source) == nodeSet.end())
1229  {
1230  // check if source node exist in the graph
1231  result.errorMessage = ERR_SOURCE_NODE_NOT_IN_GRAPH;
1232  return result;
1233  }
1234  /* With each distance, iterator to that vertex in
1235  its bucket is stored so that vertex can be deleted
1236  in O(1) at time of updation. So
1237  dist[i].first = distance of ith vertex from src vertex
1238  dits[i].second = vertex i in bucket number */
1239  unsigned int V = nodeSet.size();
1240  std::map<const Node<T> *, std::pair<long, const Node<T> *>> dist;
1241 
1242  // Initialize all distances as infinite (INF)
1243  for (auto node : nodeSet)
1244  {
1245  dist[&(*node)].first = std::numeric_limits<long>::max();
1246  }
1247 
1248  // Create buckets B[].
1249  // B[i] keep vertex of distance label i
1250  std::list<const Node<T> *> B[maxWeight * V + 1];
1251 
1252  B[0].push_back(&source);
1253  dist[&source].first = 0;
1254 
1255  int idx = 0;
1256  while (1)
1257  {
1258  // Go sequentially through buckets till one non-empty
1259  // bucket is found
1260  while (B[idx].size() == 0 && idx < maxWeight * V)
1261  {
1262  idx++;
1263  }
1264 
1265  // If all buckets are empty, we are done.
1266  if (idx == maxWeight * V)
1267  {
1268  break;
1269  }
1270 
1271  // Take top vertex from bucket and pop it
1272  auto u = B[idx].front();
1273  B[idx].pop_front();
1274 
1275  // Process all adjacents of extracted vertex 'u' and
1276  // update their distanced if required.
1277  for (auto i = adj[u].begin(); i != adj[u].end(); ++i)
1278  {
1279  auto v = (*i).first;
1280  int weight = 0;
1281  if ((*i).second->isWeighted().has_value() && (*i).second->isWeighted().value())
1282  {
1283  if ((*i).second->isDirected().has_value() && (*i).second->isDirected().value())
1284  {
1285  const DirectedWeightedEdge<T> *dw_edge = dynamic_cast<const DirectedWeightedEdge<T> *>((*i).second);
1286  weight = dw_edge->getWeight();
1287  }
1288  else if ((*i).second->isDirected().has_value() && !(*i).second->isDirected().value())
1289  {
1290  const UndirectedWeightedEdge<T> *udw_edge = dynamic_cast<const UndirectedWeightedEdge<T> *>((*i).second);
1291  weight = udw_edge->getWeight();
1292  }
1293  else
1294  {
1295  //ERROR it shouldn't never returned ( does not exist a Node Weighted and not Directed/Undirected)
1296  result.errorMessage = ERR_NO_DIR_OR_UNDIR_EDGE;
1297  return result;
1298  }
1299  }
1300  else
1301  {
1302  // No Weighted Edge
1303  result.errorMessage = ERR_NO_WEIGHTED_EDGE;
1304  return result;
1305  }
1306  auto u_i = std::find_if(dist.begin(), dist.end(), [u](std::pair<const Node<T> *, std::pair<long, const Node<T> *>> const &it)
1307  { return (*u == *(it.first)); });
1308 
1309  auto v_i = std::find_if(dist.begin(), dist.end(), [v](std::pair<const Node<T> *, std::pair<long, const Node<T> *>> const &it)
1310  { return (*v == *(it.first)); });
1311  long du = u_i->second.first;
1312  long dv = v_i->second.first;
1313 
1314  // If there is shorted path to v through u.
1315  if (dv > du + weight)
1316  {
1317  // If dv is not INF then it must be in B[dv]
1318  // bucket, so erase its entry using iterator
1319  // in O(1)
1320  if (dv != std::numeric_limits<long>::max())
1321  {
1322  auto findIter = std::find(B[dv].begin(), B[dv].end(), dist[v].second);
1323  B[dv].erase(findIter);
1324  }
1325 
1326  // updating the distance
1327  dist[v].first = du + weight;
1328  dv = dist[v].first;
1329 
1330  // pushing vertex v into updated distance's bucket
1331  B[dv].push_front(v);
1332 
1333  // storing updated iterator in dist[v].second
1334  dist[v].second = *(B[dv].begin());
1335  }
1336  }
1337  }
1338  for (auto dist_i : dist)
1339  {
1340  result.minDistanceMap[dist_i.first->getId()] = dist_i.second.first;
1341  }
1342  result.success = true;
1343 
1344  return result;
1345  }
1346 
1347  template <typename T>
1348  int Graph<T>::writeToFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool writeNodeFeat, bool writeEdgeWeight) const
1349  {
1350  int result = 0;
1351  if (format == InputOutputFormat::STANDARD_CSV)
1352  {
1353  result = writeToStandardFile_csv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1354  }
1355  else if (format == InputOutputFormat::STANDARD_TSV)
1356  {
1357  result = writeToStandardFile_tsv(workingDir, OFileName, compress, writeNodeFeat, writeEdgeWeight);
1358  }
1359  else
1360  {
1361  //OUTPUT FORMAT NOT RECOGNIZED
1362  return -1;
1363  }
1364  if (result == 0 && compress)
1365  {
1366  auto compress = [this, &workingDir, &OFileName, &writeNodeFeat, &writeEdgeWeight](const std::string &extension)
1367  {
1368  std::string completePathToFileGraph = workingDir + "/" + OFileName + extension;
1369  std::string completePathToFileGraphCompressed = workingDir + "/" + OFileName + extension + ".gz";
1370  int _result = compressFile(completePathToFileGraph, completePathToFileGraphCompressed);
1371  if (_result == 0)
1372  {
1373  _result = remove(completePathToFileGraph.c_str());
1374  }
1375  if (_result == 0)
1376  {
1377  if (writeNodeFeat)
1378  {
1379  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat" + extension;
1380  std::string completePathToFileNodeFeatCompressed = workingDir + "/" + OFileName + "_NodeFeat" + extension + ".gz";
1381  _result = compressFile(completePathToFileNodeFeat, completePathToFileNodeFeatCompressed);
1382  if (_result == 0)
1383  {
1384  _result = remove(completePathToFileNodeFeat.c_str());
1385  }
1386  }
1387  }
1388  if (_result == 0)
1389  {
1390  if (writeEdgeWeight)
1391  {
1392  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight" + extension;
1393  std::string completePathToFileEdgeWeightCompressed = workingDir + "/" + OFileName + "_EdgeWeight" + extension + ".gz";
1394  _result = compressFile(completePathToFileEdgeWeight, completePathToFileEdgeWeightCompressed);
1395  if (_result == 0)
1396  {
1397  _result = remove(completePathToFileEdgeWeight.c_str());
1398  }
1399  }
1400  }
1401  return _result;
1402  };
1403  if (format == InputOutputFormat::STANDARD_CSV)
1404  {
1405  auto result = compress(".csv");
1406  }
1407  else if (format == InputOutputFormat::STANDARD_TSV)
1408  {
1409  auto result = compress(".tsv");
1410  }
1411  else
1412  {
1413  //OUTPUT FORMAT NOT RECOGNIZED
1414  result = -1;
1415  }
1416  }
1417  return result;
1418  }
1419 
1420  template <typename T>
1421  int Graph<T>::readFromFile(InputOutputFormat format, const std::string &workingDir, const std::string &OFileName, bool compress, bool readNodeFeat, bool readEdgeWeight)
1422  {
1423  int result = 0;
1424  if (compress)
1425  {
1426  auto decompress = [this, &workingDir, &OFileName, &readNodeFeat, &readEdgeWeight](const std::string &extension)
1427  {
1428  std::string completePathToFileGraph = workingDir + "/" + OFileName + extension;
1429  std::string completePathToFileGraphCompressed = workingDir + "/" + OFileName + extension + ".gz";
1430  int _result = decompressFile(completePathToFileGraphCompressed, completePathToFileGraph);
1431  if (_result == 0)
1432  {
1433  if (readNodeFeat)
1434  {
1435  std::string completePathToFileNodeFeat = workingDir + "/" + OFileName + "_NodeFeat" + extension;
1436  std::string completePathToFileNodeFeatCompressed = workingDir + "/" + OFileName + "_NodeFeat" + extension + ".gz";
1437  _result = decompressFile(completePathToFileNodeFeatCompressed, completePathToFileNodeFeat);
1438  }
1439  }
1440  if (_result == 0)
1441  {
1442  if (readEdgeWeight)
1443  {
1444  std::string completePathToFileEdgeWeight = workingDir + "/" + OFileName + "_EdgeWeight" + extension;
1445  std::string completePathToFileEdgeWeightCompressed = workingDir + "/" + OFileName + "_EdgeWeight" + extension + ".gz";
1446  _result = decompressFile(completePathToFileEdgeWeightCompressed, completePathToFileEdgeWeight);
1447  }
1448  }
1449  return _result;
1450  };
1451  if (format == InputOutputFormat::STANDARD_CSV)
1452  {
1453  result = decompress(".csv");
1454  }
1455  else if (format == InputOutputFormat::STANDARD_TSV)
1456  {
1457  result = decompress(".tsv");
1458  }
1459  else
1460  {
1461  //OUTPUT FORMAT NOT RECOGNIZED
1462  result = -1;
1463  }
1464  }
1465  if (result == 0)
1466  {
1467  if (format == InputOutputFormat::STANDARD_CSV)
1468  {
1469  result = readFromStandardFile_csv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1470  }
1471  else if (format == InputOutputFormat::STANDARD_TSV)
1472  {
1473  result = readFromStandardFile_tsv(workingDir, OFileName, compress, readNodeFeat, readEdgeWeight);
1474  }
1475  else
1476  {
1477  //OUTPUT FORMAT NOT RECOGNIZED
1478  result = -1;
1479  }
1480  }
1481  return result;
1482  }
1483 
1484  template <typename T>
1485  PartitionMap<T> Graph<T>::partitionGraph(PARTITIONING::PartitionAlgorithm algorithm, unsigned int numberOfPartitions) const
1486  {
1487  PartitionMap<T> partitionMap;
1488  for (unsigned int i = 0; i < numberOfPartitions; ++i)
1489  {
1490  partitionMap[i] = new PARTITIONING::Partition<T>(i);
1491  }
1492  if (algorithm == PARTITIONING::PartitionAlgorithm::GREEDY_VC_ALG)
1493  {
1494  greedyPartition(partitionMap);
1495  }
1496  else if (algorithm == PARTITIONING::PartitionAlgorithm::HDRF_ALG)
1497  {
1498  HDRFPartition(partitionMap);
1499  }
1500  else
1501  {
1502  //Error not recognized algorithm
1503  partitionMap.clear();
1504  }
1505  return partitionMap;
1506  }
1507 
1508 
1509  template <typename T>
1510  std::ostream &operator<<(std::ostream &os, const AdjacencyMatrix<T> &adj)
1511  {
1512  os << "Adjacency Matrix:\n";
1513  auto it = adj.begin();
1514  unsigned long max_column = 0;
1515  for (it; it != adj.end(); ++it)
1516  {
1517  if (it->second.size() > max_column)
1518  {
1519  max_column = it->second.size();
1520  }
1521  }
1522  if (max_column == 0)
1523  {
1524  os << "ERROR in Print\n";
1525  return os;
1526  }
1527  else
1528  {
1529  it = adj.begin();
1530  os << "|--|";
1531  for (int i = 0; i < max_column; i++)
1532  {
1533  os << "-----|";
1534  }
1535  os << "\n";
1536  for (it; it != adj.end(); ++it)
1537  {
1538  os << "|N" << it->first->getId() << "|";
1539  auto it2 = it->second.begin();
1540  for (it2; it2 != it->second.end(); ++it2)
1541  {
1542  os << "N" << it2->first->getId() << ",E" << it2->second->getId() << "|";
1543  }
1544  os << "\n|--|";
1545  for (int i = 0; i < max_column; i++)
1546  {
1547  os << "-----|";
1548  }
1549  os << "\n";
1550  }
1551  }
1552  return os;
1553  }
1554 
1555 } // namespace CXXGRAPH
1556 #endif // __GRAPH_H__
Definition: DirectedEdge.hpp:39
Definition: DirectedWeightedEdge.hpp:42
Definition: Edge.hpp:40
Class that implement the Graph. ( This class is not Thread Safe )
Definition: Graph.hpp:76
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:1013
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:307
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:368
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:1135
virtual void removeEdge(unsigned long edgeId)
Function remove an Edge from the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:337
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:1348
virtual bool isDirectedGraph() const
This function checks if a graph is directed Note: No Thread Safe.
Definition: Graph.hpp:1204
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:1220
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:863
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:1045
virtual void addEdge(const Edge< T > *edge)
Function add an Edge to the Graph Edge Set Note: No Thread Safe.
Definition: Graph.hpp:327
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:1485
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:1421
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:836
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:348
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:973
virtual void setEdgeSet(std::list< const Edge< T > * > &edgeSet)
Function set the Edge Set of the Graph Note: No Thread Safe.
Definition: Graph.hpp:313
Definition: Node.hpp:35
Definition: Partition.hpp:38
Definition: UndirectedEdge.hpp:39
Definition: UndirectedWeightedEdge.hpp:43
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:62