## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / traversal / depth_first_search.py @ 5cef0f13

History | View | Annotate | Download (12.2 KB)

1 | 5cef0f13 | tiamilani | ```
# depth_first_search.py - depth-first traversals of a graph
``` |
---|---|---|---|

2 | ```
#
``` |
||

3 | ```
# Copyright 2004-2019 NetworkX developers.
``` |
||

4 | ```
#
``` |
||

5 | ```
# This file is part of NetworkX.
``` |
||

6 | ```
#
``` |
||

7 | ```
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
``` |
||

8 | ```
# information.
``` |
||

9 | ```
#
``` |
||

10 | ```
# Author:
``` |
||

11 | ```
# Aric Hagberg <aric.hagberg@gmail.com>
``` |
||

12 | ```
"""Basic algorithms for depth-first searching the nodes of a graph."""
``` |
||

13 | import networkx as nx |
||

14 | from collections import defaultdict |
||

15 | |||

16 | __all__ = ['dfs_edges', 'dfs_tree', |
||

17 | 'dfs_predecessors', 'dfs_successors', |
||

18 | 'dfs_preorder_nodes', 'dfs_postorder_nodes', |
||

19 | ```
'dfs_labeled_edges']
``` |
||

20 | |||

21 | |||

22 | def dfs_edges(G, source=None, depth_limit=None): |
||

23 | ```
"""Iterate over edges in a depth-first-search (DFS).
``` |
||

24 | ```
``` |
||

25 | ```
Perform a depth-first-search over the nodes of G and yield
``` |
||

26 | ```
the edges in order. This may not generate all edges in G (see edge_dfs).
``` |
||

27 | ```
``` |
||

28 | ```
Parameters
``` |
||

29 | ```
----------
``` |
||

30 | ```
G : NetworkX graph
``` |
||

31 | ```
``` |
||

32 | ```
source : node, optional
``` |
||

33 | ```
Specify starting node for depth-first search and return edges in
``` |
||

34 | ```
the component reachable from source.
``` |
||

35 | ```
``` |
||

36 | ```
depth_limit : int, optional (default=len(G))
``` |
||

37 | ```
Specify the maximum search depth.
``` |
||

38 | ```
``` |
||

39 | ```
Returns
``` |
||

40 | ```
-------
``` |
||

41 | ```
edges: generator
``` |
||

42 | ```
A generator of edges in the depth-first-search.
``` |
||

43 | ```
``` |
||

44 | ```
Examples
``` |
||

45 | ```
--------
``` |
||

46 | ```
>>> G = nx.path_graph(5)
``` |
||

47 | ```
>>> list(nx.dfs_edges(G, source=0))
``` |
||

48 | ```
[(0, 1), (1, 2), (2, 3), (3, 4)]
``` |
||

49 | ```
>>> list(nx.dfs_edges(G, source=0, depth_limit=2))
``` |
||

50 | ```
[(0, 1), (1, 2)]
``` |
||

51 | ```
``` |
||

52 | ```
Notes
``` |
||

53 | ```
-----
``` |
||

54 | ```
If a source is not specified then a source is chosen arbitrarily and
``` |
||

55 | ```
repeatedly until all components in the graph are searched.
``` |
||

56 | ```
``` |
||

57 | ```
The implementation of this function is adapted from David Eppstein's
``` |
||

58 | ```
depth-first search function in `PADS`_, with modifications
``` |
||

59 | ```
to allow depth limits based on the Wikipedia article
``` |
||

60 | ```
"`Depth-limited search`_".
``` |
||

61 | ```
``` |
||

62 | ```
.. _PADS: http://www.ics.uci.edu/~eppstein/PADS
``` |
||

63 | ```
.. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
``` |
||

64 | ```
``` |
||

65 | ```
See Also
``` |
||

66 | ```
--------
``` |
||

67 | ```
dfs_preorder_nodes
``` |
||

68 | ```
dfs_postorder_nodes
``` |
||

69 | ```
dfs_labeled_edges
``` |
||

70 | ```
edge_dfs
``` |
||

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 | ```
visited = set()
``` |
||

79 | if depth_limit is None: |
||

80 | ```
depth_limit = len(G)
``` |
||

81 | for start in nodes: |
||

82 | if start in visited: |
||

83 | ```
continue
``` |
||

84 | visited.add(start) |
||

85 | ```
stack = [(start, depth_limit, iter(G[start]))]
``` |
||

86 | ```
while stack:
``` |
||

87 | ```
parent, depth_now, children = stack[-1]
``` |
||

88 | ```
try:
``` |
||

89 | ```
child = next(children)
``` |
||

90 | if child not in visited: |
||

91 | ```
yield parent, child
``` |
||

92 | visited.add(child) |
||

93 | if depth_now > 1: |
||

94 | stack.append((child, depth_now - 1, iter(G[child]))) |
||

95 | except StopIteration: |
||

96 | stack.pop() |
||

97 | |||

98 | |||

99 | def dfs_tree(G, source=None, depth_limit=None): |
||

100 | ```
"""Returns oriented tree constructed from a depth-first-search from source.
``` |
||

101 | ```
``` |
||

102 | ```
Parameters
``` |
||

103 | ```
----------
``` |
||

104 | ```
G : NetworkX graph
``` |
||

105 | ```
``` |
||

106 | ```
source : node, optional
``` |
||

107 | ```
Specify starting node for depth-first search.
``` |
||

108 | ```
``` |
||

109 | ```
depth_limit : int, optional (default=len(G))
``` |
||

110 | ```
Specify the maximum search depth.
``` |
||

111 | ```
``` |
||

112 | ```
Returns
``` |
||

113 | ```
-------
``` |
||

114 | ```
T : NetworkX DiGraph
``` |
||

115 | ```
An oriented tree
``` |
||

116 | ```
``` |
||

117 | ```
Examples
``` |
||

118 | ```
--------
``` |
||

119 | ```
>>> G = nx.path_graph(5)
``` |
||

120 | ```
>>> T = nx.dfs_tree(G, source=0, depth_limit=2)
``` |
||

121 | ```
>>> list(T.edges())
``` |
||

122 | ```
[(0, 1), (1, 2)]
``` |
||

123 | ```
>>> T = nx.dfs_tree(G, source=0)
``` |
||

124 | ```
>>> list(T.edges())
``` |
||

125 | ```
[(0, 1), (1, 2), (2, 3), (3, 4)]
``` |
||

126 | ```
``` |
||

127 | ```
"""
``` |
||

128 | T = nx.DiGraph() |
||

129 | if source is None: |
||

130 | T.add_nodes_from(G) |
||

131 | ```
else:
``` |
||

132 | T.add_node(source) |
||

133 | T.add_edges_from(dfs_edges(G, source, depth_limit)) |
||

134 | ```
return T
``` |
||

135 | |||

136 | |||

137 | def dfs_predecessors(G, source=None, depth_limit=None): |
||

138 | ```
"""Returns dictionary of predecessors in depth-first-search from source.
``` |
||

139 | ```
``` |
||

140 | ```
Parameters
``` |
||

141 | ```
----------
``` |
||

142 | ```
G : NetworkX graph
``` |
||

143 | ```
``` |
||

144 | ```
source : node, optional
``` |
||

145 | ```
Specify starting node for depth-first search.
``` |
||

146 | ```
``` |
||

147 | ```
depth_limit : int, optional (default=len(G))
``` |
||

148 | ```
Specify the maximum search depth.
``` |
||

149 | ```
``` |
||

150 | ```
Returns
``` |
||

151 | ```
-------
``` |
||

152 | ```
pred: dict
``` |
||

153 | ```
A dictionary with nodes as keys and predecessor nodes as values.
``` |
||

154 | ```
``` |
||

155 | ```
Examples
``` |
||

156 | ```
--------
``` |
||

157 | ```
>>> G = nx.path_graph(4)
``` |
||

158 | ```
>>> nx.dfs_predecessors(G, source=0)
``` |
||

159 | ```
{1: 0, 2: 1, 3: 2}
``` |
||

160 | ```
>>> nx.dfs_predecessors(G, source=0, depth_limit=2)
``` |
||

161 | ```
{1: 0, 2: 1}
``` |
||

162 | ```
``` |
||

163 | ```
Notes
``` |
||

164 | ```
-----
``` |
||

165 | ```
If a source is not specified then a source is chosen arbitrarily and
``` |
||

166 | ```
repeatedly until all components in the graph are searched.
``` |
||

167 | ```
``` |
||

168 | ```
The implementation of this function is adapted from David Eppstein's
``` |
||

169 | ```
depth-first search function in `PADS`_, with modifications
``` |
||

170 | ```
to allow depth limits based on the Wikipedia article
``` |
||

171 | ```
"`Depth-limited search`_".
``` |
||

172 | ```
``` |
||

173 | ```
.. _PADS: http://www.ics.uci.edu/~eppstein/PADS
``` |
||

174 | ```
.. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
``` |
||

175 | ```
"""
``` |
||

176 | return {t: s for s, t in dfs_edges(G, source, depth_limit)} |
||

177 | |||

178 | |||

179 | def dfs_successors(G, source=None, depth_limit=None): |
||

180 | ```
"""Returns dictionary of successors in depth-first-search from source.
``` |
||

181 | ```
``` |
||

182 | ```
Parameters
``` |
||

183 | ```
----------
``` |
||

184 | ```
G : NetworkX graph
``` |
||

185 | ```
``` |
||

186 | ```
source : node, optional
``` |
||

187 | ```
Specify starting node for depth-first search.
``` |
||

188 | ```
``` |
||

189 | ```
depth_limit : int, optional (default=len(G))
``` |
||

190 | ```
Specify the maximum search depth.
``` |
||

191 | ```
``` |
||

192 | ```
Returns
``` |
||

193 | ```
-------
``` |
||

194 | ```
succ: dict
``` |
||

195 | ```
A dictionary with nodes as keys and list of successor nodes as values.
``` |
||

196 | ```
``` |
||

197 | ```
Examples
``` |
||

198 | ```
--------
``` |
||

199 | ```
>>> G = nx.path_graph(5)
``` |
||

200 | ```
>>> nx.dfs_successors(G, source=0)
``` |
||

201 | ```
{0: [1], 1: [2], 2: [3], 3: [4]}
``` |
||

202 | ```
>>> nx.dfs_successors(G, source=0, depth_limit=2)
``` |
||

203 | ```
{0: [1], 1: [2]}
``` |
||

204 | ```
``` |
||

205 | ```
Notes
``` |
||

206 | ```
-----
``` |
||

207 | ```
If a source is not specified then a source is chosen arbitrarily and
``` |
||

208 | ```
repeatedly until all components in the graph are searched.
``` |
||

209 | ```
``` |
||

210 | ```
The implementation of this function is adapted from David Eppstein's
``` |
||

211 | ```
depth-first search function in `PADS`_, with modifications
``` |
||

212 | ```
to allow depth limits based on the Wikipedia article
``` |
||

213 | ```
"`Depth-limited search`_".
``` |
||

214 | ```
``` |
||

215 | ```
.. _PADS: http://www.ics.uci.edu/~eppstein/PADS
``` |
||

216 | ```
.. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
``` |
||

217 | ```
"""
``` |
||

218 | ```
d = defaultdict(list)
``` |
||

219 | for s, t in dfs_edges(G, source=source, depth_limit=depth_limit): |
||

220 | d[s].append(t) |
||

221 | return dict(d) |
||

222 | |||

223 | |||

224 | def dfs_postorder_nodes(G, source=None, depth_limit=None): |
||

225 | ```
"""Generate nodes in a depth-first-search post-ordering starting at source.
``` |
||

226 | ```
``` |
||

227 | ```
Parameters
``` |
||

228 | ```
----------
``` |
||

229 | ```
G : NetworkX graph
``` |
||

230 | ```
``` |
||

231 | ```
source : node, optional
``` |
||

232 | ```
Specify starting node for depth-first search.
``` |
||

233 | ```
``` |
||

234 | ```
depth_limit : int, optional (default=len(G))
``` |
||

235 | ```
Specify the maximum search depth.
``` |
||

236 | ```
``` |
||

237 | ```
Returns
``` |
||

238 | ```
-------
``` |
||

239 | ```
nodes: generator
``` |
||

240 | ```
A generator of nodes in a depth-first-search post-ordering.
``` |
||

241 | ```
``` |
||

242 | ```
Examples
``` |
||

243 | ```
--------
``` |
||

244 | ```
>>> G = nx.path_graph(5)
``` |
||

245 | ```
>>> list(nx.dfs_postorder_nodes(G, source=0))
``` |
||

246 | ```
[4, 3, 2, 1, 0]
``` |
||

247 | ```
>>> list(nx.dfs_postorder_nodes(G, source=0, depth_limit=2))
``` |
||

248 | ```
[1, 0]
``` |
||

249 | ```
``` |
||

250 | ```
Notes
``` |
||

251 | ```
-----
``` |
||

252 | ```
If a source is not specified then a source is chosen arbitrarily and
``` |
||

253 | ```
repeatedly until all components in the graph are searched.
``` |
||

254 | ```
``` |
||

255 | ```
The implementation of this function is adapted from David Eppstein's
``` |
||

256 | ```
depth-first search function in `PADS`_, with modifications
``` |
||

257 | ```
to allow depth limits based on the Wikipedia article
``` |
||

258 | ```
"`Depth-limited search`_".
``` |
||

259 | ```
``` |
||

260 | ```
.. _PADS: http://www.ics.uci.edu/~eppstein/PADS
``` |
||

261 | ```
.. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
``` |
||

262 | ```
``` |
||

263 | ```
See Also
``` |
||

264 | ```
--------
``` |
||

265 | ```
dfs_edges
``` |
||

266 | ```
dfs_preorder_nodes
``` |
||

267 | ```
dfs_labeled_edges
``` |
||

268 | ```
"""
``` |
||

269 | edges = nx.dfs_labeled_edges(G, source=source, depth_limit=depth_limit) |
||

270 | return (v for u, v, d in edges if d == 'reverse') |
||

271 | |||

272 | |||

273 | def dfs_preorder_nodes(G, source=None, depth_limit=None): |
||

274 | ```
"""Generate nodes in a depth-first-search pre-ordering starting at source.
``` |
||

275 | ```
``` |
||

276 | ```
Parameters
``` |
||

277 | ```
----------
``` |
||

278 | ```
G : NetworkX graph
``` |
||

279 | ```
``` |
||

280 | ```
source : node, optional
``` |
||

281 | ```
Specify starting node for depth-first search and return nodes in
``` |
||

282 | ```
the component reachable from source.
``` |
||

283 | ```
``` |
||

284 | ```
depth_limit : int, optional (default=len(G))
``` |
||

285 | ```
Specify the maximum search depth.
``` |
||

286 | ```
``` |
||

287 | ```
Returns
``` |
||

288 | ```
-------
``` |
||

289 | ```
nodes: generator
``` |
||

290 | ```
A generator of nodes in a depth-first-search pre-ordering.
``` |
||

291 | ```
``` |
||

292 | ```
Examples
``` |
||

293 | ```
--------
``` |
||

294 | ```
>>> G = nx.path_graph(5)
``` |
||

295 | ```
>>> list(nx.dfs_preorder_nodes(G, source=0))
``` |
||

296 | ```
[0, 1, 2, 3, 4]
``` |
||

297 | ```
>>> list(nx.dfs_preorder_nodes(G, source=0, depth_limit=2))
``` |
||

298 | ```
[0, 1, 2]
``` |
||

299 | ```
``` |
||

300 | ```
Notes
``` |
||

301 | ```
-----
``` |
||

302 | ```
If a source is not specified then a source is chosen arbitrarily and
``` |
||

303 | ```
repeatedly until all components in the graph are searched.
``` |
||

304 | ```
``` |
||

305 | ```
The implementation of this function is adapted from David Eppstein's
``` |
||

306 | ```
depth-first search function in `PADS`_, with modifications
``` |
||

307 | ```
to allow depth limits based on the Wikipedia article
``` |
||

308 | ```
"`Depth-limited search`_".
``` |
||

309 | ```
``` |
||

310 | ```
.. _PADS: http://www.ics.uci.edu/~eppstein/PADS
``` |
||

311 | ```
.. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
``` |
||

312 | ```
``` |
||

313 | ```
See Also
``` |
||

314 | ```
--------
``` |
||

315 | ```
dfs_edges
``` |
||

316 | ```
dfs_postorder_nodes
``` |
||

317 | ```
dfs_labeled_edges
``` |
||

318 | ```
"""
``` |
||

319 | edges = nx.dfs_labeled_edges(G, source=source, depth_limit=depth_limit) |
||

320 | return (v for u, v, d in edges if d == 'forward') |
||

321 | |||

322 | |||

323 | def dfs_labeled_edges(G, source=None, depth_limit=None): |
||

324 | ```
"""Iterate over edges in a depth-first-search (DFS) labeled by type.
``` |
||

325 | ```
``` |
||

326 | ```
Parameters
``` |
||

327 | ```
----------
``` |
||

328 | ```
G : NetworkX graph
``` |
||

329 | ```
``` |
||

330 | ```
source : node, optional
``` |
||

331 | ```
Specify starting node for depth-first search and return edges in
``` |
||

332 | ```
the component reachable from source.
``` |
||

333 | ```
``` |
||

334 | ```
depth_limit : int, optional (default=len(G))
``` |
||

335 | ```
Specify the maximum search depth.
``` |
||

336 | ```
``` |
||

337 | ```
Returns
``` |
||

338 | ```
-------
``` |
||

339 | ```
edges: generator
``` |
||

340 | ```
A generator of triples of the form (*u*, *v*, *d*), where (*u*,
``` |
||

341 | ```
*v*) is the edge being explored in the depth-first search and *d*
``` |
||

342 | ```
is one of the strings 'forward', 'nontree', or 'reverse'. A
``` |
||

343 | ```
'forward' edge is one in which *u* has been visited but *v* has
``` |
||

344 | ```
not. A 'nontree' edge is one in which both *u* and *v* have been
``` |
||

345 | ```
visited but the edge is not in the DFS tree. A 'reverse' edge is
``` |
||

346 | ```
on in which both *u* and *v* have been visited and the edge is in
``` |
||

347 | ```
the DFS tree.
``` |
||

348 | ```
``` |
||

349 | ```
Examples
``` |
||

350 | ```
--------
``` |
||

351 | ```
``` |
||

352 | ```
The labels reveal the complete transcript of the depth-first search
``` |
||

353 | ```
algorithm in more detail than, for example, :func:`dfs_edges`::
``` |
||

354 | ```
``` |
||

355 | ```
>>> from pprint import pprint
``` |
||

356 | ```
>>>
``` |
||

357 | ```
>>> G = nx.DiGraph([(0, 1), (1, 2), (2, 1)])
``` |
||

358 | ```
>>> pprint(list(nx.dfs_labeled_edges(G, source=0)))
``` |
||

359 | ```
[(0, 0, 'forward'),
``` |
||

360 | ```
(0, 1, 'forward'),
``` |
||

361 | ```
(1, 2, 'forward'),
``` |
||

362 | ```
(2, 1, 'nontree'),
``` |
||

363 | ```
(1, 2, 'reverse'),
``` |
||

364 | ```
(0, 1, 'reverse'),
``` |
||

365 | ```
(0, 0, 'reverse')]
``` |
||

366 | ```
``` |
||

367 | ```
Notes
``` |
||

368 | ```
-----
``` |
||

369 | ```
If a source is not specified then a source is chosen arbitrarily and
``` |
||

370 | ```
repeatedly until all components in the graph are searched.
``` |
||

371 | ```
``` |
||

372 | ```
The implementation of this function is adapted from David Eppstein's
``` |
||

373 | ```
depth-first search function in `PADS`_, with modifications
``` |
||

374 | ```
to allow depth limits based on the Wikipedia article
``` |
||

375 | ```
"`Depth-limited search`_".
``` |
||

376 | ```
``` |
||

377 | ```
.. _PADS: http://www.ics.uci.edu/~eppstein/PADS
``` |
||

378 | ```
.. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
``` |
||

379 | ```
``` |
||

380 | ```
See Also
``` |
||

381 | ```
--------
``` |
||

382 | ```
dfs_edges
``` |
||

383 | ```
dfs_preorder_nodes
``` |
||

384 | ```
dfs_postorder_nodes
``` |
||

385 | ```
"""
``` |
||

386 | ```
# Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py
``` |
||

387 | ```
# by D. Eppstein, July 2004.
``` |
||

388 | if source is None: |
||

389 | ```
# edges for all components
``` |
||

390 | nodes = G |
||

391 | ```
else:
``` |
||

392 | ```
# edges for components with source
``` |
||

393 | nodes = [source] |
||

394 | ```
visited = set()
``` |
||

395 | if depth_limit is None: |
||

396 | ```
depth_limit = len(G)
``` |
||

397 | for start in nodes: |
||

398 | if start in visited: |
||

399 | ```
continue
``` |
||

400 | yield start, start, 'forward' |
||

401 | visited.add(start) |
||

402 | ```
stack = [(start, depth_limit, iter(G[start]))]
``` |
||

403 | ```
while stack:
``` |
||

404 | ```
parent, depth_now, children = stack[-1]
``` |
||

405 | ```
try:
``` |
||

406 | ```
child = next(children)
``` |
||

407 | if child in visited: |
||

408 | yield parent, child, 'nontree' |
||

409 | ```
else:
``` |
||

410 | yield parent, child, 'forward' |
||

411 | visited.add(child) |
||

412 | if depth_now > 1: |
||

413 | stack.append((child, depth_now - 1, iter(G[child]))) |
||

414 | except StopIteration: |
||

415 | stack.pop() |
||

416 | ```
if stack:
``` |
||

417 | yield stack[-1][0], parent, 'reverse' |
||

418 | yield start, start, 'reverse' |