- graph_tool.search.bfs_search(g, source=None, visitor=<graph_tool.search.BFSVisitor object>)[source]#
Breadth-first traversal of a directed or undirected graph.
Graph to be used.
Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order.
A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of
Dijkstra’s search algorithm
\(A^*\) heuristic search algorithm
A breadth-first traversal visits vertices that are closer to the source before visiting vertices that are further away. In this context “distance” is defined as the number of edges in the shortest path from the source vertex.
The time complexity is \(O(V + E)\).
The pseudo-code for the BFS algorithm is listed below, with the annotated event points, for which the given visitor object will be called with the appropriate method.
BFS(G, source) for each vertex u in V[G] initialize vertex u color[u] := WHITE d[u] := infinity end for color[source] := GRAY d[source] := 0 ENQUEUE(Q, source) discover vertex source while (Q != Ø) u := DEQUEUE(Q) examine vertex u for each vertex v in Adj[u] examine edge (u,v) if (color[v] = WHITE) (u,v) is a tree edge color[v] := GRAY ENQUEUE(Q, v) discover vertex v else (u,v) is a non-tree edge if (color[v] = GRAY) ... (u,v) has a gray target else ... (u,v) has a black target end for color[u] := BLACK finish vertex u end while
Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching, 1959[bfs-wikipedia]
We must define what should be done during the search by subclassing
BFSVisitor, and specializing the appropriate methods. In the following we will keep track of the distance from the root, and the predecessor tree.
class VisitorExample(gt.BFSVisitor): def __init__(self, name, pred, dist): self.name = name self.pred = pred self.dist = dist def discover_vertex(self, u): print("-->", self.name[u], "has been discovered!") def examine_vertex(self, u): print(self.name[u], "has been examined...") def tree_edge(self, e): self.pred[e.target()] = int(e.source()) self.dist[e.target()] = self.dist[e.source()] + 1
With the above class defined, we can perform the BFS search as follows.
>>> g = gt.load_graph("search_example.xml") >>> name = g.vp["name"] >>> dist = g.new_vertex_property("int") >>> pred = g.new_vertex_property("int64_t") >>> gt.bfs_search(g, g.vertex(0), VisitorExample(name, pred, dist)) --> Bob has been discovered! Bob has been examined... --> Eve has been discovered! --> Chuck has been discovered! --> Carlos has been discovered! --> Isaac has been discovered! Eve has been examined... --> Imothep has been discovered! --> Carol has been discovered! Chuck has been examined... Carlos has been examined... --> Alice has been discovered! Isaac has been examined... Imothep has been examined... Carol has been examined... Alice has been examined... --> Oscar has been discovered! --> Dave has been discovered! Oscar has been examined... Dave has been examined... >>> print(dist.a) [0 2 2 1 1 3 1 1 3 2] >>> print(pred.a) [0 3 6 0 0 1 0 0 1 6]