CXXGraph  0.2.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 >:
Inheritance graph
[legend]

Public Member Functions

 Graph (const std::list< const Edge< T > * > &edgeSet)
 
virtual const std::list< const Edge< T > * > & getEdgeSet () const
 Function that return the Edge set of the Graph Note: No Thread Safe. More...
 
virtual void setEdgeSet (std::list< const Edge< 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 edgeId)
 Function remove an Edge from the Graph Edge Set Note: No Thread Safe. More...
 
virtual const std::list< 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 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 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 PrimResult 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 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 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 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 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) 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
edgeThe Edge to insert

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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
sourcesource vertex
targettarget 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.

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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
startNode from where traversing starts
Returns
a vector of Node indicating which Node were visited during the search.

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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
startNode from where traversing starts
Returns
a vector of Node indicating which Node were visited during the search.

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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
formatThe Output format of the file
workingDirThe path to the directory in which will be placed the output file
OFileNameThe Output File Name ( )
compressIndicates if the output will be compressed
writeNodeFeatIndicates if export also Node Features
writeEdgeWeightIndicates 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
sourcesource vertex
maxWeightmaximum weight of the edge
Returns
shortest distance for all nodes reachable from source else ERROR in case there is error in the computation.

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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
sourcesource vertex
targettarget 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.

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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.

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ getEdge()

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

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

Parameters
edgeIdThe Edge Id to return
Returns
the Edge if exist

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ getEdgeSet()

template<typename T >
const std::list< const Edge< 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

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ getNodeSet()

template<typename T >
const std::list< 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

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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
startNode from where traversing starts
Returns
a vector of nodes that belong to C but not to M.

◆ 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)

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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)

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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.

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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.

◆ partitionGraph()

template<typename T >
PartitionMap< T > CXXGRAPH::Graph< T >::partitionGraph ( PARTITIONING::PartitionAlgorithm  algorithm,
unsigned int  numberOfPartitions 
) const
virtual

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

Parameters
algorithmThe partition algorithm
numberOfPartitionThe number of partitions
Returns
The partiton Map of the partitioned graph

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ prim()

template<typename T >
const PrimResult 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.

◆ 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
formatThe Input format of the file
workingDirThe path to the directory in which is placed the Input file
OFileNameThe Input File Name ( )
compressIndicates if the Input is compressed
writeNodeFeatIndicates if import also Node Features
writeEdgeWeightIndicates if import also Edge Weights
Returns
0 if all OK, else return a negative value

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ removeEdge()

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

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

Parameters
edgeIdThe Edge Id to remove

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ setEdgeSet()

template<typename T >
void CXXGRAPH::Graph< T >::setEdgeSet ( std::list< const Edge< T > * > &  edgeSet)
virtual

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

Parameters
edgeSetThe Edge Set

Reimplemented in CXXGRAPH::Graph_TS< T >.

◆ 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
formatThe Output format of the file
workingDirThe path to the directory in which is placed the Output file
OFileNameThe Output File Name ( )
compressIndicates if the Output will be compressed ( Pay Attention if compress flag is true, not compressed files will be deleted [ #48 ] )
writeNodeFeatIndicates if export also Node Features
writeEdgeWeightIndicates if export also Edge Weights
Returns
0 if all OK, else return a negative value

Reimplemented in CXXGRAPH::Graph_TS< T >.


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