Class that implement the Thread Safe Graph. More...

#include <Graph_TS.hpp>

Inheritance diagram for CXXGRAPH::Graph_TS< T >:

Collaboration diagram for CXXGRAPH::Graph_TS< T >:

Public Member Functions
	Graph_TS (const std::list< const Edge< T > * > &edgeSet)

	Graph_TS (const Graph< T > &graph)

const std::list< const Edge< T > * > &	getEdgeSet () const override
	Function that return the Edge set of the Graph Note: Thread Safe. More...

void	setEdgeSet (std::list< const Edge< T > * > &edgeSet) override
	Function set the Edge Set of the Graph Note: Thread Safe. More...

void	addEdge (const Edge< T > *edge) override
	Function add an Edge to the Graph Edge Set Note: Thread Safe. More...

void	removeEdge (unsigned long long edgeId) override
	Function remove an Edge from the Graph Edge Set Note: Thread Safe. More...

const std::list< const Node< T > * >	getNodeSet () const override
	Function that return the Node Set of the Graph Note: Thread Safe. More...

const std::optional< const Edge< T > * >	getEdge (unsigned long long edgeId) const override
	Function that return an Edge with specific ID if Exist in the Graph Note: Thread Safe. More...

const AdjacencyMatrix< T >	getAdjMatrix () const override
	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: Thread Safe.

const DijkstraResult	dijkstra (const Node< T > &source, const Node< T > &target) const override
	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: Thread Safe. More...

const BellmanFordResult	bellmanford (const Node< T > &source, const Node< T > &target) const override
	Function runs the bellmanford algorithm for some source node and target node in the graph and returns the shortest distance of target from the source if there is no negative cycle in the graph. Note: Thread Safe. More...

const FWResult	floydWarshall () const override
	Function runs the floyd-Warshall algorithm for every node in the graph and returns the shortest distance of each node from another node if there is no negative cycle in the graph. Note: Thread Safe. More...

const std::vector< Node< T > >	breadth_first_search (const Node< T > &start) const override
	Function performs the breadth first search algorithm over the graph Note: Thread Safe. More...

const std::vector< Node< T > >	depth_first_search (const Node< T > &start) const override
	Function performs the depth first search algorithm over the graph Note: Thread Safe. More...

bool	isCyclicDirectedGraphDFS () const override
	This function uses DFS to check for cycle in the graph. Pay Attention, this function work only with directed Graph Note: Thread Safe. More...

bool	isCyclicDirectedGraphBFS () const override
	This function uses BFS to check for cycle in the graph. Pay Attention, this function work only with directed Graph Note: Thread Safe. More...

bool	isDirectedGraph () const override
	This function checks if a graph is directed Note: Thread Safe. More...

const DialResult	dial (const Node< T > &source, int maxWeight) const override
	This function write the graph in an output file Note: Thread Safe. More...

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 override
	This function write the graph in an output file Note: Thread Safe. More...

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) override
	This function read the graph from an input file Note: Thread Safe. More...

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 override
	This function partition a graph in a set of partitions Note: Thread Safe. More...

