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

#include <traversal.hpp>

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

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

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

typedef std::function< bool(const BFS< graph_t > &, node, node)>	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. More...

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

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

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

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

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

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

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_neighbours (bool v) noexcept
	Should the algorithm call the neighbour processing function for already visited neighbours? More...

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

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

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

bool	node_was_visited (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 data_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? More...

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

void	process_neighbours (node s) noexcept
	Process the neighbours of node s.

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

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

linear_queue< node >	m_queue
	The structure of the traversal.

data_array< char >	m_vis
	The set of visited nodes.

bool	m_proc_vis_neighs = false
	Should the traversal process previously-visitied neighbours?

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

BFS_bool_one	m_term
	graph_traversal early terminating function. More...

BFS_process_one	m_proc_cur
	graph_traversal node processing function. More...

BFS_process_two	m_proc_neigh
	graph_traversal neighbour node processing function. More...

BFS_bool_two	m_add_node
	graph_traversal node addition function. More...

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:

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 neighbours
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	(	node	s,
		node	t,
		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_proc_vis_neighs has been set via method set_process_visited_neighbours.

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, u, 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(u,w)
  6.        endif
  7.
  8.        if w not visited before and node_add(w) then
  9.            push w into X
 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, initialised with the source,
   .    // either a stack or a queue.
  2.    X = {source}
  3.    while X is not empty do
  4.        v = X.front or X.top
  5.        remove X's top
  6.        proc_curr(v)
  7.        if terminate(v) then Finish traversal
  8.        else
  9.            Nv = out-neighbourhood of v
 10.            ProcessNeighbourhood(graph, v, Nv)
 11.            If graph is directed and process reverse edges then
 12.                Nv = in-neighbourhood of v
 13.                ProcessNeighbourhood(graph, 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-neighbours", but also to "in-neighbours".

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

the termination function m_term, and the attributes:

◆ set_process_visited_neighbours()

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_neighbours ( bool v )

inlinenoexcept

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

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	(	node	u,
		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 std::vector< node > & sources )

inlinenoexcept

Start the traversal at every given node.

Parameters

sources List of 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 ( node source )

inlinenoexcept

Start traversal at a given node.

Parameters

source 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>

constexpr 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

graph_traversal 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_proc_cur

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_proc_cur

protected

graph_traversal node processing function.

Processes the current node visited.

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

◆ m_proc_neigh

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_proc_neigh

protected

graph_traversal neighbour 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_term

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_term

protected

graph_traversal 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 neighbours following out-edges, reach neighbours following in-neighbours. If vertex s has out-neighbours {1,2,3} and in-neighbours {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_neighbours()

◆ set_visited()

◆ start_at() [1/2]

◆ start_at() [2/2]

Member Data Documentation

◆ is_graph_directed

◆ m_add_node

◆ m_proc_cur

◆ m_proc_neigh

◆ m_term

◆ m_use_rev_edges