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

Public Member Functions | Friends | List of all members
CXXGRAPH::Graph< T > Class Template Reference

Class that implement the Graph. ( This class is not Thread Safe ) More...

`#include <Graph.hpp>`

Inheritance diagram for CXXGRAPH::Graph< T >:
[legend]

## Public Member Functions
| Graph (const T_EdgeSet< T > &edgeSet)
virtual const T_EdgeSet< T > & | getEdgeSet () const
| Function that return the Edge set of the Graph Note: No Thread Safe. More...
virtual void | setEdgeSet (T_EdgeSet< T > &edgeSet)
| Function set the Edge Set of the Graph Note: No Thread Safe. More...
virtual void | addEdge (const Edge< T > *edge)
| Function add an Edge to the Graph Edge Set Note: No Thread Safe. More...
virtual void | removeEdge (unsigned long long edgeId)
| Function remove an Edge from the Graph Edge Set Note: No Thread Safe. More...
virtual const std::set< const Node< T > * > | getNodeSet () const
| Function that return the Node Set of the Graph Note: No Thread Safe. More...
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. More...
virtual const AdjacencyMatrix< T > | getAdjMatrix () const
| This function generate a list of adjacency matrix with every element of the matrix contain the node where is directed the link and the Edge corrispondent to the link Note: No Thread Safe.
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 of the node & values is the subset. More...
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. More...
virtual std::vector< Node< T > > | eulerianPath () const
| This function finds the eulerian path of a directed graph using hierholzers algorithm. More...
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 the shortest distance of target from the source. Note: No Thread Safe. More...
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 returns the shortest distance of target from the source. It can also detect if a negative cycle exists in the graph. Note: No Thread Safe. More...
virtual const FWResult | floydWarshall () const
| Function runs the floyd-warshall algorithm and returns the shortest distance of all pair of nodes. It can also detect if a negative cycle exists in the graph. Note: No Thread Safe. More...
virtual const MstResult | prim () const
| Function runs the prim algorithm and returns the minimum spanning tree if the graph is undirected. Note: No Thread Safe. More...
virtual const MstResult | boruvka () const
| Function runs the boruvka algorithm and returns the minimum spanning tree & cost if the graph is undirected. Note: No Thread Safe. More...
virtual const MstResult | kruskal () const
| Function runs the kruskal algorithm and returns the minimum spanning tree if the graph is undirected. Note: No Thread Safe. More...
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. More...
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. More...
virtual bool | isCyclicDirectedGraphDFS () const
| This function uses DFS to check for cycle in the graph. Pay Attention, this function work only with directed Graph Note: No Thread Safe. More...
virtual bool | isCyclicDirectedGraphBFS () const
| This function uses BFS to check for cycle in the graph. Pay Attention, this function work only with directed Graph Note: No Thread Safe. More...
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. More...
virtual bool | containsCycle (const T_EdgeSet< T > *edgeSet, std::unordered_map< unsigned long long, Subset > *) const
| This function checks if the given Subset forms a cycle or not using union-find method. More...
virtual bool | isDirectedGraph () const
| This function checks if a graph is directed Note: No Thread Safe. More...
virtual bool | isUndirectedGraph () const
| This function checks if a graph is undirected Note: No Thread Safe. More...
virtual bool | isConnectedGraph () const
| This function checks if the graph is connected or not Applicable for Undirected Graph, for Directed Graph use the isStronglyConnectedGraph() function. More...
virtual bool | isStronglyConnectedGraph () const
| This function checks if the graph is strongly connected or not Applicable for Directed Graph, for Undirected Graph use the isConnectedGraph() function. More...
virtual std::vector< std::vector< Node< T > > > | kosaraju () const
| This function performs performs the kosaraju algorthm on the graph to find the strongly connected components. More...
virtual const std::vector< Node< T > > | graph_slicing (const Node< T > &start) const
| This function performs Graph Slicing based on connectivity. More...
virtual const DialResult | dial (const Node< T > &source, int maxWeight) const
| This function write the graph in an output file Note: No Thread Safe. More...
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 returns the maximum flow of the graph. More...
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. More...
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. More...
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. More...

## Friends
std::ostream & | operator<< (std::ostream &os, const Graph< T > &graph)
std::ostream & | operator<< (std::ostream &os, const AdjacencyMatrix< T > &adj)

## Detailed Description

### template<typename T>
class CXXGRAPH::Graph< T >

Class that implement the Graph. ( This class is not Thread Safe )

## Member Function Documentation

## ◆ addEdge()

template<typename T >

