bfs_iterator

Contents

bfs_iterator#

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

Return an iterator of the edges corresponding to a breath-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:
bfs_iteratorIterator or numpy.ndarray

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

See also

dfs_iterator

Depth-first search

dijkstra_iterator

Dijkstra’s search algorithm

astar_iterator

\(A^*\) heuristic search algorithm

Notes

See bfs_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

[bfs]

Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching, 1959

Examples

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