DirectedGraph Breadth-First Traversal Algorithm Reference 
DirectedGraph Breadth-First Visit/Search Algorithm ReferenceDirectedGraph breadth-first search/visit traversal algorithm exposes graph features via visitor pattern callbacks.
See: Examples
ARCcore.graph.directed.breadthFirstTraverse
Please refer to Chapter 23 "Elementary Graph Algorithms" of Introduction To Algorithms (MIT Press)
for a complete discussion of the depth-first search and visit algorithms encapsulated by jsgraph's depthFirstTraverse algorithm implemented here.
BFT Request and Response
breadthFirstTraverse is called with a normalized traversal algorithm request object and returns a normalized traversal algorithm response object.
var response = digraph.directed.breadthFirstTraverse({
digraph: myDigraph,
visitor: myBFTVisitor
});
Note that by default, breadthFirstTraverse will fail if called on DirectedGraph container that has no root vertices (due to cycle(s) or no vertices at all).
To allow this, in other words go through the motions but traverse nothing, set request.options.allowEmptyStartVector flag true.
See Digraph Traversal for details.
BFT Visitor Interface Object
A BFT visitor interface is a JavaScript object with zero or more defined function callbacks from the table below.
Note that all client-provided visitor functions are required to return a Boolean response: true to continue the traversal, false to terminate.
| callback | request | explanation |
|---|---|---|
| initializeVertex | { u: string, g: DirectedGraph } | invoked on every vertex of the graph before the start of the graph search |
| startVertex | { u: string, g: DirectedGraph } | invoked on every vertex in the start vertex set before starting the breadth-first visit starting at that vertex |
| discoverVertex | { u: string, g: DirectedGraph } | invoked when a vertex is encountered for the first time |
| examineVertex | { u: string, g: DirectedGraph } | invoked on a vertex as it is popped from the queue. This happens immediately before examine_edge() is invoked on each of the out-edges of vertex u |
| examineEdge | { e: { u: string, v: string }, g: DirectedGraph } | invoked on every out-edge of each vertex after it is discovered |
| treeEdge | { e: { uL string, v: string }, g: DirectedGraph } | invoked on each edge as it becomes a member of the edges that form the search tree |
| nonTreeEdge | { e: { u: string, v: string }, g: DirectedGraph } | invoked on back or cross edges of the directed graph |
| grayTarget | { e: { u: string, v: string }, g: DirectedGraph } | invoked on the subset of non-tree edges whose target vertex is colored grat at the time of examination. The color gray indicates that the vertex is currently in the queue |
| blackTarget | { e: { u: string, v: string }, g: DirectedGraph } | invoked on a subset of the edges whose target vertex is colored black at the time of examination. The color black indicates that the vertex has been removed from the queue |
| finishVertex | { u: string, g: DirectedGraph } | invoked on a vertex after all of its out edges have been added to the search tree and all adjacent vertices have been discovered (but before the out-edges of the adjacent vertices have been examined) |
Encapsule Project, Seattle WA
undefined/@encapsule/holism v0.0.10