This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.
- dfs_search(graph, source, visitor)#
Depth-first traversal of a directed/undirected graph.
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 all 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
If an exception is raised inside the callback function, the graph traversal will be stopped immediately. You can exploit this to exit early by raising a
StopSearchexception. You can also prune part of the search tree by raising
In the following example we keep track of the tree edges:
import rustworkx as rx from rustworkx.visit import DFSVisitor class TreeEdgesRecorder(DFSVisitor): def __init__(self): self.edges =  def tree_edge(self, edge): self.edges.append(edge) graph = rx.PyGraph() graph.extend_from_edge_list([(1, 3), (0, 1), (2, 1), (0, 2)]) vis = TreeEdgesRecorder() rx.dfs_search(graph, , vis) print('Tree edges:', vis.edges)
Tree edges: [(0, 2, None), (2, 1, None), (1, 3, None)]
Graph can not be mutated while traversing.
graph (PyGraph) – The graph to be used.
source (List[int]) – An optional list of node indices to use as the starting nodes for the depth-first search. If this is not specified then a source will be chosen arbitrarly and repeated until all components of the graph are searched.
visitor – A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of