| CXXGraph 0.4.0 CXXGraph is a header only, that manages the Graphs and it's algorithm in C++

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