Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.traversal.depth_first_search

# depth_first_search.py - depth-first traversals of a graph
#
#
# This file is part of NetworkX.
#
# information.
#
# Author:
#   Aric Hagberg <aric.hagberg@gmail.com>
"""Basic algorithms for depth-first searching the nodes of a graph."""
import networkx as nx
from collections import defaultdict

__all__ = ['dfs_edges', 'dfs_tree',
'dfs_predecessors', 'dfs_successors',
'dfs_preorder_nodes', 'dfs_postorder_nodes',
'dfs_labeled_edges']

[docs]def dfs_edges(G, source=None, depth_limit=None):
"""Iterate over edges in a depth-first-search (DFS).

Perform a depth-first-search over the nodes of G and yield
the edges in order. This may not generate all edges in G (see edge_dfs).

Parameters
----------
G : NetworkX graph

source : node, optional
Specify starting node for depth-first search and return edges in
the component reachable from source.

depth_limit : int, optional (default=len(G))
Specify the maximum search depth.

Returns
-------
edges: generator
A generator of edges in the depth-first-search.

Examples
--------
>>> G = nx.path_graph(5)
>>> list(nx.dfs_edges(G, source=0))
[(0, 1), (1, 2), (2, 3), (3, 4)]
>>> list(nx.dfs_edges(G, source=0, depth_limit=2))
[(0, 1), (1, 2)]

Notes
-----
If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.

The implementation of this function is adapted from David Eppstein's
depth-first search function in PADS_, with modifications
to allow depth limits based on the Wikipedia article
"Depth-limited search_".

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

--------
dfs_preorder_nodes
dfs_postorder_nodes
dfs_labeled_edges
edge_dfs
"""
if source is None:
# edges for all components
nodes = G
else:
# edges for components with source
nodes = [source]
visited = set()
if depth_limit is None:
depth_limit = len(G)
for start in nodes:
if start in visited:
continue
stack = [(start, depth_limit, iter(G[start]))]
while stack:
parent, depth_now, children = stack[-1]
try:
child = next(children)
if child not in visited:
yield parent, child
if depth_now > 1:
stack.append((child, depth_now - 1, iter(G[child])))
except StopIteration:
stack.pop()

[docs]def dfs_tree(G, source=None, depth_limit=None):
"""Returns oriented tree constructed from a depth-first-search from source.

Parameters
----------
G : NetworkX graph

source : node, optional
Specify starting node for depth-first search.

depth_limit : int, optional (default=len(G))
Specify the maximum search depth.

Returns
-------
T : NetworkX DiGraph
An oriented tree

Examples
--------
>>> G = nx.path_graph(5)
>>> T = nx.dfs_tree(G, source=0, depth_limit=2)
>>> list(T.edges())
[(0, 1), (1, 2)]
>>> T = nx.dfs_tree(G, source=0)
>>> list(T.edges())
[(0, 1), (1, 2), (2, 3), (3, 4)]

"""
T = nx.DiGraph()
if source is None:
else:
return T

[docs]def dfs_predecessors(G, source=None, depth_limit=None):
"""Returns dictionary of predecessors in depth-first-search from source.

Parameters
----------
G : NetworkX graph

source : node, optional
Specify starting node for depth-first search and return edges in
the component reachable from source.

depth_limit : int, optional (default=len(G))
Specify the maximum search depth.

Returns
-------
pred: dict
A dictionary with nodes as keys and predecessor nodes as values.

Examples
--------
>>> G = nx.path_graph(4)
>>> nx.dfs_predecessors(G, source=0)
{1: 0, 2: 1, 3: 2}
>>> nx.dfs_predecessors(G, source=0, depth_limit=2)
{1: 0, 2: 1}

Notes
-----
If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.

The implementation of this function is adapted from David Eppstein's
depth-first search function in PADS_, with modifications
to allow depth limits based on the Wikipedia article
"Depth-limited search_".

.. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
"""
return {t: s for s, t in dfs_edges(G, source, depth_limit)}

[docs]def dfs_successors(G, source=None, depth_limit=None):
"""Returns dictionary of successors in depth-first-search from source.

Parameters
----------
G : NetworkX graph

source : node, optional
Specify starting node for depth-first search and return edges in
the component reachable from source.

depth_limit : int, optional (default=len(G))
Specify the maximum search depth.

Returns
-------
succ: dict
A dictionary with nodes as keys and list of successor nodes as values.

Examples
--------
>>> G = nx.path_graph(5)
>>> nx.dfs_successors(G, source=0)
{0: , 1: , 2: , 3: }
>>> nx.dfs_successors(G, source=0, depth_limit=2)
{0: , 1: }

Notes
-----
If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.

The implementation of this function is adapted from David Eppstein's
depth-first search function in PADS_, with modifications
to allow depth limits based on the Wikipedia article
"Depth-limited search_".

.. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search
"""
d = defaultdict(list)
for s, t in dfs_edges(G, source=source, depth_limit=depth_limit):
d[s].append(t)
return dict(d)

