Lazily traverse a graph depth-first or breadth-first. More...

#include <graph-traverse-generators.H>

Collaboration diagram for Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >:

Public Member Functions
	Graph_Traverse_Generator (GT &__g, Show_Arc __sa=Show_Arc())
	Construct a lazy traverser bound to graph `__g` with arc filter `__sa`.

Aleph::Generator< typename GT::Node * >	traverse (typename GT::Node *start) &
	Lazily traverse the graph from `start`.

Private Types
using	State = graph_traverse_generator_detail::Traverse_State

Static Private Member Functions
static unsigned char	raw (State s) noexcept

static bool	seed_arc (typename GT::Arc a, typename GT::Node tgt) noexcept
	Prepare arc `a` (leading to `tgt`) for frontier expansion, 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 Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >

Lazily traverse a graph depth-first or breadth-first.

Mirrors Graph_Traverse (see graph-traverse.H): the queue type Q selects the traversal order (DynListStack for DFS, DynListQueue for BFS — see the Graph_Traverse_DFS_Generator/Graph_Traverse_BFS_Generator aliases below), and Itor iterates the arcs incident to a node.

Template Parameters

GT	Graph type (e.g. `List_Graph<...>`, `List_Digraph<...>`).
Itor	Arc iterator type for a node (e.g. `Node_Arc_Iterator<GT>`).
Q	Queue template: `DynListStack` for DFS, `DynListQueue` for BFS.
Show_Arc	Arc filter functor; arcs for which it returns `false` are skipped, exactly as in `Graph_Traverse`.

Note: Thread safety / reentrancy: traverse() is neither reentrant nor thread-safe on a shared GT. It mutates the bound graph directly (g_.reset_nodes(), g_.reset_arcs(), and per-node/per-arc set_state() as the coroutine resumes) rather than tracking state of its own, so at most one active traversal may exist on a given graph at a time. Calling traverse() again on the same GT — from another thread, or from the same thread while a previous Generator from this class is still being iterated (not yet exhausted or destroyed) — resets state out from under that other traversal and corrupts both. Callers needing concurrent or overlapping traversals of the same graph must supply their own external synchronization (e.g. serialize full traversals with a mutex), or traverse separate GT instances.

Definition at line 133 of file graph-traverse-generators.H.

Member Typedef Documentation

◆ State

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

using Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::State = graph_traverse_generator_detail::Traverse_State

private

Definition at line 135 of file graph-traverse-generators.H.

Constructor & Destructor Documentation

◆ Graph_Traverse_Generator()

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

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

inline

Construct a lazy traverser bound to graph __g with arc filter __sa.

Definition at line 163 of file graph-traverse-generators.H.

Member Function Documentation

◆ raw()

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

static unsigned char Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::raw ( State s )

inlinestaticprivatenoexcept

Definition at line 140 of file graph-traverse-generators.H.

Referenced by Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::seed_arc(), and Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

◆ seed_arc()

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

static bool Aleph::Graph_Traverse_Generator< 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, and report whether the caller should enqueue it.

Same semantics as Graph_Traverse::seed_arc (graph-traverse.H) — kept as a separate copy rather than shared because the two classes use different state representations (Traverse_State enum here vs. the GT_Unprocessed/GT_Processing/GT_Processed constants there; see the file-level note on why this header defines its own enum).

Definition at line 149 of file graph-traverse-generators.H.

References Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::raw().

Referenced by Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse().

◆ traverse()

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

Aleph::Generator< typename GT::Node * > Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >::traverse ( typename GT::Node * start ) &

inline

Lazily traverse the graph from start.

Parameters

start Starting node for the traversal.

Returns: A lazy sequence of GT::Node *, one per visited node, in the order determined by Q (stack ⇒ DFS, queue ⇒ BFS).

Note: Complexity: O(1) amortized per yielded node — same total O(V+E) work as the eager traversal, just spread across resumes.

Exceptions

std::invalid_argument if start == nullptr. Like every Aleph::Generator-returning function, the body doesn't run until the first resume (initial_suspend), so this check fires on the first begin()/operator++() of the returned sequence, not on the traverse(start) call itself — catch it around the iteration, not just around the call.

Note: This method is &-ref-qualified on purpose: traverse() is a member-function coroutine, so its frame keeps a raw this and doesn't touch g_/sa_ until the first resume — well after a temporary Graph_Traverse_Generator would have been destroyed. Graph_Traverse_BFS_Generator<GT,Itor>(g).traverse(start) is therefore a compile error instead of a dangling-this bug: bind the traverser to a named variable first (as every example and test in this codebase already does) and keep it alive for as long as the returned sequence is iterated.; Not reentrant/thread-safe on a shared GT — see the class-level note. Do not start a new traversal on this graph until the previous one (if any) is exhausted or its Generator destroyed.