#NEWLINE# def depth_first_search( graph , root = None , filter = null ( ) ) : #NEWLINE# #INDENT# "\n    Depth-first search.\n\n    @type  graph: graph, digraph\n    @param graph: Graph.\n    \n    @type  root: node\n    @param root: Optional root node (will explore only root's connected component)\n\n    @rtype:  tuple\n    @return: A tupple containing a dictionary and two lists:\n        1. Generated spanning tree\n        2. Graph's preordering\n        3. Graph's postordering\n    " #NEWLINE# recursionlimit = getrecursionlimit ( ) #NEWLINE# setrecursionlimit ( max ( ( len ( graph . nodes ( ) ) * 2 ) , recursionlimit ) ) #NEWLINE# def dfs( node ) : #NEWLINE# #INDENT# '\n        Depth-first search subfunction.\n        ' #NEWLINE# visited [ node ] = 1 #NEWLINE# pre . append ( node ) #NEWLINE# for each in graph [ node ] : #NEWLINE# #INDENT# if ( ( each not in visited ) and filter ( each , node ) ) : #NEWLINE# #INDENT# spanning_tree [ each ] = node #NEWLINE# dfs ( each ) #NEWLINE# #UNINDENT# #UNINDENT# post . append ( node ) #NEWLINE# #UNINDENT# visited = { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } #NEWLINE# spanning_tree = { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } #NEWLINE# pre = [ ] #NEWLINE# post = [ ] #NEWLINE# filter . configure ( graph , spanning_tree ) #NEWLINE# if ( root is not None ) : #NEWLINE# #INDENT# if filter ( root , None ) : #NEWLINE# #INDENT# spanning_tree [ root ] = None #NEWLINE# dfs ( root ) #NEWLINE# #UNINDENT# setrecursionlimit ( recursionlimit ) #NEWLINE# return ( spanning_tree , visited , post ) #NEWLINE# #UNINDENT# for each in graph : #NEWLINE# #INDENT# if ( ( each not in visited ) and filter ( each , None ) ) : #NEWLINE# #INDENT# spanning_tree [ each ] = None #NEWLINE# dfs ( each ) #NEWLINE# #UNINDENT# #UNINDENT# setrecursionlimit ( recursionlimit ) #NEWLINE# return ( spanning_tree , pre , post )