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.

Static Private Member Functions
static bool	seed_arc (typename GT::Arc a, typename GT::Node tgt) noexcept
	Prepare arc `a` (leading to `tgt`) for frontier expansion out of `start`/`curr`, and report whether the caller should enqueue it.

Private Attributes
GT &	g

Show_Arc	sa

Detailed Description

template<AlephGraph GT, class Itor, template< typename T > class Q = DynListStack, ArcFilter< GT > 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

Warning: graph-traverse-generators.H's Graph_Traverse_Generator re-implements operator()(start, op)'s algorithm as a coroutine (a plain callback can't co_yield, so it can't just wrap this class). A behavioral fix here — anything touching node/arc state transitions, not just cosmetics — needs the matching fix applied there too; it will not pick it up automatically. See its own class-level @see back to here.

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

Constructor & Destructor Documentation

◆ Graph_Traverse()

template<AlephGraph GT, class Itor , template< typename T > class Q = DynListStack, ArcFilter< GT > 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 120 of file graph-traverse.H.

Member Function Documentation

◆ exec() [1/2]

template<AlephGraph GT, class Itor , template< typename T > class Q = DynListStack, ArcFilter< GT > 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 200 of file graph-traverse.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), Graph_Traverse< GT, Itor, Q, Show_Arc >::g, GraphCommon< GT, Node, Arc >::get_connected_node(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), Graph_Traverse< GT, Itor, Q, Show_Arc >::sa, Graph_Traverse< GT, Itor, Q, Show_Arc >::seed_arc(), 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(), and TEST_F().

◆ exec() [2/2]

template<AlephGraph GT, class Itor , template< typename T > class Q = DynListStack, ArcFilter< GT > 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 253 of file graph-traverse.H.

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

◆ operator()() [1/4]

template<AlephGraph GT, class Itor , template< typename T > class Q = DynListStack, ArcFilter< GT > 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 349 of file graph-traverse.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator()() [2/4]

template<AlephGraph GT, class Itor , template< typename T > class Q = DynListStack, ArcFilter< GT > 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 185 of file graph-traverse.H.

◆ operator()() [3/4]

template<AlephGraph GT, class Itor , template< typename T > class Q = DynListStack, ArcFilter< GT > 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 266 of file graph-traverse.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), 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(), 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<AlephGraph GT, class Itor , template< typename T > class Q = DynListStack, ArcFilter< GT > 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 130 of file graph-traverse.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), 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(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), Graph_Traverse< GT, Itor, Q, Show_Arc >::sa, Graph_Traverse< GT, Itor, Q, Show_Arc >::seed_arc(), GTNodeCommon< NodeInfo >::set_state(), GTArcCommon< ArcInfo >::set_state(), GTNodeCommon< NodeInfo >::state(), GTArcCommon< ArcInfo >::state(), and GraphCommon< GT, Node, Arc >::vsize().

◆ seed_arc()

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

static bool Graph_Traverse< GT, Itor, Q, Show_Arc >::seed_arc	(	typename GT::Arc *	a,
		typename GT::Node *	tgt
	)

inlinestaticprivatenoexcept

Prepare arc a (leading to tgt) for frontier expansion out of start/curr, and report whether the caller should enqueue it.

If tgt is a genuine new discovery (Unprocessed), both a and tgt are marked Processing and this returns true — the caller should enqueue a. Otherwise (tgt already Processing or Processed, which includes the tgt == start/tgt == curr self-loop case: start/curr is already Processed by the time this runs) a is marked Processed and this returns false — the caller must not enqueue it. Shared by every seeding loop below so the self-loop guard exists in exactly one place.