traverseBreadthFirst#

Fully qualified name: omni::graph::exec::unstable::traverseBreadthFirst

template<typename Strategy, typename NodeUserData = NoUserData> void omni::graph::exec::unstable::traverseBreadthFirst( INode *node, typename Traversal<INode, ITopology, Strategy, FlowBreadthFirst, NodeUserData, false>::CallbackFn call, )#

Performs a breadth-first (BFS) traversal of a node.

EF has several built-in traversal algorithms:

Depth-First traversal recursively visits a node’s children before visiting its siblings. This traversal type is implemented by traverseDepthFirst.
Breadth-First traversal recursively visits a node’s siblings before visiting its children. This traversal type is implemented by this function.

Visitation Strategy

The template argument Strategy defines the “visitation strategy”. When encountering a node during traversal, the visitation strategy is consulted. If the strategy gives approval to “visit” the node, the given lambda (i.e. call) is invoked. EF ships with the following different strategies, all of which deal with determining if the node should be visited based on the incoming edge (i.e. nodes can have multiple input edges):

VisitFirst. Invoke the given lambda on the first traversed incoming edge.
VisitLast. Invoke the given lambda after all incoming edges have been traversed (i.e. visit on the last edge).
VisitAll. Invoke the given lambda for each incoming edge.

User Defined Work/Data

The lambda call has the following signature (void)(auto info, INode* prev, INode* curr).

curr is the node that the visitation strategy has approved for visiting.

prev is the other end of the incoming edge that was traversed to get to curr.

info is a helper object which serves the following purposes:

Traversal can be continued by calling info.continueVisit(node). Calling info.continueVisit(curr) will continue the breadth-first traversal. However, continueVisit can be called on any node (and even multiple times in the lambda). This allows for the traversal of graph definitions attached to nodes.
The optional template argument NodeUserData defines user defined data that will be allocated for each node to be traversed. info.userData(node) returns the data for the given node.

Concurrency

This function traverses nodes serially. Any user data (i.e. NodeUserData) allocated during traversal will be destroyed upon this function returning.

Learning More

A high-level traversal guide can be found at Traversing a Graph while a more in-depth guide can be found at Graph Travesal In-Depth .