Class computes that Shortest Paths for all pairs of nodes in the graph using the Floyd-Warshall algorithm. More...

#include <FloydWarshall.hpp>

Public Member Functions
	FloydWarshall ()
	Default constructor. More...

	FloydWarshall (const Graph &graph)
	Computation Constructor. More...

	FloydWarshall (const FloydWarshall &)=default
	Copy constructor. More...

	FloydWarshall (FloydWarshall &&) noexcept=default
	Move constructor. More...

FloydWarshall &	operator= (const FloydWarshall &)=default
	Copy assignment. More...

FloydWarshall &	operator= (FloydWarshall &&) noexcept=default
	Move assignment. More...

	~FloydWarshall ()=default
	Default destructor. More...

void	compute (const Graph &graph)
	Computation. This is where the shortest distances and the successors of each node pair gets computed. More...

bool	hasNegativePath () const
	Checks whether the input graph has negative cycles. More...

Distance< val_t >	pathLength (const idx_t src, const idx_t dest) const
	Computes the shortest path length from 'src' to 'dest'. More...

std::pair< bool, idx_list_t >	getPath (const idx_t src, const idx_t dest) const
	Computes the node sequence that represents the shortest path from 'src' to 'dest'. More...

Graph	getSPT (const idx_t src) const
	Returns a graph that only contains the edges of the SPT (Shortest Path Tree) starting at 'src'. More...

double	closenessCentrality (const idx_t id) const
	Computes the closeness centrality of node 'id'. More...

double	harmonicCentrality (const idx_t id) const
	Computes the harmonic centrality of node 'id'. More...

Private Types
using	idx_t = typename Graph::idx_t

using	val_t = typename Graph::val_t

using	distance_matrix_t = std::vector< Distance< val_t >>

using	idx_list_t = typename Graph::idx_list_t

Private Attributes
bool	isInitialized_ = false
	Boolean storing initialization status. More...

std::pair< bool, idx_t >	negativePath_
	Boolean storing info on negative path in graph. More...

Graph	graph_
	Reference to graph. More...

distance_matrix_t	dist_
	Shortest Path lengths. More...

idx_list_t	next_
	Shortest Path successors. More...

Detailed Description

template<class Graph>
class gl::algorithm::FloydWarshall< Graph >

Class computes that Shortest Paths for all pairs of nodes in the graph using the Floyd-Warshall algorithm.

Member Typedef Documentation

template<class Graph >

using gl::algorithm::FloydWarshall< Graph >::idx_t = typename Graph::idx_t

private

template<class Graph >

using gl::algorithm::FloydWarshall< Graph >::val_t = typename Graph::val_t

private

template<class Graph >

using gl::algorithm::FloydWarshall< Graph >::distance_matrix_t = std::vector<Distance<val_t>>

private

template<class Graph >

using gl::algorithm::FloydWarshall< Graph >::idx_list_t = typename Graph::idx_list_t

private

Constructor & Destructor Documentation

template<class Graph >

gl::algorithm::FloydWarshall< Graph >::FloydWarshall ( )

Default constructor.

template<class Graph >

gl::algorithm::FloydWarshall< Graph >::FloydWarshall ( const Graph & graph )

explicit

Computation Constructor.

template<class Graph >

gl::algorithm::FloydWarshall< Graph >::FloydWarshall ( const FloydWarshall< Graph > & )

default

Copy constructor.

template<class Graph >

gl::algorithm::FloydWarshall< Graph >::FloydWarshall ( FloydWarshall< Graph > && )

defaultnoexcept

Move constructor.

template<class Graph >

gl::algorithm::FloydWarshall< Graph >::~FloydWarshall ( )

default

Default destructor.

Member Function Documentation

template<class Graph >

FloydWarshall& gl::algorithm::FloydWarshall< Graph >::operator= ( const FloydWarshall< Graph > & )

default

Copy assignment.

template<class Graph >

FloydWarshall& gl::algorithm::FloydWarshall< Graph >::operator= ( FloydWarshall< Graph > && )

defaultnoexcept

Move assignment.

template<class Graph >

void gl::algorithm::FloydWarshall< Graph >::compute ( const Graph & graph )

Computation. This is where the shortest distances and the successors of each node pair gets computed.

Parameters

graph Input graph on which the shortest paths will be computed.

template<class Graph >

bool gl::algorithm::FloydWarshall< Graph >::hasNegativePath ( ) const

Checks whether the input graph has negative cycles.

Returns: True for negative cycle / false for none.

template<class Graph >

Distance< typename Graph::val_t > gl::algorithm::FloydWarshall< Graph >::pathLength	(	const idx_t	src,
		const idx_t	dest
	)		const

Computes the shortest path length from 'src' to 'dest'.

Parameters

src	Starting point of shortest path.
dest	End point of shortest path.

Returns: shortest path length / weight.

template<class Graph >

std::pair< bool, typename Graph::idx_list_t > gl::algorithm::FloydWarshall< Graph >::getPath	(	const idx_t	src,
		const idx_t	dest
	)		const

Computes the node sequence that represents the shortest path from 'src' to 'dest'.

Parameters

src	Starting point of shortest path.
dest	End point of shortest path.

Returns: boolean stating existance of a path & shortest path in form of an ordered list of node indices.

template<class Graph >

Graph gl::algorithm::FloydWarshall< Graph >::getSPT ( const idx_t src ) const

Returns a graph that only contains the edges of the SPT (Shortest Path Tree) starting at 'src'.

Parameters

[in] src source node of SPT graph.

Returns: SPT Graph.

template<class Graph >

double gl::algorithm::FloydWarshall< Graph >::closenessCentrality ( const idx_t id ) const

Computes the closeness centrality of node 'id'.

Precondition: Connected graph

Parameters

[in] id Node whose closeness centrality is to be computed

Returns: closeness centrality of 'id'.

template<class Graph >

double gl::algorithm::FloydWarshall< Graph >::harmonicCentrality ( const idx_t id ) const

Computes the harmonic centrality of node 'id'.

Parameters

[in] id Node whose harmonic centrality is to be computed

Returns: harmonic centrality of 'id'.

Member Data Documentation

template<class Graph >

bool gl::algorithm::FloydWarshall< Graph >::isInitialized_ = false

private

Boolean storing initialization status.

template<class Graph >

std::pair<bool,idx_t> gl::algorithm::FloydWarshall< Graph >::negativePath_

private

Boolean storing info on negative path in graph.

template<class Graph >

Graph gl::algorithm::FloydWarshall< Graph >::graph_

private

Reference to graph.

template<class Graph >

distance_matrix_t gl::algorithm::FloydWarshall< Graph >::dist_

private

Shortest Path lengths.

template<class Graph >

idx_list_t gl::algorithm::FloydWarshall< Graph >::next_

private

Shortest Path successors.

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

/home/travis/build/guetzli32/GraphLib/graphlib/src/algorithms/FloydWarshall.hpp

Public Member Functions

Private Types

Private Attributes

Detailed Description

template<class Graph> class gl::algorithm::FloydWarshall< Graph >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class Graph>
class gl::algorithm::FloydWarshall< Graph >