void CXXGRAPH::Graph< T >::addEdge | ( | const Edge< T > * | edge | ) |
| virtual

Function add an Edge to the Graph Edge Set Note: No Thread Safe.

Parameters

  edge | The Edge to insert

## ◆ bellmanford()

template<typename T >

const BellmanFordResult CXXGRAPH::Graph< T >::bellmanford | ( | const Node< T > & | source,
|  | const Node< T > & | target
| ) |  | const
| virtual

Function runs the bellman-ford algorithm for some source node and target node in the graph and returns the shortest distance of target from the source. It can also detect if a negative cycle exists in the graph. Note: No Thread Safe.

Parameters

  source | source vertex
  target | target vertex

Returns
  shortest distance if target is reachable from source else ERROR in case if target is not reachable from source. If there is no error then also returns if the graph contains a negative cycle.

## ◆ boruvka()

template<typename T >

const MstResult CXXGRAPH::Graph< T >::boruvka
| virtual

Function runs the boruvka algorithm and returns the minimum spanning tree & cost if the graph is undirected. Note: No Thread Safe.

Returns
  struct of type MstResult with following fields success: true if algorithm completed successfully ELSE false mst: vector containing id of nodes in minimum spanning tree & cost of MST mstCost: Cost of MST errorMessage: "" if no error ELSE report the encountered error

## ◆ breadth_first_search()

template<typename T >

const std::vector< Node< T > > CXXGRAPH::Graph< T >::breadth_first_search | ( | const Node< T > & | start | ) | const
| virtual

Function performs the breadth first search algorithm over the graph Note: No Thread Safe.

Parameters

  start | Node from where traversing starts

Returns
  a vector of Node indicating which Node were visited during the search.

## ◆ containsCycle() [1/2]

template<typename T >

bool CXXGRAPH::Graph< T >::containsCycle | ( | const T_EdgeSet< T > * | edgeSet | ) | const
| virtual

This function checks if the given set of edges forms a cycle or not using union-find method.

Returns
  true if a cycle is detected, else false

## ◆ containsCycle() [2/2]

template<typename T >

bool CXXGRAPH::Graph< T >::containsCycle | ( | const T_EdgeSet< T > * | edgeSet,
|  | std::unordered_map< unsigned long long, Subset > * | subset
| ) |  | const
| virtual

This function checks if the given Subset forms a cycle or not using union-find method.

Returns
  true if a cycle is detected, else false

## ◆ depth_first_search()

template<typename T >

const std::vector< Node< T > > CXXGRAPH::Graph< T >::depth_first_search | ( | const Node< T > & | start | ) | const
| virtual

Function performs the depth first search algorithm over the graph Note: No Thread Safe.

Parameters

  start | Node from where traversing starts

Returns
  a vector of Node indicating which Node were visited during the search.

## ◆ dial()

template<typename T >

const DialResult CXXGRAPH::Graph< T >::dial | ( | const Node< T > & | source,
|  | int | maxWeight
| ) |  | const
| virtual

This function write the graph in an output file Note: No Thread Safe.

Parameters

  format | The Output format of the file
  workingDir | The path to the directory in which will be placed the output file
  OFileName | The Output File Name ( )
  compress | Indicates if the output will be compressed
  writeNodeFeat | Indicates if export also Node Features
  writeEdgeWeight | Indicates if export also Edge Weights

Returns
  0 if all OK, else return a negative value

Function runs the Dial algorithm (Optimized Dijkstra for small range weights) for some source node and target node in the graph and returns the shortest distance of target from the source. Note: No Thread Safe

Parameters

  source | source vertex
  maxWeight | maximum weight of the edge

Returns
  shortest distance for all nodes reachable from source else ERROR in case there is error in the computation.

## ◆ dijkstra()

template<typename T >

const DijkstraResult CXXGRAPH::Graph< T >::dijkstra | ( | const Node< T > & | source,
|  | const Node< T > & | target
| ) |  | const
| virtual

Function runs the dijkstra algorithm for some source node and target node in the graph and returns the shortest distance of target from the source. Note: No Thread Safe.

Parameters

  source | source vertex
  target | target vertex

Returns
  shortest distance if target is reachable from source else ERROR in case if target is not reachable from source or there is error in the computation.

## ◆ eulerianPath()

template<typename T >

std::vector< Node< T > > CXXGRAPH::Graph< T >::eulerianPath
| virtual

This function finds the eulerian path of a directed graph using hierholzers algorithm.

Returns
  a vector containing nodes in eulerian path Note: No Thread Safe