Public Member Functions inherited from CXXGRAPH::Graph< T >
	Graph (const std::list< const Edge< T > * > &edgeSet)

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 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 bool	containsCycle (const std::list< const Edge< 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 std::list< const Edge< 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	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...

Public Member Functions inherited from CXXGRAPH::ThreadSafe
void	getLock () const

void	releaseLock () const

Additional Inherited Members
Protected Attributes inherited from CXXGRAPH::ThreadSafe
std::mutex	mutex

Detailed Description

template<typename T>
class CXXGRAPH::Graph_TS< T >

Class that implement the Thread Safe Graph.

Member Function Documentation

◆ addEdge()

template<typename T >

void CXXGRAPH::Graph_TS< T >::addEdge ( const Edge< T > * edge )

overridevirtual

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

Parameters

edge	The Edge to insert

Reimplemented from CXXGRAPH::Graph< T >.

◆ bellmanford()

template<typename T >

const BellmanFordResult CXXGRAPH::Graph_TS< T >::bellmanford	(	const Node< T > &	source,
		const Node< T > &	target
	)		const

overridevirtual

Function runs the bellmanford algorithm for some source node and target node in the graph and returns the shortest distance of target from the source if there is no negative cycle in the graph. Note: 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 negative cycle or there is error in the computation.

Reimplemented from CXXGRAPH::Graph< T >.

◆ breadth_first_search()

template<typename T >

const std::vector< Node< T > > CXXGRAPH::Graph_TS< T >::breadth_first_search ( const Node< T > & start ) const

overridevirtual

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

Parameters

start Node from where traversing starts

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

Reimplemented from CXXGRAPH::Graph< T >.

◆ depth_first_search()

template<typename T >

const std::vector< Node< T > > CXXGRAPH::Graph_TS< T >::depth_first_search ( const Node< T > & start ) const

overridevirtual

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

Parameters

start Node from where traversing starts

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

Reimplemented from CXXGRAPH::Graph< T >.

◆ dial()

template<typename T >

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

overridevirtual

This function write the graph in an output file Note: 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: 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.

Reimplemented from CXXGRAPH::Graph< T >.

◆ dijkstra()

template<typename T >

const DijkstraResult CXXGRAPH::Graph_TS< T >::dijkstra	(	const Node< T > &	source,
		const Node< T > &	target
	)		const

overridevirtual

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

Reimplemented from CXXGRAPH::Graph< T >.

◆ floydWarshall()

template<typename T >

const FWResult CXXGRAPH::Graph_TS< T >::floydWarshall

overridevirtual

Function runs the floyd-Warshall algorithm for every node in the graph and returns the shortest distance of each node from another node if there is no negative cycle in the graph. Note: Thread Safe.

Returns: shortest distance if any node is reachable from other node else ERROR in case if target is not reachable from source or there is negative cycle or there is error in the computation.

Reimplemented from CXXGRAPH::Graph< T >.

◆ getEdge()

template<typename T >

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

overridevirtual

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

Parameters

edgeId The Edge Id to return

Returns: the Edge if exist

Reimplemented from CXXGRAPH::Graph< T >.

◆ getEdgeSet()

template<typename T >

const std::list< const Edge< T > * > & CXXGRAPH::Graph_TS< T >::getEdgeSet

overridevirtual

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

Returns: a list of Edges of the graph

Reimplemented from CXXGRAPH::Graph< T >.

◆ getNodeSet()

template<typename T >

const std::list< const Node< T > * > CXXGRAPH::Graph_TS< T >::getNodeSet

overridevirtual

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

Returns: a list of Nodes of the graph

Reimplemented from CXXGRAPH::Graph< T >.

◆ isCyclicDirectedGraphBFS()

template<typename T >

bool CXXGRAPH::Graph_TS< T >::isCyclicDirectedGraphBFS

overridevirtual

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

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

Reimplemented from CXXGRAPH::Graph< T >.

◆ isCyclicDirectedGraphDFS()

template<typename T >

bool CXXGRAPH::Graph_TS< T >::isCyclicDirectedGraphDFS

overridevirtual

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

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

Reimplemented from CXXGRAPH::Graph< T >.

◆ isDirectedGraph()

template<typename T >

bool CXXGRAPH::Graph_TS< T >::isDirectedGraph

overridevirtual

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

Returns: true if the graph is directed, else false.

Reimplemented from CXXGRAPH::Graph< T >.

◆ partitionGraph()

template<typename T >

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

overridevirtual

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

Parameters

algorithm	The partition algorithm
numberOfPartition	The number of partitions

Returns: The partiton Map of the partitioned graph

Reimplemented from CXXGRAPH::Graph< T >.

◆ readFromFile()

template<typename T >

int CXXGRAPH::Graph_TS< 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`
	)

overridevirtual

This function read the graph from an input file Note: 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

Reimplemented from CXXGRAPH::Graph< T >.

◆ removeEdge()

template<typename T >

void CXXGRAPH::Graph_TS< T >::removeEdge ( unsigned long long edgeId )

overridevirtual

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

Parameters

edgeId The Edge Id to remove

Reimplemented from CXXGRAPH::Graph< T >.

◆ setEdgeSet()

template<typename T >

void CXXGRAPH::Graph_TS< T >::setEdgeSet ( std::list< const Edge< T > * > & edgeSet )

overridevirtual

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

Parameters

edgeSet The Edge Set

Reimplemented from CXXGRAPH::Graph< T >.

◆ writeToFile()

template<typename T >

int CXXGRAPH::Graph_TS< 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

overridevirtual

This function write the graph in an output file Note: 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

Reimplemented from CXXGRAPH::Graph< T >.

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

/github/workspace/include/Graph/Graph_TS.hpp

Public Member Functions

Additional Inherited Members

Detailed Description

template<typename T> class CXXGRAPH::Graph_TS< T >

Member Function Documentation

◆ addEdge()

◆ bellmanford()

◆ breadth_first_search()

◆ depth_first_search()

◆ dial()

◆ dijkstra()

◆ floydWarshall()

◆ getEdge()

◆ getEdgeSet()

◆ getNodeSet()

◆ isCyclicDirectedGraphBFS()

◆ isCyclicDirectedGraphDFS()

◆ isDirectedGraph()

◆ partitionGraph()

◆ readFromFile()

◆ removeEdge()

◆ setEdgeSet()

◆ writeToFile()

template<typename T>
class CXXGRAPH::Graph_TS< T >