Abstract graph Breadth-First Search traversal. More...

#include <traversal.hpp>

Public Types
typedef std::function< void(const BFS< graph_t > &, const node)>	BFS_process_one
	Single node processing function.

typedef std::function< void(const BFS< graph_t > &, const node, const node, const bool)>	BFS_process_two
	Two nodes processing function.

typedef std::function< bool(const BFS< graph_t > &, const node)>	BFS_bool_one
	One node decision function.

typedef std::function< bool(const BFS< graph_t > &, const node, const node, const bool)>	BFS_bool_two
	Two nodes decision function.

Public Member Functions
	BFS (const graph_t &g) noexcept
	Constructor.

	~BFS () noexcept=default
	Destructor.

void	reset () noexcept
	Set the graph traversal to its default state.

void	start_at (const node source) noexcept
	Start traversal at a given node.

void	start_at (const std::vector< node > &sources) noexcept
	Start the traversal at every given node.

void	set_use_rev_edges (const bool use) noexcept
	Set whether the traversal can use reversed edges.

void	set_terminate_default () noexcept
	Set the default value of m_terminate.

void	set_terminate (const BFS_bool_one &f) noexcept
	Set the function that controls the termination of the loop.

void	set_process_current_default () noexcept
	Set the default value of m_process_current.

void	set_process_current (const BFS_process_one &f) noexcept
	Set the function that controls the processing of the current node.

void	set_process_neighbour_default () noexcept
	Set the default value of m_process_neighbour.

void	set_process_neighbour (const BFS_process_two &f) noexcept
	Set the function that controls the processing of the current neighbour.

void	set_node_add_default () noexcept
	Set the default value of m_add_node.

void	set_node_add (const BFS_bool_two &f) noexcept
	Set the function that controls when a node is to be added to the queue.

void	set_process_visited_neighbors (const bool v) noexcept
	Should the algorithm call the neighbour processing function for already visited neighbors?

void	clear_visited () noexcept
	Sets all nodes to not visited.

void	clear_queue () noexcept
	Clear the memory allocated for this structure.

void	set_visited (const node u, const char vis) noexcept
	Set node u as visited or not.

bool	node_was_visited (const node u) const noexcept
	Returns whether or not node u has been visited.

bool	all_visited () const noexcept
	Have all nodes been visited?

const graph_t &	get_graph () const noexcept
	Returns a constant reference to the graph.

const array< char > &	get_visited () const noexcept
	Return visited nodes information.

Static Public Attributes
static constexpr bool	is_graph_directed
	Is the graph used to initiliaze the object directed?

Protected Member Functions
void	deal_with_neighbour (const node s, const node t, const bool ltr) noexcept
	Deal with a neighbour of an input node.

void	process_neighbors (const node s) noexcept
	Process the neighbors of node s.

void	do_traversal () noexcept
	Traversal through the graph's vertices.

Protected Attributes
const graph_t &	m_G
	Constant reference to the graph.

queue_array< node >	m_queue
	The structure of the traversal.

array< char >	m_vis
	The set of visited nodes.

bool	m_process_visited_neighbors = false
	Should the traversal process previously-visitied neighbors?

bool	m_use_rev_edges = false
	In directed graphs, traverse edges in the reverse direction.

BFS_bool_one	m_terminate
	Early terminating function.

bool	m_is_terminate_set
	Is function m_terminate set?

BFS_process_one	m_process_current
	Node processing function.

bool	m_is_process_current_set
	Is function m_process_current set?

BFS_process_two	m_process_neighbour
	Node processing function.

bool	m_is_process_neighbour_set
	Is function m_process_neighbour set?

BFS_bool_two	m_add_node
	Node addition function.

bool	m_is_add_node_set
	Is function m_add_node set?

Detailed Description

template<class graph_t, std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>
class lal::detail::BFS< graph_t, >

Abstract graph Breadth-First Search traversal.

The traversal can be controlled by setting custom control-flow functions:

a function used for early termination of the traversal (see set_terminate),
a function that processes the current node in the traversal (see set_process_current),
a function that processes the current edge in the traversal (see set_process_neighbour),
a function that controls when a node is to be added to the queue of the traversal (see set_node_add).

This graph_traversal traversal can also use "reversed edges" when doing traversals on directed graphs. A back edge in a directed graph of a node u is a node that points to u, namely, the directed edge is of the form (v,u), for another node v of the graph. This can be set via the set_use_rev_edges method.

An example of usage is as follows:

lal::detail::BFS<graphs::undirected_graph> bfs(g); // 'g' is an undirected graph
bfs.set_terminate( ... ); // assign a function to decide when to terminate the search.
bfs.set_process_neighbour( ... ); // assign a function to process neighbors
bfs.start_at(0); // start the traversal now at node 0.

Template Parameters

graph_t Type of graph.

Member Function Documentation

◆ clear_queue()

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::clear_queue ( )

inlinenoexcept

Clear the memory allocated for this structure.

When using this function, users might also want to call clear_visited.

◆ clear_visited()

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::clear_visited ( )

inlinenoexcept

Sets all nodes to not visited.

When using this function, users might also want to call clear_queue.

◆ deal_with_neighbour()

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::deal_with_neighbour	(	const node	s,
		const node	t,
		const bool	ltr )

inlineprotectednoexcept

Deal with a neighbour of an input node.

Processes the neighbour and pushes it into the queue.

