<s> """<STR_LIT>""" <EOL> import networkx as nx <EOL> from collections import defaultdict <EOL> __author__ = """<STR_LIT:\n>""" . join ( [ '<STR_LIT>' ] ) <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' ] <EOL> def dfs_edges ( G , source = None ) : <EOL> """<STR_LIT>""" <EOL> if source is None : <EOL> nodes = G <EOL> else : <EOL> nodes = [ source ] <EOL> visited = set ( ) <EOL> for start in nodes : <EOL> if start in visited : <EOL> continue <EOL> visited . add ( start ) <EOL> stack = [ ( start , iter ( G [ start ] ) ) ] <EOL> while stack : <EOL> parent , children = stack [ - <NUM_LIT:1> ] <EOL> try : <EOL> child = next ( children ) <EOL> if child not in visited : <EOL> yield parent , child <EOL> visited . add ( child ) <EOL> stack . append ( ( child , iter ( G [ child ] ) ) ) <EOL> except StopIteration : <EOL> stack . pop ( ) <EOL> def dfs_tree ( G , source ) : <EOL> """<STR_LIT>""" <EOL> T = nx . DiGraph ( ) <EOL> if source is None : <EOL> T . add_nodes_from ( G ) <EOL> else : <EOL> T . add_node ( source ) <EOL> T . add_edges_from ( dfs_edges ( G , source ) ) <EOL> return T <EOL> def dfs_predecessors ( G , source = None ) : <EOL> """<STR_LIT>""" <EOL> return dict ( ( t , s ) for s , t in dfs_edges ( G , source = source ) ) <EOL> def dfs_successors ( G , source = None ) : <EOL> """<STR_LIT>""" <EOL> d = defaultdict ( list ) <EOL> for s , t in dfs_edges ( G , source = source ) : <EOL> d [ s ] . append ( t ) <EOL> return dict ( d ) <EOL> def dfs_postorder_nodes ( G , source = None ) : <EOL> """<STR_LIT>""" <EOL> post = ( v for u , v , d in nx . dfs_labeled_edges ( G , source = source ) <EOL> if d [ '<STR_LIT>' ] == '<STR_LIT>' ) <EOL> return post <EOL> def dfs_preorder_nodes ( G , source = None ) : <EOL> """<STR_LIT>""" <EOL> pre = ( v for u , v , d in nx . dfs_labeled_edges ( G , source = source ) <EOL> if d [ '<STR_LIT>' ] == '<STR_LIT>' ) <EOL> return pre <EOL> def dfs_labeled_edges ( G , source = None ) : <EOL> """<STR_LIT>""" <EOL> if source is None : <EOL> nodes = G <EOL> else : <EOL> nodes = [ source ] <EOL> visited = set ( ) <EOL> for start in nodes : <EOL> if start in visited : <EOL> continue <EOL> yield start , start , { '<STR_LIT>' : '<STR_LIT>' } <EOL> visited . add ( start ) <EOL> stack = [ ( start , iter ( G [ start ] ) ) ] <EOL> while stack : <EOL> parent , children = stack [ - <NUM_LIT:1> ] <EOL> try : <EOL> child = next ( children ) <EOL> if child in visited : <EOL> yield parent , child , { '<STR_LIT>' : '<STR_LIT>' } <EOL> else : <EOL> yield parent , child , { '<STR_LIT>' : '<STR_LIT>' } <EOL> visited . add ( child ) <EOL> stack . append ( ( child , iter ( G [ child ] ) ) ) <EOL> except StopIteration : <EOL> stack . pop ( ) <EOL> if stack : <EOL> yield stack [ - <NUM_LIT:1> ] [ <NUM_LIT:0> ] , parent , { '<STR_LIT>' : '<STR_LIT>' } <EOL> yield start , start , { '<STR_LIT>' : '<STR_LIT>' } </s>
