edgegraph.traversal.depthfirst.dfs_recursive

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

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

The algorithm used is detailed in [CLRS09], figure 22.4, and [GoTa60], Algorithm 13.6. Slight modifications have been made due to the nature of EdgeGraph’s data model, and to add an early-exit condition if the desired vertex is found. 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