Breadth-first and depth-first traversal helpers, visitors, and aliases. More...

#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include "graph.hpp"

Include dependency graph for traversal.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	nxpp::visitor
	Minimal visitor interface for wrapper-level traversal callbacks. More...

class	nxpp::GenericBfsEdgeVisitor< GraphWrapper, Edge >

class	nxpp::GenericBfsVisitVisitor< GraphWrapper, Edge, OnVertex, OnTreeEdge >

class	nxpp::GenericBfsObjectVisitor< NodeID, Edge, GraphWrapper, Visitor >

class	nxpp::GenericDfsEdgeVisitor< GraphWrapper, Edge >

class	nxpp::GenericDfsVisitVisitor< GraphWrapper, Edge, OnTreeEdge, OnBackEdge >

class	nxpp::GenericDfsObjectVisitor< NodeID, Edge, GraphWrapper, Visitor >

Functions
template<typename GraphWrapper >
auto	nxpp::bfs_edges (const GraphWrapper &G, const typename GraphWrapper::NodeType &start)
	Deprecated free-function alias for `G.bfs_edges(start)`.

template<typename GraphWrapper >
auto	nxpp::bfs_tree (const GraphWrapper &G, const typename GraphWrapper::NodeType &start)
	Deprecated free-function alias for `G.bfs_tree(start)`.

template<typename GraphWrapper >
auto	nxpp::bfs_successors (const GraphWrapper &G, const typename GraphWrapper::NodeType &start)
	Deprecated free-function alias for `G.bfs_successors(start)`.

template<typename Visitor , typename NodeID , typename GraphWrapper >
void	nxpp::bfs_dispatch_examine_vertex (Visitor &visitor, const NodeID &u, const GraphWrapper &G)

template<typename Visitor , typename NodeID , typename GraphWrapper >
void	nxpp::bfs_dispatch_tree_edge (Visitor &visitor, const NodeID &u, const NodeID &v, const GraphWrapper &G)

template<typename GraphWrapper , typename Visitor >
void	nxpp::breadth_first_search (const GraphWrapper &G, const typename GraphWrapper::NodeType &start, Visitor &visitor)
	Deprecated free-function alias for `G.breadth_first_search(start, visitor)`.

template<typename GraphWrapper , typename OnVertex , typename OnTreeEdge >
void	nxpp::bfs_visit (const GraphWrapper &G, const typename GraphWrapper::NodeType &start, OnVertex &&on_vertex, OnTreeEdge &&on_tree_edge)
	Deprecated free-function alias for `G.bfs_visit(start, on_vertex, on_tree_edge)`.

template<typename GraphWrapper >
auto	nxpp::dfs_edges (const GraphWrapper &G, const typename GraphWrapper::NodeType &start)
	Deprecated free-function alias for `G.dfs_edges(start)`.

template<typename GraphWrapper >
auto	nxpp::dfs_tree (const GraphWrapper &G, const typename GraphWrapper::NodeType &start)
	Deprecated free-function alias for `G.dfs_tree(start)`.

template<typename GraphWrapper >
auto	nxpp::dfs_predecessors (const GraphWrapper &G, const typename GraphWrapper::NodeType &start)
	Deprecated free-function alias for `G.dfs_predecessors(start)`.

template<typename GraphWrapper >
auto	nxpp::dfs_successors (const GraphWrapper &G, const typename GraphWrapper::NodeType &start)
	Deprecated free-function alias for `G.dfs_successors(start)`.

template<typename Visitor , typename NodeID , typename GraphWrapper >
void	nxpp::dfs_dispatch_tree_edge (Visitor &visitor, const NodeID &u, const NodeID &v, const GraphWrapper &G)

template<typename Visitor , typename NodeID , typename GraphWrapper >
void	nxpp::dfs_dispatch_back_edge (Visitor &visitor, const NodeID &u, const NodeID &v, const GraphWrapper &G)

template<typename GraphWrapper , typename Visitor >
void	nxpp::depth_first_search (const GraphWrapper &G, const typename GraphWrapper::NodeType &start, Visitor &visitor)
	Deprecated free-function alias for `G.depth_first_search(start, visitor)`.

template<typename GraphWrapper , typename OnTreeEdge , typename OnBackEdge >
void	nxpp::dfs_visit (const GraphWrapper &G, const typename GraphWrapper::NodeType &start, OnTreeEdge &&on_tree_edge, OnBackEdge &&on_back_edge)
	Deprecated free-function alias for `G.dfs_visit(start, on_tree_edge, on_back_edge)`.

Detailed Description

Breadth-first and depth-first traversal helpers, visitors, and aliases.

Function Documentation

◆ bfs_edges()

template<typename GraphWrapper >

auto nxpp::bfs_edges	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start
	)

Deprecated free-function alias for G.bfs_edges(start).

Parameters

G	Graph wrapper on which to run BFS.
start	Start node ID.

Returns: The same BFS tree-edge list returned by G.bfs_edges(start).

References nxpp::bfs_edges().

Referenced by nxpp::bfs_edges(), nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::bfs_successors(), and nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::bfs_tree().

◆ bfs_successors()

