dfs_iterator

Contents

dfs_iterator#

graph_tool.search.dfs_iterator(g, source=None, array=False)[source]#

Return an iterator of the edges corresponding to a depth-first traversal of the graph.

Parameters:
gGraph

Graph to be used.

sourceVertex (optional, default: None)

Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order.

arraybool (optional, default: False)

If True, a numpy.ndarray with the edge endpoints be returned instead.

Returns:
dfs_iteratorIterator or numpy.ndarray

An iterator over the edges in depth-first order. If array == True, this will be a numpy.ndarray instead, of shape (E,2), containing the edge endpoints.

See also

bfs_iterator

Breadth-first search

dijkstra_iterator

Dijkstra’s search algorithm

astar_iterator

\(A^*\) heuristic search algorithm

Notes

See dfs_search() for an explanation of the algorithm.

The time complexity is \(O(1)\) to create the generator and \(O(V + E)\) to traverse it completely.

References

Examples

>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> for e in gt.dfs_iterator(g, g.vertex(0)):
...    print(name[e.source()], "->", name[e.target()])
Bob -> Eve
Eve -> Isaac
Isaac -> Chuck
Chuck -> Imothep
Imothep -> Carol
Imothep -> Carlos
Carlos -> Alice
Alice -> Oscar
Oscar -> Dave
Contents