DirectedGraph Depth-First Traversal Algorithm Reference

-Home

-Documentation

-ARCcore

-graph

-Algorithms

Digraph Depth-First

+DirectedGraph

-Algorithms

Examples

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.

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.

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

It is a edge which is present in tree obtained after applying DFS on the graph. All the Green edges are tree 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.

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

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.

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.

callback | request | explanation |
---|---|---|

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 |

Sun Jun 16 2019 18:31:44 GMT-0400 (Eastern Daylight Time)

undefined/@encapsule/holism v0.0.10

undefined/polytely-app-runtime v