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 of the graph before the start of the graph search |
| discoverVertex | { u: string, g: DirectedGraph } | invoked on every vertex of the graph before the start of the graph search |
| examineVertex | { u: string, g: DirectedGraph } | invoked on every vertex of the graph before the start of the graph search |
| examineEdge | { e: { u: string, v: string }, g: DirectedGraph } | invoked on every out-edge of each vertex after it is discovered |
| nonTreeEdge | { e: { u: string, v: string }, g: DirectedGraph } | invoked on back or cross edges |
| 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
Encapsule/holism v0.0.26