Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/traversal/depth_first_search.py: 20%
86 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Basic algorithms for depth-first searching the nodes of a graph."""
2from collections import defaultdict
4import networkx as nx
6__all__ = [
7 "dfs_edges",
8 "dfs_tree",
9 "dfs_predecessors",
10 "dfs_successors",
11 "dfs_preorder_nodes",
12 "dfs_postorder_nodes",
13 "dfs_labeled_edges",
14]
17@nx._dispatch
18def dfs_edges(G, source=None, depth_limit=None):
19 """Iterate over edges in a depth-first-search (DFS).
21 Perform a depth-first-search over the nodes of `G` and yield
22 the edges in order. This may not generate all edges in `G`
23 (see `~networkx.algorithms.traversal.edgedfs.edge_dfs`).
25 Parameters
26 ----------
27 G : NetworkX graph
29 source : node, optional
30 Specify starting node for depth-first search and yield edges in
31 the component reachable from source.
33 depth_limit : int, optional (default=len(G))
34 Specify the maximum search depth.
36 Yields
37 ------
38 edge: 2-tuple of nodes
39 Yields edges resulting from the depth-first-search.
41 Examples
42 --------
43 >>> G = nx.path_graph(5)
44 >>> list(nx.dfs_edges(G, source=0))
45 [(0, 1), (1, 2), (2, 3), (3, 4)]
46 >>> list(nx.dfs_edges(G, source=0, depth_limit=2))
47 [(0, 1), (1, 2)]
49 Notes
50 -----
51 If a source is not specified then a source is chosen arbitrarily and
52 repeatedly until all components in the graph are searched.
54 The implementation of this function is adapted from David Eppstein's
55 depth-first search function in PADS [1]_, with modifications
56 to allow depth limits based on the Wikipedia article
57 "Depth-limited search" [2]_.
59 See Also
60 --------
61 dfs_preorder_nodes
62 dfs_postorder_nodes
63 dfs_labeled_edges
64 :func:`~networkx.algorithms.traversal.edgedfs.edge_dfs`
65 :func:`~networkx.algorithms.traversal.breadth_first_search.bfs_edges`
67 References
68 ----------
69 .. [1] http://www.ics.uci.edu/~eppstein/PADS
70 .. [2] https://en.wikipedia.org/wiki/Depth-limited_search
71 """
72 if source is None:
73 # edges for all components
74 nodes = G
75 else:
76 # edges for components with source
77 nodes = [source]
78 if depth_limit is None:
79 depth_limit = len(G)
81 visited = set()
82 for start in nodes:
83 if start in visited:
84 continue
85 visited.add(start)
86 stack = [(start, iter(G[start]))]
87 depth_now = 1
88 while stack:
89 parent, children = stack[-1]
90 for child in children:
91 if child not in visited:
92 yield parent, child
93 visited.add(child)
94 if depth_now < depth_limit:
95 stack.append((child, iter(G[child])))
96 depth_now += 1
97 break
98 else:
99 stack.pop()
100 depth_now -= 1
103@nx._dispatch
104def dfs_tree(G, source=None, depth_limit=None):
105 """Returns oriented tree constructed from a depth-first-search from source.
107 Parameters
108 ----------
109 G : NetworkX graph
111 source : node, optional
112 Specify starting node for depth-first search.
114 depth_limit : int, optional (default=len(G))
115 Specify the maximum search depth.
117 Returns
118 -------
119 T : NetworkX DiGraph
120 An oriented tree
122 Examples
123 --------
124 >>> G = nx.path_graph(5)
125 >>> T = nx.dfs_tree(G, source=0, depth_limit=2)
126 >>> list(T.edges())
127 [(0, 1), (1, 2)]
128 >>> T = nx.dfs_tree(G, source=0)
129 >>> list(T.edges())
130 [(0, 1), (1, 2), (2, 3), (3, 4)]
132 See Also
133 --------
134 dfs_preorder_nodes
135 dfs_postorder_nodes
136 dfs_labeled_edges
137 edge_dfs
138 bfs_tree
139 """
140 T = nx.DiGraph()
141 if source is None:
142 T.add_nodes_from(G)
143 else:
144 T.add_node(source)
145 T.add_edges_from(dfs_edges(G, source, depth_limit))
146 return T
149@nx._dispatch
150def dfs_predecessors(G, source=None, depth_limit=None):
151 """Returns dictionary of predecessors in depth-first-search from source.
153 Parameters
154 ----------
155 G : NetworkX graph
157 source : node, optional
158 Specify starting node for depth-first search.
159 Note that you will get predecessors for all nodes in the
160 component containing `source`. This input only specifies
161 where the DFS starts.
163 depth_limit : int, optional (default=len(G))
164 Specify the maximum search depth.
166 Returns
167 -------
168 pred: dict
169 A dictionary with nodes as keys and predecessor nodes as values.
171 Examples
172 --------
173 >>> G = nx.path_graph(4)
174 >>> nx.dfs_predecessors(G, source=0)
175 {1: 0, 2: 1, 3: 2}
176 >>> nx.dfs_predecessors(G, source=0, depth_limit=2)
177 {1: 0, 2: 1}
179 Notes
180 -----
181 If a source is not specified then a source is chosen arbitrarily and
182 repeatedly until all components in the graph are searched.
184 The implementation of this function is adapted from David Eppstein's
185 depth-first search function in `PADS`_, with modifications
186 to allow depth limits based on the Wikipedia article
187 "`Depth-limited search`_".
189 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
190 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
192 See Also
193 --------
194 dfs_preorder_nodes
195 dfs_postorder_nodes
196 dfs_labeled_edges
197 edge_dfs
198 bfs_tree
199 """
200 return {t: s for s, t in dfs_edges(G, source, depth_limit)}
203@nx._dispatch
204def dfs_successors(G, source=None, depth_limit=None):
205 """Returns dictionary of successors in depth-first-search from source.
207 Parameters
208 ----------
209 G : NetworkX graph
211 source : node, optional
212 Specify starting node for depth-first search.
213 Note that you will get successors for all nodes in the
214 component containing `source`. This input only specifies
215 where the DFS starts.
217 depth_limit : int, optional (default=len(G))
218 Specify the maximum search depth.
220 Returns
221 -------
222 succ: dict
223 A dictionary with nodes as keys and list of successor nodes as values.
225 Examples
226 --------
227 >>> G = nx.path_graph(5)
228 >>> nx.dfs_successors(G, source=0)
229 {0: [1], 1: [2], 2: [3], 3: [4]}
230 >>> nx.dfs_successors(G, source=0, depth_limit=2)
231 {0: [1], 1: [2]}
233 Notes
234 -----
235 If a source is not specified then a source is chosen arbitrarily and
236 repeatedly until all components in the graph are searched.
238 The implementation of this function is adapted from David Eppstein's
239 depth-first search function in `PADS`_, with modifications
240 to allow depth limits based on the Wikipedia article
241 "`Depth-limited search`_".
243 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
244 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
246 See Also
247 --------
248 dfs_preorder_nodes
249 dfs_postorder_nodes
250 dfs_labeled_edges
251 edge_dfs
252 bfs_tree
253 """
254 d = defaultdict(list)
255 for s, t in dfs_edges(G, source=source, depth_limit=depth_limit):
256 d[s].append(t)
257 return dict(d)
260@nx._dispatch
261def dfs_postorder_nodes(G, source=None, depth_limit=None):
262 """Generate nodes in a depth-first-search post-ordering starting at source.
264 Parameters
265 ----------
266 G : NetworkX graph
268 source : node, optional
269 Specify starting node for depth-first search.
271 depth_limit : int, optional (default=len(G))
272 Specify the maximum search depth.
274 Returns
275 -------
276 nodes: generator
277 A generator of nodes in a depth-first-search post-ordering.
279 Examples
280 --------
281 >>> G = nx.path_graph(5)
282 >>> list(nx.dfs_postorder_nodes(G, source=0))
283 [4, 3, 2, 1, 0]
284 >>> list(nx.dfs_postorder_nodes(G, source=0, depth_limit=2))
285 [1, 0]
287 Notes
288 -----
289 If a source is not specified then a source is chosen arbitrarily and
290 repeatedly until all components in the graph are searched.
292 The implementation of this function is adapted from David Eppstein's
293 depth-first search function in `PADS`_, with modifications
294 to allow depth limits based on the Wikipedia article
295 "`Depth-limited search`_".
297 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
298 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
300 See Also
301 --------
302 dfs_edges
303 dfs_preorder_nodes
304 dfs_labeled_edges
305 edge_dfs
306 bfs_tree
307 """
308 edges = nx.dfs_labeled_edges(G, source=source, depth_limit=depth_limit)
309 return (v for u, v, d in edges if d == "reverse")
312@nx._dispatch
313def dfs_preorder_nodes(G, source=None, depth_limit=None):
314 """Generate nodes in a depth-first-search pre-ordering starting at source.
316 Parameters
317 ----------
318 G : NetworkX graph
320 source : node, optional
321 Specify starting node for depth-first search and return nodes in
322 the component reachable from source.
324 depth_limit : int, optional (default=len(G))
325 Specify the maximum search depth.
327 Returns
328 -------
329 nodes: generator
330 A generator of nodes in a depth-first-search pre-ordering.
332 Examples
333 --------
334 >>> G = nx.path_graph(5)
335 >>> list(nx.dfs_preorder_nodes(G, source=0))
336 [0, 1, 2, 3, 4]
337 >>> list(nx.dfs_preorder_nodes(G, source=0, depth_limit=2))
338 [0, 1, 2]
340 Notes
341 -----
342 If a source is not specified then a source is chosen arbitrarily and
343 repeatedly until all components in the graph are searched.
345 The implementation of this function is adapted from David Eppstein's
346 depth-first search function in `PADS`_, with modifications
347 to allow depth limits based on the Wikipedia article
348 "`Depth-limited search`_".
350 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
351 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
353 See Also
354 --------
355 dfs_edges
356 dfs_postorder_nodes
357 dfs_labeled_edges
358 bfs_edges
359 """
360 edges = nx.dfs_labeled_edges(G, source=source, depth_limit=depth_limit)
361 return (v for u, v, d in edges if d == "forward")
364@nx._dispatch
365def dfs_labeled_edges(G, source=None, depth_limit=None):
366 """Iterate over edges in a depth-first-search (DFS) labeled by type.
368 Parameters
369 ----------
370 G : NetworkX graph
372 source : node, optional
373 Specify starting node for depth-first search and return edges in
374 the component reachable from source.
376 depth_limit : int, optional (default=len(G))
377 Specify the maximum search depth.
379 Returns
380 -------
381 edges: generator
382 A generator of triples of the form (*u*, *v*, *d*), where (*u*,
383 *v*) is the edge being explored in the depth-first search and *d*
384 is one of the strings 'forward', 'nontree', 'reverse', or 'reverse-depth_limit'.
385 A 'forward' edge is one in which *u* has been visited but *v* has
386 not. A 'nontree' edge is one in which both *u* and *v* have been
387 visited but the edge is not in the DFS tree. A 'reverse' edge is
388 one in which both *u* and *v* have been visited and the edge is in
389 the DFS tree. When the `depth_limit` is reached via a 'forward' edge,
390 a 'reverse' edge is immediately generated rather than the subtree
391 being explored. To indicate this flavor of 'reverse' edge, the string
392 yielded is 'reverse-depth_limit'.
394 Examples
395 --------
397 The labels reveal the complete transcript of the depth-first search
398 algorithm in more detail than, for example, :func:`dfs_edges`::
400 >>> from pprint import pprint
401 >>>
402 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 1)])
403 >>> pprint(list(nx.dfs_labeled_edges(G, source=0)))
404 [(0, 0, 'forward'),
405 (0, 1, 'forward'),
406 (1, 2, 'forward'),
407 (2, 1, 'nontree'),
408 (1, 2, 'reverse'),
409 (0, 1, 'reverse'),
410 (0, 0, 'reverse')]
412 Notes
413 -----
414 If a source is not specified then a source is chosen arbitrarily and
415 repeatedly until all components in the graph are searched.
417 The implementation of this function is adapted from David Eppstein's
418 depth-first search function in `PADS`_, with modifications
419 to allow depth limits based on the Wikipedia article
420 "`Depth-limited search`_".
422 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS
423 .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
425 See Also
426 --------
427 dfs_edges
428 dfs_preorder_nodes
429 dfs_postorder_nodes
430 """
431 # Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py
432 # by D. Eppstein, July 2004.
433 if source is None:
434 # edges for all components
435 nodes = G
436 else:
437 # edges for components with source
438 nodes = [source]
439 if depth_limit is None:
440 depth_limit = len(G)
442 visited = set()
443 for start in nodes:
444 if start in visited:
445 continue
446 yield start, start, "forward"
447 visited.add(start)
448 stack = [(start, iter(G[start]))]
449 depth_now = 1
450 while stack:
451 parent, children = stack[-1]
452 for child in children:
453 if child in visited:
454 yield parent, child, "nontree"
455 else:
456 yield parent, child, "forward"
457 visited.add(child)
458 if depth_now < depth_limit:
459 stack.append((child, iter(G[child])))
460 depth_now += 1
461 break
462 else:
463 yield parent, child, "reverse-depth_limit"
464 else:
465 stack.pop()
466 depth_now -= 1
467 if stack:
468 yield stack[-1][0], parent, "reverse"
469 yield start, start, "reverse"