Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Basic algorithms for depth-first searching the nodes of a graph."""
3from collections import defaultdict
5import networkx as nx
7__all__ = [
8 "dfs_edges",
9 "dfs_tree",
10 "dfs_predecessors",
11 "dfs_successors",
12 "dfs_preorder_nodes",
13 "dfs_postorder_nodes",
14 "dfs_labeled_edges",
15]
18@nx._dispatchable
19def dfs_edges(G, source=None, depth_limit=None, *, sort_neighbors=None):
20 """Iterate over edges in a depth-first-search (DFS).
22 Perform a depth-first-search over the nodes of `G` and yield
23 the edges in order. This may not generate all edges in `G`
24 (see `~networkx.algorithms.traversal.edgedfs.edge_dfs`).
26 Parameters
27 ----------
28 G : NetworkX graph
30 source : node, optional
31 Specify starting node for depth-first search and yield edges in
32 the component reachable from source.
34 depth_limit : int, optional (default=len(G))
35 Specify the maximum search depth.
37 sort_neighbors : function (default=None)
38 A function that takes an iterator over nodes as the input, and
39 returns an iterable of the same nodes with a custom ordering.
40 For example, `sorted` will sort the nodes in increasing order.
42 Yields
43 ------
44 edge: 2-tuple of nodes
45 Yields edges resulting from the depth-first-search.
47 Examples
48 --------
49 >>> G = nx.path_graph(5)
50 >>> list(nx.dfs_edges(G, source=0))
51 [(0, 1), (1, 2), (2, 3), (3, 4)]
52 >>> list(nx.dfs_edges(G, source=0, depth_limit=2))
53 [(0, 1), (1, 2)]
55 Notes
56 -----
57 If a source is not specified then a source is chosen arbitrarily and
58 repeatedly until all components in the graph are searched.
60 The implementation of this function is adapted from David Eppstein's
61 depth-first search function in PADS [1]_, with modifications
62 to allow depth limits based on the Wikipedia article
63 "Depth-limited search" [2]_.
65 See Also
66 --------
67 dfs_preorder_nodes
68 dfs_postorder_nodes
69 dfs_labeled_edges
70 :func:`~networkx.algorithms.traversal.edgedfs.edge_dfs`
71 :func:`~networkx.algorithms.traversal.breadth_first_search.bfs_edges`
73 References
74 ----------
75 .. [1] http://www.ics.uci.edu/~eppstein/PADS
76 .. [2] https://en.wikipedia.org/wiki/Depth-limited_search
77 """
78 if source is None:
79 # edges for all components
80 nodes = G
81 else:
82 # edges for components with source
83 nodes = [source]
84 if depth_limit is None:
85 depth_limit = len(G)
87 get_children = (
88 G.neighbors
89 if sort_neighbors is None
90 else lambda n: iter(sort_neighbors(G.neighbors(n)))
91 )
93 visited = set()
94 for start in nodes:
95 if start in visited:
96 continue
97 visited.add(start)
98 stack = [(start, get_children(start))]
99 depth_now = 1
100 while stack:
101 parent, children = stack[-1]
102 for child in children:
103 if child not in visited:
104 yield parent, child
105 visited.add(child)
106 if depth_now < depth_limit:
107 stack.append((child, get_children(child)))
108 depth_now += 1
109 break
110 else:
111 stack.pop()
112 depth_now -= 1
115@nx._dispatchable(returns_graph=True)
116def dfs_tree(G, source=None, depth_limit=None, *, sort_neighbors=None):
117 """Returns oriented tree constructed from a depth-first-search from source.
119 Parameters
120 ----------
121 G : NetworkX graph
123 source : node, optional
124 Specify starting node for depth-first search.
126 depth_limit : int, optional (default=len(G))
127 Specify the maximum search depth.
129 sort_neighbors : function (default=None)
130 A function that takes an iterator over nodes as the input, and
131 returns an iterable of the same nodes with a custom ordering.
132 For example, `sorted` will sort the nodes in increasing order.
134 Returns
135 -------
136 T : NetworkX DiGraph
137 An oriented tree
139 Examples
140 --------
141 >>> G = nx.path_graph(5)
142 >>> T = nx.dfs_tree(G, source=0, depth_limit=2)
143 >>> list(T.edges())
144 [(0, 1), (1, 2)]
145 >>> T = nx.dfs_tree(G, source=0)
146 >>> list(T.edges())
147 [(0, 1), (1, 2), (2, 3), (3, 4)]
149 See Also
150 --------
151 dfs_preorder_nodes
152 dfs_postorder_nodes
153 dfs_labeled_edges
154 :func:`~networkx.algorithms.traversal.edgedfs.edge_dfs`
155 :func:`~networkx.algorithms.traversal.breadth_first_search.bfs_tree`
156 """
157 T = nx.DiGraph()
158 if source is None:
159 T.add_nodes_from(G)
160 else:
161 T.add_node(source)
162 T.add_edges_from(dfs_edges(G, source, depth_limit, sort_neighbors=sort_neighbors))
163 return T
166@nx._dispatchable
167def dfs_predecessors(G, source=None, depth_limit=None, *, sort_neighbors=None):
168 """Returns dictionary of predecessors in depth-first-search from source.
170 Parameters
171 ----------
172 G : NetworkX graph
174 source : node, optional
175 Specify starting node for depth-first search.
176 Note that you will get predecessors for all nodes in the
177 component containing `source`. This input only specifies
178 where the DFS starts.
180 depth_limit : int, optional (default=len(G))
181 Specify the maximum search depth.
183 sort_neighbors : function (default=None)
184 A function that takes an iterator over nodes as the input, and
185 returns an iterable of the same nodes with a custom ordering.
186 For example, `sorted` will sort the nodes in increasing order.
188 Returns
189 -------
190 pred: dict
191 A dictionary with nodes as keys and predecessor nodes as values.
193 Examples
194 --------
195 >>> G = nx.path_graph(4)
196 >>> nx.dfs_predecessors(G, source=0)
197 {1: 0, 2: 1, 3: 2}
198 >>> nx.dfs_predecessors(G, source=0, depth_limit=2)
199 {1: 0, 2: 1}
201 Notes
202 -----
203 If a source is not specified then a source is chosen arbitrarily and
204 repeatedly until all components in the graph are searched.
206 The implementation of this function is adapted from David Eppstein's
207 depth-first search function in `PADS`_, with modifications
208 to allow depth limits based on the Wikipedia article
209 "`Depth-limited search`_".
211 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
212 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
214 See Also
215 --------
216 dfs_preorder_nodes
217 dfs_postorder_nodes
218 dfs_labeled_edges
219 :func:`~networkx.algorithms.traversal.edgedfs.edge_dfs`
220 :func:`~networkx.algorithms.traversal.breadth_first_search.bfs_tree`
221 """
222 return {
223 t: s
224 for s, t in dfs_edges(G, source, depth_limit, sort_neighbors=sort_neighbors)
225 }
228@nx._dispatchable
229def dfs_successors(G, source=None, depth_limit=None, *, sort_neighbors=None):
230 """Returns dictionary of successors in depth-first-search from source.
232 Parameters
233 ----------
234 G : NetworkX graph
236 source : node, optional
237 Specify starting node for depth-first search.
238 Note that you will get successors for all nodes in the
239 component containing `source`. This input only specifies
240 where the DFS starts.
242 depth_limit : int, optional (default=len(G))
243 Specify the maximum search depth.
245 sort_neighbors : function (default=None)
246 A function that takes an iterator over nodes as the input, and
247 returns an iterable of the same nodes with a custom ordering.
248 For example, `sorted` will sort the nodes in increasing order.
250 Returns
251 -------
252 succ: dict
253 A dictionary with nodes as keys and list of successor nodes as values.
255 Examples
256 --------
257 >>> G = nx.path_graph(5)
258 >>> nx.dfs_successors(G, source=0)
259 {0: [1], 1: [2], 2: [3], 3: [4]}
260 >>> nx.dfs_successors(G, source=0, depth_limit=2)
261 {0: [1], 1: [2]}
263 Notes
264 -----
265 If a source is not specified then a source is chosen arbitrarily and
266 repeatedly until all components in the graph are searched.
268 The implementation of this function is adapted from David Eppstein's
269 depth-first search function in `PADS`_, with modifications
270 to allow depth limits based on the Wikipedia article
271 "`Depth-limited search`_".
273 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
274 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
276 See Also
277 --------
278 dfs_preorder_nodes
279 dfs_postorder_nodes
280 dfs_labeled_edges
281 :func:`~networkx.algorithms.traversal.edgedfs.edge_dfs`
282 :func:`~networkx.algorithms.traversal.breadth_first_search.bfs_tree`
283 """
284 d = defaultdict(list)
285 for s, t in dfs_edges(
286 G,
287 source=source,
288 depth_limit=depth_limit,
289 sort_neighbors=sort_neighbors,
290 ):
291 d[s].append(t)
292 return dict(d)
295@nx._dispatchable
296def dfs_postorder_nodes(G, source=None, depth_limit=None, *, sort_neighbors=None):
297 """Generate nodes in a depth-first-search post-ordering starting at source.
299 Parameters
300 ----------
301 G : NetworkX graph
303 source : node, optional
304 Specify starting node for depth-first search.
306 depth_limit : int, optional (default=len(G))
307 Specify the maximum search depth.
309 sort_neighbors : function (default=None)
310 A function that takes an iterator over nodes as the input, and
311 returns an iterable of the same nodes with a custom ordering.
312 For example, `sorted` will sort the nodes in increasing order.
314 Returns
315 -------
316 nodes: generator
317 A generator of nodes in a depth-first-search post-ordering.
319 Examples
320 --------
321 >>> G = nx.path_graph(5)
322 >>> list(nx.dfs_postorder_nodes(G, source=0))
323 [4, 3, 2, 1, 0]
324 >>> list(nx.dfs_postorder_nodes(G, source=0, depth_limit=2))
325 [1, 0]
327 Notes
328 -----
329 If a source is not specified then a source is chosen arbitrarily and
330 repeatedly until all components in the graph are searched.
332 The implementation of this function is adapted from David Eppstein's
333 depth-first search function in `PADS`_, with modifications
334 to allow depth limits based on the Wikipedia article
335 "`Depth-limited search`_".
337 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
338 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
340 See Also
341 --------
342 dfs_edges
343 dfs_preorder_nodes
344 dfs_labeled_edges
345 :func:`~networkx.algorithms.traversal.edgedfs.edge_dfs`
346 :func:`~networkx.algorithms.traversal.breadth_first_search.bfs_tree`
347 """
348 edges = nx.dfs_labeled_edges(
349 G, source=source, depth_limit=depth_limit, sort_neighbors=sort_neighbors
350 )
351 return (v for u, v, d in edges if d == "reverse")
354@nx._dispatchable
355def dfs_preorder_nodes(G, source=None, depth_limit=None, *, sort_neighbors=None):
356 """Generate nodes in a depth-first-search pre-ordering starting at source.
358 Parameters
359 ----------
360 G : NetworkX graph
362 source : node, optional
363 Specify starting node for depth-first search and return nodes in
364 the component reachable from source.
366 depth_limit : int, optional (default=len(G))
367 Specify the maximum search depth.
369 sort_neighbors : function (default=None)
370 A function that takes an iterator over nodes as the input, and
371 returns an iterable of the same nodes with a custom ordering.
372 For example, `sorted` will sort the nodes in increasing order.
374 Returns
375 -------
376 nodes: generator
377 A generator of nodes in a depth-first-search pre-ordering.
379 Examples
380 --------
381 >>> G = nx.path_graph(5)
382 >>> list(nx.dfs_preorder_nodes(G, source=0))
383 [0, 1, 2, 3, 4]
384 >>> list(nx.dfs_preorder_nodes(G, source=0, depth_limit=2))
385 [0, 1, 2]
387 Notes
388 -----
389 If a source is not specified then a source is chosen arbitrarily and
390 repeatedly until all components in the graph are searched.
392 The implementation of this function is adapted from David Eppstein's
393 depth-first search function in `PADS`_, with modifications
394 to allow depth limits based on the Wikipedia article
395 "`Depth-limited search`_".
397 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
398 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
400 See Also
401 --------
402 dfs_edges
403 dfs_postorder_nodes
404 dfs_labeled_edges
405 :func:`~networkx.algorithms.traversal.breadth_first_search.bfs_edges`
406 """
407 edges = nx.dfs_labeled_edges(
408 G, source=source, depth_limit=depth_limit, sort_neighbors=sort_neighbors
409 )
410 return (v for u, v, d in edges if d == "forward")
413@nx._dispatchable
414def dfs_labeled_edges(G, source=None, depth_limit=None, *, sort_neighbors=None):
415 """Iterate over edges in a depth-first-search (DFS) labeled by type.
417 Parameters
418 ----------
419 G : NetworkX graph
421 source : node, optional
422 Specify starting node for depth-first search and return edges in
423 the component reachable from source.
425 depth_limit : int, optional (default=len(G))
426 Specify the maximum search depth.
428 sort_neighbors : function (default=None)
429 A function that takes an iterator over nodes as the input, and
430 returns an iterable of the same nodes with a custom ordering.
431 For example, `sorted` will sort the nodes in increasing order.
433 Returns
434 -------
435 edges: generator
436 A generator of triples of the form (*u*, *v*, *d*), where (*u*,
437 *v*) is the edge being explored in the depth-first search and *d*
438 is one of the strings 'forward', 'nontree', 'reverse', or 'reverse-depth_limit'.
439 A 'forward' edge is one in which *u* has been visited but *v* has
440 not. A 'nontree' edge is one in which both *u* and *v* have been
441 visited but the edge is not in the DFS tree. A 'reverse' edge is
442 one in which both *u* and *v* have been visited and the edge is in
443 the DFS tree. When the `depth_limit` is reached via a 'forward' edge,
444 a 'reverse' edge is immediately generated rather than the subtree
445 being explored. To indicate this flavor of 'reverse' edge, the string
446 yielded is 'reverse-depth_limit'.
448 Examples
449 --------
451 The labels reveal the complete transcript of the depth-first search
452 algorithm in more detail than, for example, :func:`dfs_edges`::
454 >>> from pprint import pprint
455 >>>
456 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 1)])
457 >>> pprint(list(nx.dfs_labeled_edges(G, source=0)))
458 [(0, 0, 'forward'),
459 (0, 1, 'forward'),
460 (1, 2, 'forward'),
461 (2, 1, 'nontree'),
462 (1, 2, 'reverse'),
463 (0, 1, 'reverse'),
464 (0, 0, 'reverse')]
466 Notes
467 -----
468 If a source is not specified then a source is chosen arbitrarily and
469 repeatedly until all components in the graph are searched.
471 The implementation of this function is adapted from David Eppstein's
472 depth-first search function in `PADS`_, with modifications
473 to allow depth limits based on the Wikipedia article
474 "`Depth-limited search`_".
476 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
477 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
479 See Also
480 --------
481 dfs_edges
482 dfs_preorder_nodes
483 dfs_postorder_nodes
484 """
485 # Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py
486 # by D. Eppstein, July 2004.
487 if source is None:
488 # edges for all components
489 nodes = G
490 else:
491 # edges for components with source
492 nodes = [source]
493 if depth_limit is None:
494 depth_limit = len(G)
496 get_children = (
497 G.neighbors
498 if sort_neighbors is None
499 else lambda n: iter(sort_neighbors(G.neighbors(n)))
500 )
502 visited = set()
503 for start in nodes:
504 if start in visited:
505 continue
506 yield start, start, "forward"
507 visited.add(start)
508 stack = [(start, get_children(start))]
509 depth_now = 1
510 while stack:
511 parent, children = stack[-1]
512 for child in children:
513 if child in visited:
514 yield parent, child, "nontree"
515 else:
516 yield parent, child, "forward"
517 visited.add(child)
518 if depth_now < depth_limit:
519 stack.append((child, iter(get_children(child))))
520 depth_now += 1
521 break
522 else:
523 yield parent, child, "reverse-depth_limit"
524 else:
525 stack.pop()
526 depth_now -= 1
527 if stack:
528 yield stack[-1][0], parent, "reverse"
529 yield start, start, "reverse"