Class that provides Graph traversal using the BFS scheme. More...

#include <BFS.hpp>

Public Member Functions
	BFS (const Graph &, const idx_t)
	Computation constructor. More...

	BFS ()
	Default constructor. More...

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

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

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

BFS &	operator= (BFS &&)=default
	Move assignment. More...

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

void	compute (const Graph &graph, const idx_t src)
	Computation. This is where the BFS algorithm is performed. More...

ordered_list_t	getTraversalOrder () const
	Computes the BFS node traversal order from the source. More...

ordered_list_t	getTraversalOrderMaxDistance (const idx_t &distance) const
	Computes the BFS node traversal order from the source. More...

idx_list_t	getNodesExactDistance (const idx_t &distance) const
	Computes all nodes that are at the exact distance given from the source. More...

idx_t	getNodeDistance (const idx_t &dest) const
	Returns the number of edges between 'src' and 'dest'. More...

idx_list_t	getNodesMaxDistance (const idx_t &distance) const
	Computes all nodes that are at within a maximum distance given from the source. More...

ordered_list_t	getPath (const idx_t &dest) const
	Computes the BFS shortest path from 'src' to 'dest'. More...

Private Types
using	idx_t = typename Graph::idx_t
	Type of indices. More...

using	ordered_list_t = typename Graph::ordered_list_t
	Ordered node ID list. More...

using	visit_list_t = typename Graph::visit_list_t
	Boolean list that stored previously visited nodes. More...

using	BFS_queue_t = std::deque< idx_t >
	Data structure for BFS searches. More...

using	distance_list_t = std::vector< idx_t >
	Stores BFS distances of each node. More...

using	idx_list_t = typename Graph::idx_list_t
	Unordered node ID list. More...

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

idx_t	src_
	Source node. More...

idx_list_t	parents_
	Parents on shortest path tree. More...

ordered_list_t	final_
	BFS Traversal order. More...

distance_list_t	distances_
	List containing distances from source. More...

Detailed Description

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

Class that provides Graph traversal using the BFS scheme.

Member Typedef Documentation

template<class Graph >

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

private

Type of indices.

template<class Graph >

using gl::algorithm::BFS< Graph >::ordered_list_t = typename Graph::ordered_list_t

private

Ordered node ID list.

template<class Graph >

using gl::algorithm::BFS< Graph >::visit_list_t = typename Graph::visit_list_t

private

Boolean list that stored previously visited nodes.

template<class Graph >

using gl::algorithm::BFS< Graph >::BFS_queue_t = std::deque<idx_t>

private

Data structure for BFS searches.

template<class Graph >

using gl::algorithm::BFS< Graph >::distance_list_t = std::vector<idx_t>

private

Stores BFS distances of each node.

template<class Graph >

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

private

Unordered node ID list.

Constructor & Destructor Documentation

template<class Graph >

gl::algorithm::BFS< Graph >::BFS	(	const Graph &	graph,
		const idx_t	src
	)

explicit

Computation constructor.

Directly computes the BFS algorithm on the specified graph

Parameters

[in]	graph	Graph that will be traversed
[in]	src	Source node. Starting point of the Breadth First Search.

template<class Graph >

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

Default constructor.

template<class Graph >

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

default

Copy constructor.

template<class Graph >

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

defaultnoexcept

Move constructor.

template<class Graph >

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

default

Default destructor.

Member Function Documentation

template<class Graph >

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

default

Copy assignment.

template<class Graph >

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

default

Move assignment.

template<class Graph >

void gl::algorithm::BFS< Graph >::compute	(	const Graph &	graph,
		const idx_t	src
	)

Computation. This is where the BFS algorithm is performed.

Parameters

[in]	graph	Input graph on which the BFS will be computed.
[in]	src	source node of BFS.

template<class Graph >

Graph::ordered_list_t gl::algorithm::BFS< Graph >::getTraversalOrder ( ) const

Computes the BFS node traversal order from the source.

Returns: ordered BFS traversal order

template<class Graph >

Graph::ordered_list_t gl::algorithm::BFS< Graph >::getTraversalOrderMaxDistance ( const idx_t & distance ) const

Computes the BFS node traversal order from the source.

Parameters

[in] distance Maximum distance to source of the nodes that are to be found.

Returns: ordered BFS traversal order up to given distance from source

template<class Graph >

Graph::idx_list_t gl::algorithm::BFS< Graph >::getNodesExactDistance ( const idx_t & distance ) const

Computes all nodes that are at the exact distance given from the source.

Parameters

[in] distance Exact distance to source of the nodes that are to be found.

Returns: list of nodes at exact given distance from source.

template<class Graph >

Graph::idx_t gl::algorithm::BFS< Graph >::getNodeDistance ( const idx_t & dest ) const

Returns the number of edges between 'src' and 'dest'.

Parameters

[in] dest Node whose BFS distance is to be computed.

Returns: Number of edges between 'src' and 'dest'.

template<class Graph >

Graph::idx_list_t gl::algorithm::BFS< Graph >::getNodesMaxDistance ( const idx_t & distance ) const

Computes all nodes that are at within a maximum distance given from the source.

Parameters

[in] distance Maximum distance to source of the nodes that are to be found.

Returns: list of nodes within given distance from source.

template<class Graph >

Graph::ordered_list_t gl::algorithm::BFS< Graph >::getPath ( const idx_t & dest ) const

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

Parameters

[in] dest Destination of the shortest path from 'src'.

Returns: Node indices representing the shortest src-dest-path.

Member Data Documentation

template<class Graph >

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

private

Boolean storing initialization status.

template<class Graph >

idx_t gl::algorithm::BFS< Graph >::src_

private

Source node.

template<class Graph >

idx_list_t gl::algorithm::BFS< Graph >::parents_

private

Parents on shortest path tree.

template<class Graph >

ordered_list_t gl::algorithm::BFS< Graph >::final_

private

BFS Traversal order.

template<class Graph >

distance_list_t gl::algorithm::BFS< Graph >::distances_

private

List containing distances from source.

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

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

Public Member Functions

Private Types

Private Attributes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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