networkx.algorithms.traversal.depth_first_search.dfs_labeled_edges¶

dfs_labeled_edges
(G, source=None, depth_limit=None)[source]¶ Iterate over edges in a depthfirstsearch (DFS) labeled by type.
Parameters:  G (NetworkX graph)
 source (node, optional) – Specify starting node for depthfirst search and return edges in the component reachable from source.
 depth_limit (int, optional (default=len(G))) – Specify the maximum search depth.
Returns: edges – A generator of triples of the form (u, v, d), where (u, v) is the edge being explored in the depthfirst 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.
Return type: generator
Examples
The labels reveal the complete transcript of the depthfirst search algorithm in more detail than, for example,
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 depthfirst search function in PADS, with modifications to allow depth limits based on the Wikipedia article “Depthlimited search”.
See also