graph_tool.search.dfs_search

graph_tool.search.dfs_search(g, source=None, visitor=<graph_tool.search.DFSVisitor object>)

Depth-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.

visitorDFSVisitor (optional, default: DFSVisitor())

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

See also

bfs_search

Breadth-first search

dijkstra_search

Dijkstra’s search algorithm

astar_search

\(A^*\) heuristic search algorithm

Notes

When possible, a depth-first traversal chooses a vertex adjacent to the current vertex to visit next. If all adjacent vertices have already been discovered, or there are no adjacent vertices, then the algorithm backtracks to the last vertex that had undiscovered neighbors. Once all reachable vertices have been visited, the algorithm selects from any remaining undiscovered vertices and continues the traversal. The algorithm finishes when all vertices have been visited.

The time complexity is \(O(V + E)\).

The pseudo-code for the DFS algorithm is listed below, with the annotated event points, for which the given visitor object will be called with the appropriate method.

DFS(G)
  for each vertex u in V
    color[u] := WHITE                 initialize vertex u
  end for
  time := 0
  call DFS-VISIT(G, source)           start vertex s

DFS-VISIT(G, u)
  color[u] := GRAY                    discover vertex u
  for each v in Adj[u]                examine edge (u,v)
    if (color[v] = WHITE)             (u,v) is a tree edge
      call DFS-VISIT(G, v)
    else if (color[v] = GRAY)         (u,v) is a back edge
      ...
    else if (color[v] = BLACK)        (u,v) is a cross or forward edge
      ...
  end for
  color[u] := BLACK                   finish vertex u

References

[dfs-bgl]

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

[dfs-wikipedia]

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

Examples

We must define what should be done during the search by subclassing DFSVisitor, and specializing the appropriate methods. In the following we will keep track of the discover time, and the predecessor tree.

class VisitorExample(gt.DFSVisitor):

    def __init__(self, name, pred, time):
        self.name = name
        self.pred = pred
        self.time = time
        self.last_time = 0

    def discover_vertex(self, u):
        print("-->", self.name[u], "has been discovered!")
        self.time[u] = self.last_time
        self.last_time += 1

    def examine_edge(self, e):
        print("edge (%s, %s) has been examined..." % \
            (self.name[e.source()], self.name[e.target()]))

    def tree_edge(self, e):
        self.pred[e.target()] = int(e.source())

With the above class defined, we can perform the DFS search as follows.

>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> time = g.new_vertex_property("int")
>>> pred = g.new_vertex_property("int64_t")
>>> gt.dfs_search(g, g.vertex(0), VisitorExample(name, pred, time))
--> Bob has been discovered!
edge (Bob, Eve) has been examined...
--> Eve has been discovered!
edge (Eve, Isaac) has been examined...
--> Isaac has been discovered!
edge (Isaac, Bob) has been examined...
edge (Isaac, Chuck) has been examined...
--> Chuck has been discovered!
edge (Chuck, Eve) has been examined...
edge (Chuck, Isaac) has been examined...
edge (Chuck, Imothep) has been examined...
--> Imothep has been discovered!
edge (Imothep, Carol) has been examined...
--> Carol has been discovered!
edge (Carol, Eve) has been examined...
edge (Carol, Imothep) has been examined...
edge (Imothep, Carlos) has been examined...
--> Carlos has been discovered!
edge (Carlos, Eve) has been examined...
edge (Carlos, Imothep) has been examined...
edge (Carlos, Bob) has been examined...
edge (Carlos, Alice) has been examined...
--> Alice has been discovered!
edge (Alice, Oscar) has been examined...
--> Oscar has been discovered!
edge (Oscar, Alice) has been examined...
edge (Oscar, Dave) has been examined...
--> Dave has been discovered!
edge (Dave, Oscar) has been examined...
edge (Dave, Alice) has been examined...
edge (Alice, Dave) has been examined...
edge (Alice, Carlos) has been examined...
edge (Imothep, Chuck) has been examined...
edge (Imothep, Eve) has been examined...
edge (Chuck, Bob) has been examined...
edge (Isaac, Eve) has been examined...
edge (Eve, Imothep) has been examined...
edge (Eve, Carlos) has been examined...
edge (Eve, Chuck) has been examined...
edge (Eve, Bob) has been examined...
edge (Eve, Carol) has been examined...
edge (Bob, Chuck) has been examined...
edge (Bob, Carlos) has been examined...
edge (Bob, Isaac) has been examined...
>>> print(time.a)
[0 7 5 6 3 9 1 2 8 4]
>>> print(pred.a)
[0 3 9 9 7 8 0 6 1 4]