DirectedGraph Breadth-First Traversal Algorithm Reference

-Home

-Documentation

-ARCcore

-graph

-Algorithms

Digraph Breadth-First

+DirectedGraph

-Algorithms

Examples

Digraph Transpose

Digraph Breadth-First

Digraph Depth-First

Digraph Traversals

DirectedGraph Breadth-First Visit/Search Algorithm Reference

DirectedGraph breadth-first search/visit traversal algorithm exposes graph features via visitor pattern callbacks.

DirectedGraph breadth-first search/visit traversal algorithm exposes graph features via visitor pattern callbacks.

See: Examples

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.

`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.

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) |

Tue Oct 15 2019 11:53:42 GMT-0400 (Eastern Daylight Time)

undefined/@encapsule/holism v0.0.10

undefined/polytely-app-runtime v