DirectedGraph Depth-First Traversal Algorithm Reference
Digraph Depth-First
Digraph Transpose
Digraph Breadth-First
Digraph Depth-First
Digraph Traversals
DirectedGraph Depth-First Visit/Search Algorithm Reference
DirectedGraph depth-first search/visit traversal algorithm exposes graph features via visitor pattern callbacks.


Please refer to Chapter 23 "Elementary Graph Algorithms" of Introduction To Algorithms (MIT Press) for a complete discussion of the classic depth-first search and visit algorithms encapsulated by jsgraph's depthFirstTraverse algorithm.

DFT Request and Response

depthFirstTraverse is called with a normalized traversal algorithm request object and returns a normalized traversal algorithm response object.

var response = digraph.directed.depthFirstTraverse({
    digraph: myDigraph,
    visitor: myDFTVisitor

Note that by default, depthFirstTraverse 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.

Edge Types

Edge types in a directed graph

Tree Edges

It is a edge which is present in tree obtained after applying DFS on the graph. All the Green edges are tree edges.

Forward Edges

It is an edge (u, v) such that v is descendant but not part of the DFS tree. Edge from 1 to 8 is a forward edge.

Back Edges

It is an edge (u, v) such that v is ancestor of edge u but not part of DFS tree. Edge from 6 to 2 is a back edge. Presence of back edge indicates a cycle in directed graph.

Cross Edges

It is a edge which connects two node such that they do not have any ancestor and a descendant relationship between them. Edge from node 5 to 4 is cross edge.

DFT visitor interface object

A DFT 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.

initializeVertex{ u: string: g: DirectedGraph }invoked on every vertex of the graph before the start of the 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
examineEdge{ e: { u: string, v: string }, g: DirectedGraph }invoked on every out-edge of each vertex after it is discovered
treeEdge{ e: { u: string, v: string }, g: DirectedGraph }invoked on each edge as it becomes a member of the edges that form the search tree
backEdge{ e: { u: string, v: string }, g: DirectedGraph }invoked on the back edges in the graph.
forwardOrCrossEdge{ e: { u: string, v: string }, g: DirectedGraph }invoked on forward or cross edges in the graph.
finishVertex{ u: string: g: DirectedGraph }invoked on vertex u after finish_vertex has been called for all the vertices in the DFS-tree rooted at vertex u. If vertex u is a leaf in the DFS-tree, then the finish_vertex function is called on u after all the out-edges of u have been examined.
finishEdge{ e: { u: string, v: string }, g: DirectedGraph }invoked on each non-tree edge as well as on each tree edge after finishVertex has been called on its target vertex

See also: Boost C++ Graph Library: DFS Visitor Concept

Encapsule Project, Seattle WA
Copyright © 2021 Chris Russell
Mon Apr 12 2021 11:07:50 GMT-0400 (Eastern Daylight Time)

undefined/@encapsule/holism v0.0.10
undefined/polytely-app-runtime v