edgegraph.traversal.depthfirst

edgegraph.traversal.depthfirst#

Depth-first search and traversal functions.

The functions here perform searches and traversals of graphs in a depth-first manner. For each operation (search and traverse), two implementations are provided: one recursive, and one iterative. The calling API is identical between the implementations, but note that the order of traversal frequently differs between them. This is the nature of the differing approaches.

See also

The algorithm used by all the functions herein visits vertices in the following order. Note that the choice of which branch to take at any given node (e.g., visiting v3 before v6) is determined by the structure of the universe.

object v1 object v2 object v3 object v4 object v5 object v6 object v7 object v8 object v9 object v10 object v11 object v12 v1 -- v2 v2 -- v3 v3 -- v4 v3 -- v5 v2 -- v6 v1 -- v7 v1 -- v8 v8 -- v9 v9 -- v10 v9 -- v11 v8 -- v12

Functions

dfs_iterative(uni, start, attrib, val)

Perform a non-recursive depth-first search in the given universe.

dfs_recursive(uni, start, attrib, val)

Perform a recursive depth-first search in the given graph for a given attribute.

dft_iterative(uni, start[, ...])

Perform an iterative depth-first traversal of the given universe, starting at the given vertex (non-generator).

dft_recursive(uni, start[, ...])

Perform a recursive depth-first traversal of the given universe, starting at the given vertex (non-generator).

idft_iterative(uni, start[, ...])

Perform an iterative depth-first traversal of the given universe, starting at the given vertex (generator).

idft_recursive(uni, start[, ...])

Perform a recursive depth-first traversal of the given universe, starting at the given vertex (generator).