bfs_search

graph_tool.search.bfs_search(g, source=None, visitor=<graph_tool.search.BFSVisitor object>)

Breadth-first traversal of a directed or undirected 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.

visitorBFSVisitor (optional, default: BFSVisitor())

A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of BFSVisitor.

See also

dfs_search

Depth-first search

dijkstra_search

Dijkstra’s search algorithm

astar_search

\(A^*\) heuristic search algorithm

Notes

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

References

[bfs]

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

[bfs-bgl]

http://www.boost.org/doc/libs/release/libs/graph/doc/breadth_first_search.html

[bfs-wikipedia]

http://en.wikipedia.org/wiki/Breadth-first_search

Examples

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]