The neighbour is processed if it has not been visited before. In case the node was visited in a previous iteration, it is processed only if m_process_visited_neighbors has been set via method set_process_visited_neighbors.

Node t is pushed into the queue only if it has not been visited before and the user function m_add_node allows it.

Parameters

s	Input node.
t	The neighbour of the input node.
ltr	Left-to-right orientation of the edge \(\{s,t\}\). If ltr is true then the edge has orientation from s to t. If ltr is false, the edge has orientation from t to s.

◆ do_traversal()

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::do_traversal ( )

inlineprotectednoexcept

Traversal through the graph's vertices.

The graph_traversal traversal is implemented as follows:

ProcessNeighbourhood(graph, Q, v, Nv):
  1. for each w in Nv do
  2.        if w has not been visited before, or it has been but
  3.            already-visited nodes have to be processed
  4.        then
  5.            proc_neigh(v,w)
  6.        endif
  7.
  8.        if w not visited before and node_add(v,w) then
  9.            push w into Q
 10.            mark w as visited in vis
 11.        endif
 12.    endfor

graph_traversal(graph, source):
   .    // set of |V(graph)| bits set to false
  1.    vis = {false}
   .    // structure of the traversal, initialized with the source, a queue.
  2.    Q = {source}
  3.    while Q is not empty do
  4.        v = Q.front
  5.        remove Q's front
  6.        proc_curr(v)
  7.        if terminate(v) then Finish traversal
  8.        else
  9.            Nv = out-neighbourhood of v
 10.            ProcessNeighbourhood(graph, Q, v, Nv)
 11.            If graph is directed and process reverse edges then
 12.                Nv = in-neighbourhood of v
 13.                ProcessNeighbourhood(graph, Q, v, Nv)
 14.            endif
 15.        endif
 16.    endwhile

Note that lines (...) extend the neighbourhood of a node "Nv" depending of the type of graph. If the graph is directed and the user wants to process "reversed edges", then the neighbourhood is not limited to "out-neighbors", but also to "in-neighbors".

◆ reset()

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::reset ( )

inlinenoexcept

Set the graph traversal to its default state.

This includes the node processing functions:

m_process_current,
m_process_neighbour,
m_add_node,

the termination function m_terminate, and the attributes:

m_use_rev_edges,
m_process_visited_neighbors.

◆ set_process_visited_neighbors()

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::set_process_visited_neighbors ( const bool v )

inlinenoexcept

Should the algorithm call the neighbour processing function for already visited neighbors?

Parameters

v	Either true or false.

◆ set_visited()

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::set_visited	(	const node	u,
		const char	vis )

inlinenoexcept

Set node u as visited or not.

Parameters

u	Node to set as visitied.
vis	A 0-1 value.

◆ start_at() [1/2]

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::start_at ( const node source )

inlinenoexcept

Start traversal at a given node.

Parameters

source Node.

◆ start_at() [2/2]

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

void lal::detail::BFS< graph_t, >::start_at ( const std::vector< node > & sources )

inlinenoexcept

Start the traversal at every given node.

Parameters

sources List of node.

Member Data Documentation

◆ is_graph_directed

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

bool lal::detail::BFS< graph_t, >::is_graph_directed

staticconstexpr

Initial value:

=

std::is_base_of_v<graphs::directed_graph, graph_t>

Is the graph used to initiliaze the object directed?

A graph is directed if it is a base class of lal::graphs::directed_graph.

◆ m_add_node

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

BFS_bool_two lal::detail::BFS< graph_t, >::m_add_node

protected

Node addition function.

Determines whether a node s should be added to the queue or not.

For more details on when this function is called see do_traversal.

◆ m_process_current

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

BFS_process_one lal::detail::BFS< graph_t, >::m_process_current

protected

Node processing function.

Processes the current node visited.

For more details on when this function is called see do_traversal.

◆ m_process_neighbour

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

BFS_process_two lal::detail::BFS< graph_t, >::m_process_neighbour

protected

Node processing function.

Processes the next visited node. The direction of the nodes visited passed as parameters is given by the boolean parameter. If it is true then the edge is s -> t. If it is false then the edge is t -> s.

For more details on when this function is called see do_traversal.

◆ m_terminate

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

BFS_bool_one lal::detail::BFS< graph_t, >::m_terminate

protected

Early terminating function.

Returns true if the graph_traversal algorithm should terminate.

For more details on when this function is called see do_traversal.

◆ m_use_rev_edges

template<class graph_t , std::enable_if_t< std::is_base_of_v< graphs::graph, graph_t >, bool > = true>

bool lal::detail::BFS< graph_t, >::m_use_rev_edges = false

protected

In directed graphs, traverse edges in the reverse direction.

Besides reaching neighbors following out-edges, reach neighbors following in-neighbors. If vertex s has out-neighbors {1,2,3} and in-neighbors {4,5}, this attribute controls whether vertices {4,5} should also be included in the traversal.

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

lal/detail/graphs/traversal.hpp

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ clear_queue()

◆ clear_visited()

◆ deal_with_neighbour()

◆ do_traversal()

◆ reset()

◆ set_process_visited_neighbors()

◆ set_visited()

◆ start_at() [1/2]

◆ start_at() [2/2]

Member Data Documentation

◆ is_graph_directed

◆ m_add_node

◆ m_process_current

◆ m_process_neighbour

◆ m_terminate

◆ m_use_rev_edges