template<typename GraphWrapper >

auto nxpp::bfs_successors	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start
	)

Deprecated free-function alias for G.bfs_successors(start).

Parameters

G	Graph wrapper on which to compute BFS successors.
start	Start node ID.

Returns: The same sparse successor map returned by G.bfs_successors(start).

References nxpp::bfs_successors().

Referenced by nxpp::bfs_successors().

◆ bfs_tree()

template<typename GraphWrapper >

auto nxpp::bfs_tree	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start
	)

Deprecated free-function alias for G.bfs_tree(start).

Parameters

G	Graph wrapper on which to build the BFS tree.
start	Start node ID.

Returns: The same BFS tree graph returned by G.bfs_tree(start).

References nxpp::bfs_tree().

Referenced by nxpp::bfs_tree().

◆ bfs_visit()

template<typename GraphWrapper , typename OnVertex , typename OnTreeEdge >

void nxpp::bfs_visit	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start,
		OnVertex &&	on_vertex,
		OnTreeEdge &&	on_tree_edge
	)

Deprecated free-function alias for G.bfs_visit(start, on_vertex, on_tree_edge).

Parameters

G	Graph wrapper on which to run the callback-based BFS visit.
start	Start node ID.
on_vertex	Callback invoked when a vertex is examined.
on_tree_edge	Callback invoked for each BFS tree edge.

References nxpp::bfs_visit().

Referenced by nxpp::bfs_visit().

◆ breadth_first_search()

template<typename GraphWrapper , typename Visitor >

void nxpp::breadth_first_search	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start,
		Visitor &	visitor
	)

Deprecated free-function alias for G.breadth_first_search(start, visitor).

Parameters

G	Graph wrapper on which to run BFS.
start	Start node ID.
visitor	Visitor object forwarded to the graph method.

References nxpp::breadth_first_search().

Referenced by nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::bfs_visit(), and nxpp::breadth_first_search().

◆ depth_first_search()

template<typename GraphWrapper , typename Visitor >

void nxpp::depth_first_search	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start,
		Visitor &	visitor
	)

Deprecated free-function alias for G.depth_first_search(start, visitor).

Parameters

G	Graph wrapper on which to run DFS.
start	Start node ID.
visitor	Visitor object forwarded to the graph method.

References nxpp::depth_first_search().

Referenced by nxpp::depth_first_search(), and nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::dfs_visit().

◆ dfs_edges()

template<typename GraphWrapper >

auto nxpp::dfs_edges	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start
	)

Deprecated free-function alias for G.dfs_edges(start).

Parameters

G	Graph wrapper on which to run DFS.
start	Start node ID.

Returns: The same DFS tree-edge list returned by G.dfs_edges(start).

References nxpp::dfs_edges().

Referenced by nxpp::dfs_edges(), nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::dfs_predecessors(), nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::dfs_successors(), and nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::dfs_tree().

◆ dfs_predecessors()

template<typename GraphWrapper >

auto nxpp::dfs_predecessors	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start
	)

Deprecated free-function alias for G.dfs_predecessors(start).

Parameters

G	Graph wrapper on which to compute DFS predecessors.
start	Start node ID.

Returns: The same predecessor map returned by G.dfs_predecessors(start).

References nxpp::dfs_predecessors().

Referenced by nxpp::dfs_predecessors().

◆ dfs_successors()

template<typename GraphWrapper >

auto nxpp::dfs_successors	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start
	)

Deprecated free-function alias for G.dfs_successors(start).

Parameters

G	Graph wrapper on which to compute DFS successors.
start	Start node ID.

Returns: The same sparse successor map returned by G.dfs_successors(start).

References nxpp::dfs_successors().

Referenced by nxpp::dfs_successors().

◆ dfs_tree()

template<typename GraphWrapper >

auto nxpp::dfs_tree	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start
	)

Deprecated free-function alias for G.dfs_tree(start).

Parameters

G	Graph wrapper on which to build the DFS tree.
start	Start node ID.

Returns: The same DFS tree graph returned by G.dfs_tree(start).

References nxpp::dfs_tree().

Referenced by nxpp::dfs_tree().

◆ dfs_visit()

template<typename GraphWrapper , typename OnTreeEdge , typename OnBackEdge >

void nxpp::dfs_visit	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	start,
		OnTreeEdge &&	on_tree_edge,
		OnBackEdge &&	on_back_edge
	)

Deprecated free-function alias for G.dfs_visit(start, on_tree_edge, on_back_edge).

Parameters

G	Graph wrapper on which to run the callback-based DFS visit.
start	Start node ID.
on_tree_edge	Callback invoked for DFS tree edges.
on_back_edge	Callback invoked for DFS back edges.

References nxpp::dfs_visit().

Referenced by nxpp::dfs_visit().

Classes

Functions

Detailed Description

Function Documentation

◆ bfs_edges()

◆ bfs_successors()

◆ bfs_tree()

◆ bfs_visit()

◆ breadth_first_search()

◆ depth_first_search()

◆ dfs_edges()

◆ dfs_predecessors()

◆ dfs_successors()

◆ dfs_tree()

◆ dfs_visit()