## ◆ floydWarshall()

template<typename T >

const FWResult CXXGRAPH::Graph< T >::floydWarshall
| virtual

Function runs the floyd-warshall algorithm and returns the shortest distance of all pair of nodes. It can also detect if a negative cycle exists in the graph. Note: No Thread Safe.

Returns
  a map whose keys are node ids and values are the shortest distance. If there is no error then also returns if the graph contains a negative cycle.

## ◆ fordFulkersonMaxFlow()

template<typename T >

double CXXGRAPH::Graph< T >::fordFulkersonMaxFlow | ( | const Node< T > & | source,
|  | const Node< T > & | target
| ) |  | const
| virtual

Function runs the Ford-Fulkerson algorithm for some source node and target node in the graph and returns the maximum flow of the graph.

Parameters

  source | source vertex
  target | target vertex

Returns
  double Max-Flow value or -1 in case of error

## ◆ getEdge()

template<typename T >

const std::optional< const Edge< T > * > CXXGRAPH::Graph< T >::getEdge | ( | unsigned long long | edgeId | ) | const
| virtual

Function that return an Edge with specific ID if Exist in the Graph Note: No Thread Safe.

Parameters

  edgeId | The Edge Id to return

Returns
  the Edge if exist

## ◆ getEdgeSet()

template<typename T >

const T_EdgeSet< T > & CXXGRAPH::Graph< T >::getEdgeSet
| virtual

Function that return the Edge set of the Graph Note: No Thread Safe.

Returns
  a list of Edges of the graph

## ◆ getNodeSet()

template<typename T >

const std::set< const Node< T > * > CXXGRAPH::Graph< T >::getNodeSet
| virtual

Function that return the Node Set of the Graph Note: No Thread Safe.

Returns
  a list of Nodes of the graph

## ◆ graph_slicing()

template<typename T >

const std::vector< Node< T > > CXXGRAPH::Graph< T >::graph_slicing | ( | const Node< T > & | start | ) | const
| virtual

This function performs Graph Slicing based on connectivity.

Mathematical definition of the problem:

Let G be the set of nodes in a graph and n be a given node in that set. Let C be the non-strict subset of G containing both n and all nodes reachable from n, and let C' be its complement. There's a third set M, which is the non-strict subset of C containing all nodes that are reachable from any node in C'. The problem consists of finding all nodes that belong to C but not to M.

Note: No Thread Safe

Parameters

  start | Node from where traversing starts

Returns
  a vector of nodes that belong to C but not to M.

## ◆ isConnectedGraph()

template<typename T >

bool CXXGRAPH::Graph< T >::isConnectedGraph
| virtual

This function checks if the graph is connected or not Applicable for Undirected Graph, for Directed Graph use the isStronglyConnectedGraph() function.

Returns
  true if the graph is connected
  false otherwise

## ◆ isCyclicDirectedGraphBFS()

template<typename T >

bool CXXGRAPH::Graph< T >::isCyclicDirectedGraphBFS
| virtual

This function uses BFS to check for cycle in the graph. Pay Attention, this function work only with directed Graph Note: No Thread Safe.

Returns
  true if a cycle is detected, else false. ( false is returned also if the graph in indirected)

## ◆ isCyclicDirectedGraphDFS()

template<typename T >

bool CXXGRAPH::Graph< T >::isCyclicDirectedGraphDFS
| virtual

This function uses DFS to check for cycle in the graph. Pay Attention, this function work only with directed Graph Note: No Thread Safe.

Returns
  true if a cycle is detected, else false. ( false is returned also if the graph in indirected)

## ◆ isDirectedGraph()

template<typename T >

bool CXXGRAPH::Graph< T >::isDirectedGraph
| virtual

This function checks if a graph is directed Note: No Thread Safe.

Returns
  true if the graph is directed, else false.

## ◆ isStronglyConnectedGraph()

template<typename T >

bool CXXGRAPH::Graph< T >::isStronglyConnectedGraph
| virtual

This function checks if the graph is strongly connected or not Applicable for Directed Graph, for Undirected Graph use the isConnectedGraph() function.

Returns
  true if the graph is connected
  false otherwise

## ◆ isUndirectedGraph()

template<typename T >

bool CXXGRAPH::Graph< T >::isUndirectedGraph
| virtual

This function checks if a graph is undirected Note: No Thread Safe.

Returns
  true if the graph is undirected, else false.

## ◆ kosaraju()

template<typename T >

std::vector< std::vector< Node< T > > > CXXGRAPH::Graph< T >::kosaraju
| virtual

