/usr/lib/python3/dist-packages/networkx/algorithms/traversal/depth_first_search.py is in python3-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | """
==================
Depth-first search
==================
Basic algorithms for depth-first searching.
Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py
by D. Eppstein, July 2004.
"""
__author__ = """\n""".join(['Aric Hagberg <hagberg@lanl.gov>'])
__all__ = ['dfs_edges', 'dfs_tree',
'dfs_predecessors', 'dfs_successors',
'dfs_preorder_nodes','dfs_postorder_nodes',
'dfs_labeled_edges']
import networkx as nx
from collections import defaultdict
def dfs_edges(G,source=None):
"""Produce edges in a depth-first-search starting at source."""
# Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py
# by D. Eppstein, July 2004.
if source is None:
# produce edges for all components
nodes=G
else:
# produce edges for components with source
nodes=[source]
visited=set()
for start in nodes:
if start in visited:
continue
visited.add(start)
stack = [(start,iter(G[start]))]
while stack:
parent,children = stack[-1]
try:
child = next(children)
if child not in visited:
yield parent,child
visited.add(child)
stack.append((child,iter(G[child])))
except StopIteration:
stack.pop()
def dfs_tree(G, source):
"""Return directed tree of depth-first-search from source."""
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))
return T
def dfs_predecessors(G, source=None):
"""Return dictionary of predecessors in depth-first-search from source."""
return dict((t,s) for s,t in dfs_edges(G,source=source))
def dfs_successors(G, source=None):
"""Return dictionary of successors in depth-first-search from source."""
d=defaultdict(list)
for s,t in dfs_edges(G,source=source):
d[s].append(t)
return dict(d)
def dfs_postorder_nodes(G,source=None):
"""Produce nodes in a depth-first-search post-ordering starting
from source.
"""
post=(v for u,v,d in nx.dfs_labeled_edges(G,source=source)
if d['dir']=='reverse')
# chain source to end of pre-ordering
# return chain(post,[source])
return post
def dfs_preorder_nodes(G,source=None):
"""Produce nodes in a depth-first-search pre-ordering starting at source."""
pre=(v for u,v,d in nx.dfs_labeled_edges(G,source=source)
if d['dir']=='forward')
# chain source to beginning of pre-ordering
# return chain([source],pre)
return pre
def dfs_labeled_edges(G,source=None):
"""Produce edges in a depth-first-search starting at source and
labeled by direction type (forward, reverse, nontree).
"""
# Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py
# by D. Eppstein, July 2004.
if source is None:
# produce edges for all components
nodes=G
else:
# produce edges for components with source
nodes=[source]
visited=set()
for start in nodes:
if start in visited:
continue
yield start,start,{'dir':'forward'}
visited.add(start)
stack = [(start,iter(G[start]))]
while stack:
parent,children = stack[-1]
try:
child = next(children)
if child in visited:
yield parent,child,{'dir':'nontree'}
else:
yield parent,child,{'dir':'forward'}
visited.add(child)
stack.append((child,iter(G[child])))
except StopIteration:
stack.pop()
if stack:
yield stack[-1][0],parent,{'dir':'reverse'}
yield start,start,{'dir':'reverse'}
|