graph-traverse-generators.H File Reference

Lazy (coroutine-based) graph traversal (DFS, BFS). More...

#include <ah-graph-concepts.H>
#include <cassert>
#include <ah-errors.H>
#include <ah-generator.H>
#include <graph-traverse.H>

Include dependency graph for graph-traverse-generators.H:

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

Go to the source code of this file.

Classes
class	Aleph::Graph_Traverse_Generator< GT, Itor, Q, Show_Arc >
	Lazily traverse a graph depth-first or breadth-first. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Typedefs
template<class GT , class Itor , class Show_Arc = Dft_Show_Arc<GT>>
using	Aleph::Graph_Traverse_DFS_Generator = Graph_Traverse_Generator< GT, Itor, DynListStack, Show_Arc >
	Lazy depth-first traversal: Graph_Traverse_Generator with a DynListStack frontier.
template<class GT , class Itor , class Show_Arc = Dft_Show_Arc<GT>>
using	Aleph::Graph_Traverse_BFS_Generator = Graph_Traverse_Generator< GT, Itor, DynListQueue, Show_Arc >
	Lazy breadth-first traversal: Graph_Traverse_Generator with a DynListQueue frontier.

Detailed Description

Lazy (coroutine-based) graph traversal (DFS, BFS).

Lazy counterpart of graph-traverse.H's Graph_Traverse: the exact same queue-driven algorithm (a DynListStack gives DFS order, a DynListQueue gives BFS order — the graph's own arcs decide which nodes are reachable next), but exposed as an Aleph::Generator<Node *> instead of a visitor callback. The eager Graph_Traverse/ Graph_Traverse_DFS/Graph_Traverse_BFS are not replaced — reach for the lazy version when the caller may stop early, or wants to compose the traversal with other lazy computation.

using Itor = Node_Arc_Iterator<MyGraph>;
Graph_Traverse_BFS_Generator<MyGraph, Itor> bfs(g);
for (MyGraph::Node *n : bfs.traverse(start))
  {
    if (found(n))
      break;               // stops the search outright
    visit(n);
  }

Note

The traverser object (bfs above) owns the Aleph::Generator's captured state (the graph reference and arc filter) via the usual member-function-coroutine rule: keep it alive for as long as the generator returned by traverse() is being iterated.

Like the eager version, traversal mutates the graph's per-node and per-arc processing state (reset_nodes()/reset_arcs() are called at the start of traverse()), so only one traversal of a given graph should be in flight at a time.

See also

graph-traverse.H Eager visitor-based DFS/BFS (Graph_Traverse).

ah-generator.H Aleph::Generator<T>, the underlying lazy sequence type.

Author

Leandro Rabindranath Leon

Definition in file graph-traverse-generators.H.