This function performs performs the kosaraju algorthm on the graph to find the strongly connected components.

Mathematical definition of the problem: A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.

Note: No Thread Safe

Returns
  a vector of vector of strongly connected components.

## ◆ kruskal()

template<typename T >

const MstResult CXXGRAPH::Graph< T >::kruskal
| virtual

Function runs the kruskal algorithm and returns the minimum spanning tree if the graph is undirected. Note: No Thread Safe.

Returns
  struct of type MstResult with following fields success: true if algorithm completed successfully ELSE false mst: vector containing id of nodes in minimum spanning tree & cost of MST mstCost: Cost of MST errorMessage: "" if no error ELSE report the encountered error

## ◆ partitionGraph()

template<typename T >

PartitionMap< T > CXXGRAPH::Graph< 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
| virtual

This function partition a graph in a set of partitions Note: No Thread Safe.

Parameters

  algorithm | The partition algorithm
  numberOfPartition | The number of partitions

Returns
  The partiton Map of the partitioned graph

## ◆ prim()

template<typename T >

const MstResult CXXGRAPH::Graph< T >::prim
| virtual

Function runs the prim algorithm and returns the minimum spanning tree if the graph is undirected. Note: No Thread Safe.

Returns
  a vector containing id of nodes in minimum spanning tree & cost of MST

## ◆ readFromFile()

template<typename T >

int CXXGRAPH::Graph< T >::readFromFile | ( | InputOutputFormat | format = `InputOutputFormat::STANDARD_CSV`,
|  | const std::string & | workingDir = `"."`,
|  | const std::string & | OFileName = `"graph"`,
|  | bool | compress = `false`,
|  | bool | readNodeFeat = `false`,
|  | bool | readEdgeWeight = `false`
| ) |  |
| virtual

This function read the graph from an input file Note: No Thread Safe.

Parameters

  format | The Input format of the file
  workingDir | The path to the directory in which is placed the Input file
  OFileName | The Input File Name ( )
  compress | Indicates if the Input is compressed
  readNodeFeat | Indicates if import also Node Features
  readEdgeWeight | Indicates if import also Edge Weights

Returns
  0 if all OK, else return a negative value

## ◆ removeEdge()

template<typename T >

void CXXGRAPH::Graph< T >::removeEdge | ( | unsigned long long | edgeId | ) |
| virtual

Function remove an Edge from the Graph Edge Set Note: No Thread Safe.

Parameters

  edgeId | The Edge Id to remove

## ◆ setEdgeSet()

template<typename T >

void CXXGRAPH::Graph< T >::setEdgeSet | ( | T_EdgeSet< T > & | edgeSet | ) |
| virtual

Function set the Edge Set of the Graph Note: No Thread Safe.

Parameters

  edgeSet | The Edge Set

## ◆ setFind()

template<typename T >

unsigned long long CXXGRAPH::Graph< T >::setFind | ( | std::unordered_map< unsigned long long, Subset > * | subsets,
|  | const unsigned long long | elem
| ) |  | const
| virtual

This function finds the subset of given a nodeId Subset is stored in a map where keys are the hash-id of the node & values is the subset.

Parameters

  subset | query subset, we want to find target in this subset
  elem | elem that we wish to find in the subset

Returns
  parent node of elem Note: No Thread Safe

## ◆ setUnion()

template<typename T >

void CXXGRAPH::Graph< T >::setUnion | ( | std::unordered_map< unsigned long long, Subset > * | subsets,
|  | const unsigned long long | set1,
|  | const unsigned long long | elem2
| ) |  | const
| virtual

This function modifies the original subset array such that it the union of two sets a and b.

Parameters

  subset | original subset is modified to obtain union of a & b
  a | parent id of set1
  b | parent id of set2 NOTE: Original subset is no longer available after union. Note: No Thread Safe

## ◆ writeToFile()

template<typename T >

int CXXGRAPH::Graph< T >::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
| virtual

This function write the graph in an output file Note: No Thread Safe.

Parameters

  format | The Output format of the file
  workingDir | The path to the directory in which is placed the Output file
  OFileName | The Output File Name ( )
  compress | Indicates if the Output will be compressed ( Pay Attention if compress flag is true, not compressed files will be deleted [ #48 ] )
  writeNodeFeat | Indicates if export also Node Features
  writeEdgeWeight | Indicates if export also Edge Weights

Returns
  0 if all OK, else return a negative value

The documentation for this class was generated from the following file:

- /github/workspace/include/Graph/Graph.hpp