graph_tool.search

This module includes several search algorithms, which are customizable to arbitrary purposes. It is mostly a wrapper around the Visitor interface of the Boost Graph Library, and the respective search functions.

Summary

bfs_search	Breadth-first traversal of a directed or undirected graph.
bfs_iterator	Return an iterator of the edges corresponding to a breath-first traversal of the graph.
dfs_search	Depth-first traversal of a directed or undirected graph.
dfs_iterator	Return an iterator of the edges corresponding to a depth-first traversal of the graph.
dijkstra_search	Dijkstra traversal of a directed or undirected graph, with non-negative weights.
dijkstra_iterator	Return an iterator of the edges corresponding to a Dijkstra traversal of the graph.
astar_search	Heuristic \(A^*\) search on a weighted, directed or undirected graph for the case where all edge weights are non-negative.
astar_iterator	Return an iterator of the edges corresponding to an \(A^*\) traversal of the graph.
bellman_ford_search	Bellman-Ford traversal of a directed or undirected graph, with negative weights.
BFSVisitor	A visitor object that is invoked at the event-points inside the bfs_search() algorithm.
DFSVisitor	A visitor object that is invoked at the event-points inside the dfs_search() algorithm.
DijkstraVisitor	A visitor object that is invoked at the event-points inside the dijkstra_search() algorithm.
BellmanFordVisitor	A visitor object that is invoked at the event-points inside the bellman_ford_search() algorithm.
AStarVisitor	A visitor object that is invoked at the event-points inside the astar_search() algorithm.
StopSearch	If this exception is raised from inside any search visitor object, the search is aborted.

Example network

In this module, most documentation examples will make use of the network search_example.xml, shown below.

>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> weight = g.ep["weight"]
>>> pos = g.vp["pos"]
>>> gt.graph_draw(g, pos, vertex_text=name, vertex_font_size=12, vertex_shape="double_circle",
...               vertex_fill_color="#729fcf", vertex_pen_width=3,
...               edge_pen_width=weight, output="search_example.svg")
<...>

This is the network used in the examples below. The width of the edges correspond to the values of the “weight” property map.