Statistics
| Branch: | Revision:

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

1 2 3 5cef0f13 tiamilani ```# depth_first_search.py - depth-first traversals of a graph ``` ```# ``` ```# Copyright 2004-2019 NetworkX developers. ``` ```# ``` ```# This file is part of NetworkX. ``` ```# ``` ```# NetworkX is distributed under a BSD license; see LICENSE.txt for more ``` ```# information. ``` ```# ``` ```# Author: ``` ```# Aric Hagberg ``` ```"""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'] ``` ```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`_". ``` ``` ``` ``` .. _PADS: http://www.ics.uci.edu/~eppstein/PADS ``` ``` .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` 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 ``` ``` visited.add(start) ``` ``` 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 ``` ``` visited.add(child) ``` ``` if depth_now > 1: ``` ``` stack.append((child, depth_now - 1, iter(G[child]))) ``` ``` except StopIteration: ``` ``` stack.pop() ``` ```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: ``` ``` T.add_nodes_from(G) ``` ``` else: ``` ``` T.add_node(source) ``` ``` T.add_edges_from(dfs_edges(G, source, depth_limit)) ``` ``` return T ``` ```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. ``` ``` ``` ``` 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`_". ``` ``` ``` ``` .. _PADS: http://www.ics.uci.edu/~eppstein/PADS ``` ``` .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search ``` ``` """ ``` ``` return {t: s for s, t in dfs_edges(G, source, depth_limit)} ``` ```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. ``` ``` ``` ``` 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], 1: [2], 2: [3], 3: [4]} ``` ``` >>> nx.dfs_successors(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`_". ``` ``` ``` ``` .. _PADS: http://www.ics.uci.edu/~eppstein/PADS ``` ``` .. _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) ``` ```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. ``` ``` ``` ``` 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`_". ``` ``` ``` ``` .. _PADS: http://www.ics.uci.edu/~eppstein/PADS ``` ``` .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` 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') ``` ```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 nodes 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`_". ``` ``` ``` ``` .. _PADS: http://www.ics.uci.edu/~eppstein/PADS ``` ``` .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` 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') ``` ```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`_". ``` ``` ``` ``` .. _PADS: http://www.ics.uci.edu/~eppstein/PADS ``` ``` .. _Depth-limited search: https://en.wikipedia.org/wiki/Depth-limited_search ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` dfs_edges ``` ``` dfs_preorder_nodes ``` ``` dfs_postorder_nodes ``` ``` """ ``` ``` # Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py ``` ``` # 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' ``` ``` visited.add(start) ``` ``` 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' ``` ``` visited.add(child) ``` ``` if depth_now > 1: ``` ``` stack.append((child, depth_now - 1, iter(G[child]))) ``` ``` except StopIteration: ``` ``` stack.pop() ``` ``` if stack: ``` ``` yield stack[-1][0], parent, 'reverse' ``` ` yield start, start, 'reverse'`