dfs_search#
- graph_tool.search.dfs_search(g, source=None, visitor=<graph_tool.search.DFSVisitor object>)[source]#
Depth-first traversal of a directed or undirected graph.
- Parameters:
- g
Graph Graph to be used.
- source
Vertex(optional, default:None) Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order.
- visitor
DFSVisitor(optional, default:DFSVisitor()) A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of
DFSVisitor.
- g
See also
bfs_searchBreadth-first search
dijkstra_searchDijkstra’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-wikipedia]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]