edgegraph.traversal.depthfirst.dft_recursive

Contents

edgegraph.traversal.depthfirst.dft_recursive#

edgegraph.traversal.depthfirst.dft_recursive(uni, start)#

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

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. This is a recursive implementation that returns a list of Vertex objects, in the order of the traversal performed.

Parameters:

  • uni (Universe) – The universe to traverse.

  • start (Vertex) – The vertex to begin traversal at.

Returns:

The vertices visited during traversal.

Raises:

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

Return type:

list[Vertex]

Contents