edgegraph.traversal.depthfirst.dfs_iterative

edgegraph.traversal.depthfirst.dfs_iterative(uni, start, attrib, val)

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

The algorithm used is similar to that in [KlTa05], algorithm 3.12. Slight modifications have been made for an early-exit if the desired vertex is discovered. This is a recursive implementation that returns either the first vertex discovered matching the specified criteria, or None if no such vertex is found.

Search criteria is specified via the attrib and val arguments. Each vertex is checked for A.) the existence of the specified attribute, and B.) the value of such attribute must be equal to the specified value. A == check is used for comparison (not is). Traversal stops as soon as such an attribute is found.

Parameters:

• uni (Universe) – The universe to search in.

• start (Vertex) – The vertex to start searching at.

• attrib (str) – Name of the attribute to check each vertex for.

• val (object) – Value to look for in the specified attribute.

Returns:

The first vertex with a matching value, or None if none is found.

Raises:

ValueError – if the start vertex is not a member of the specified universe, or if the universe is empty.

Return type:

Vertex