Traverse a graph depth-first or breadth-first and execute a visit function. More...

#include <graph-traverse.H>

Collaboration diagram for Graph_Traverse< GT, Itor, Q, Show_Arc >:

Public Member Functions
	Graph_Traverse (GT &__g, Show_Arc __sa=Show_Arc())
	Construct a traverser with a graph and arc filter.

template<class Node_Op >
size_t	operator() (typename GT::Node *start, Node_Op &op)
	Traverse the graph starting from `start` and execute `op` on each node.

template<class Node_Op >
size_t	operator() (typename GT::Node *start, Node_Op &&op=Node_Op())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Op >
size_t	exec (typename GT::Node *start, Op &op)
	Execute operation op(curr, arc) where curr is the visited node and arc is the incoming arc.

template<class Operation >
size_t	exec (typename GT::Node *start, Operation &&op=Operation())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Node_Op , class Arc_Op >
std::tuple< size_t, size_t >	operator() (typename GT::Node *start, Node_Op &node_op, Arc_Op &arc_op)
	Traverse the graph executing separate operations on nodes and arcs.

template<class Node_Op , class Arc_Op >
std::tuple< size_t, size_t >	operator() (typename GT::Node *start, Node_Op &&node_op=Node_Op(), Arc_Op &&arc_op=Arc_Op())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Private Attributes
GT &	g

Show_Arc	sa

Detailed Description

template<class GT, class Itor, template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>
class Graph_Traverse< GT, Itor, Q, Show_Arc >

Traverse a graph depth-first or breadth-first and execute a visit function.

This class template provides generic graph traversal capabilities using either depth-first search (DFS) or breadth-first search (BFS) depending on the queue type Q used.

Template Parameters

GT	Graph type
Itor	Iterator type for traversing node arcs
Q	Queue type: DynListStack for DFS, DynListQueue for BFS
Show_Arc	Arc filter functor

Definition at line 75 of file graph-traverse.H.

Constructor & Destructor Documentation

◆ Graph_Traverse()

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

Graph_Traverse< GT, Itor, Q, Show_Arc >::Graph_Traverse	(	GT &	__g,
		Show_Arc	__sa = `Show_Arc()`
	)

inline

Construct a traverser with a graph and arc filter.

Definition at line 82 of file graph-traverse.H.

Member Function Documentation

◆ exec() [1/2]

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

template<class Op >

size_t Graph_Traverse< GT, Itor, Q, Show_Arc >::exec	(	typename GT::Node *	start,
		Op &	op
	)

inline

Execute operation op(curr, arc) where curr is the visited node and arc is the incoming arc.

Parameters

start	Starting node for traversal
op	Operation to execute. Signature: bool op(Node, Arc). The arc parameter is nullptr for the start node. Return false to stop traversal early.

Returns: Number of nodes visited

Definition at line 170 of file graph-traverse.H.

References Aleph::count(), Graph_Traverse< GT, Itor, Q, Show_Arc >::g, GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::HTList::is_empty(), Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), Graph_Traverse< GT, Itor, Q, Show_Arc >::sa, GTNodeCommon< NodeInfo >::set_state(), GTArcCommon< ArcInfo >::set_state(), GTNodeCommon< NodeInfo >::state(), GTArcCommon< ArcInfo >::state(), and GraphCommon< GT, Node, Arc >::vsize().

Referenced by Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), TEST_F(), and TEST_F().

◆ exec() [2/2]

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

template<class Operation >

size_t Graph_Traverse< GT, Itor, Q, Show_Arc >::exec	(	typename GT::Node *	start,
		Operation &&	op = `Operation()`
	)

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 230 of file graph-traverse.H.

References Graph_Traverse< GT, Itor, Q, Show_Arc >::exec().

◆ operator()() [1/4]

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

template<class Node_Op , class Arc_Op >

std::tuple< size_t, size_t > Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()	(	typename GT::Node *	start,
		Node_Op &&	node_op = `Node_Op()`,
		Arc_Op &&	arc_op = `Arc_Op()`
	)

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 313 of file graph-traverse.H.

References Aleph::maps().

◆ operator()() [2/4]

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

template<class Node_Op >

size_t Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()	(	typename GT::Node *	start,
		Node_Op &&	op = `Node_Op()`
	)

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 155 of file graph-traverse.H.

◆ operator()() [3/4]

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

template<class Node_Op , class Arc_Op >

std::tuple< size_t, size_t > Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()	(	typename GT::Node *	start,
		Node_Op &	node_op,
		Arc_Op &	arc_op
	)

inline

Traverse the graph executing separate operations on nodes and arcs.

Parameters

start	Starting node for traversal
node_op	Operation for nodes. Signature: bool node_op(Node*).
arc_op	Operation for arcs. Signature: bool arc_op(Arc*).

Returns: Tuple of (nodes_visited, arcs_visited)

Definition at line 243 of file graph-traverse.H.

References Graph_Traverse< GT, Itor, Q, Show_Arc >::g, GraphCommon< GT, Node, Arc >::get_connected_node(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::HTList::is_empty(), Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), Graph_Traverse< GT, Itor, Q, Show_Arc >::sa, GTNodeCommon< NodeInfo >::set_state(), GTArcCommon< ArcInfo >::set_state(), GTNodeCommon< NodeInfo >::state(), and GTArcCommon< ArcInfo >::state().

◆ operator()() [4/4]

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

template<class Node_Op >

size_t Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()	(	typename GT::Node *	start,
		Node_Op &	op
	)

inline

Traverse the graph starting from start and execute op on each node.

Parameters

start	Starting node for traversal
op	Operation to execute on each visited node. Must return bool; return false to stop traversal early.

Returns: Number of nodes visited

Definition at line 92 of file graph-traverse.H.

References Aleph::count(), Graph_Traverse< GT, Itor, Q, Show_Arc >::g, GraphCommon< GT, Node, Arc >::get_connected_node(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::HTList::is_empty(), Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), Graph_Traverse< GT, Itor, Q, Show_Arc >::sa, GTNodeCommon< NodeInfo >::set_state(), GTArcCommon< ArcInfo >::set_state(), GTNodeCommon< NodeInfo >::state(), GTArcCommon< ArcInfo >::state(), and GraphCommon< GT, Node, Arc >::vsize().

Member Data Documentation

◆ g

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

GT& Graph_Traverse< GT, Itor, Q, Show_Arc >::g

private

Definition at line 77 of file graph-traverse.H.

Referenced by Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), and Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()().

◆ sa

template<class GT , class Itor , template< typename T > class Q = DynListStack, class Show_Arc = Dft_Show_Arc<GT>>

Show_Arc Graph_Traverse< GT, Itor, Q, Show_Arc >::sa

private

Definition at line 78 of file graph-traverse.H.

Referenced by Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), and Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()().

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

graph-traverse.H

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Graph_Traverse()

Member Function Documentation

◆ exec() [1/2]

◆ exec() [2/2]

◆ operator()() [1/4]

◆ operator()() [2/4]

◆ operator()() [3/4]

◆ operator()() [4/4]

Member Data Documentation

◆ g

◆ sa