[docs]def dfs_postorder_nodes(G, source=None, depth_limit=None):
"""Generate nodes in a depth-first-search post-ordering starting at source.

Parameters
----------
G : NetworkX graph

source : node, optional
Specify starting node for depth-first search and return edges in
the component reachable from source.

depth_limit : int, optional (default=len(G))
Specify the maximum search depth.

Returns
-------
nodes: generator
A generator of nodes in a depth-first-search post-ordering.

Examples
--------
>>> G = nx.path_graph(5)
>>> list(nx.dfs_postorder_nodes(G, source=0))
[4, 3, 2, 1, 0]
>>> list(nx.dfs_postorder_nodes(G, source=0, depth_limit=2))
[1, 0]

Notes
-----
If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.

The implementation of this function is adapted from David Eppstein's
depth-first search function in PADS_, with modifications
to allow depth limits based on the Wikipedia article
"Depth-limited search_".

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

--------
dfs_edges
dfs_preorder_nodes
dfs_labeled_edges
"""
edges = nx.dfs_labeled_edges(G, source=source, depth_limit=depth_limit)
return (v for u, v, d in edges if d == 'reverse')

[docs]def dfs_preorder_nodes(G, source=None, depth_limit=None):
"""Generate nodes in a depth-first-search pre-ordering starting at source.

Parameters
----------
G : NetworkX graph

source : node, optional
Specify starting node for depth-first search and return edges in
the component reachable from source.

depth_limit : int, optional (default=len(G))
Specify the maximum search depth.

Returns
-------
nodes: generator
A generator of nodes in a depth-first-search pre-ordering.

Examples
--------
>>> G = nx.path_graph(5)
>>> list(nx.dfs_preorder_nodes(G, source=0))
[0, 1, 2, 3, 4]
>>> list(nx.dfs_preorder_nodes(G, source=0, depth_limit=2))
[0, 1, 2]

Notes
-----
If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.

The implementation of this function is adapted from David Eppstein's
depth-first search function in PADS_, with modifications
to allow depth limits based on the Wikipedia article
"Depth-limited search_".

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

--------
dfs_edges
dfs_postorder_nodes
dfs_labeled_edges
"""
edges = nx.dfs_labeled_edges(G, source=source, depth_limit=depth_limit)
return (v for u, v, d in edges if d == 'forward')

[docs]def dfs_labeled_edges(G, source=None, depth_limit=None):
"""Iterate over edges in a depth-first-search (DFS) labeled by type.

Parameters
----------
G : NetworkX graph

source : node, optional
Specify starting node for depth-first search and return edges in
the component reachable from source.

depth_limit : int, optional (default=len(G))
Specify the maximum search depth.

Returns
-------
edges: generator
A generator of triples of the form (*u*, *v*, *d*), where (*u*,
*v*) is the edge being explored in the depth-first search and *d*
is one of the strings 'forward', 'nontree', or 'reverse'. A
'forward' edge is one in which *u* has been visited but *v* has
not. A 'nontree' edge is one in which both *u* and *v* have been
visited but the edge is not in the DFS tree. A 'reverse' edge is
on in which both *u* and *v* have been visited and the edge is in
the DFS tree.

Examples
--------

The labels reveal the complete transcript of the depth-first search
algorithm in more detail than, for example, :func:dfs_edges::

>>> from pprint import pprint
>>>
>>> G = nx.DiGraph([(0, 1), (1, 2), (2, 1)])
>>> pprint(list(nx.dfs_labeled_edges(G, source=0)))
[(0, 0, 'forward'),
(0, 1, 'forward'),
(1, 2, 'forward'),
(2, 1, 'nontree'),
(1, 2, 'reverse'),
(0, 1, 'reverse'),
(0, 0, 'reverse')]

Notes
-----
If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.

The implementation of this function is adapted from David Eppstein's
depth-first search function in PADS_, with modifications
to allow depth limits based on the Wikipedia article
"Depth-limited search_".

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

--------
dfs_edges
dfs_preorder_nodes
dfs_postorder_nodes
"""
# by D. Eppstein, July 2004.
if source is None:
# edges for all components
nodes = G
else:
# edges for components with source
nodes = [source]
visited = set()
if depth_limit is None:
depth_limit = len(G)
for start in nodes:
if start in visited:
continue
yield start, start, 'forward'
stack = [(start, depth_limit, iter(G[start]))]
while stack:
parent, depth_now, children = stack[-1]
try:
child = next(children)
if child in visited:
yield parent, child, 'nontree'
else:
yield parent, child, 'forward'