Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (12.2 KB)

1
# 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'