def depth_first_search(graph, root=None, filter=null()):
recursionlimit = getrecursionlimit()<EOL>setrecursionlimit(max(len(graph.nodes())*<NUM_LIT:2>,recursionlimit))<EOL>def dfs(node):<EOL><INDENT>"""<STR_LIT>"""<EOL>visited[node] = <NUM_LIT:1><EOL>pre.append(node)<EOL>for each in graph[node]:<EOL><INDENT>if (each not in visited and filter(each, node)):<EOL><INDENT>spanning_tree[each] = node<EOL>dfs(each)<EOL><DEDENT><DEDENT>post.append(node)<EOL><DEDENT>visited = {}            <EOL>spanning_tree = {}      <EOL>pre = []                <EOL>post = []               <EOL>filter.configure(graph, spanning_tree)<EOL>if (root is not None):<EOL><INDENT>if filter(root, None):<EOL><INDENT>spanning_tree[root] = None<EOL>dfs(root)<EOL><DEDENT>setrecursionlimit(recursionlimit)<EOL>return spanning_tree, pre, post<EOL><DEDENT>for each in graph:<EOL><INDENT>if (each not in visited and filter(each, None)):<EOL><INDENT>spanning_tree[each] = None<EOL>dfs(each)<EOL><DEDENT><DEDENT>setrecursionlimit(recursionlimit)<EOL>return (spanning_tree, pre, post)<EOL>
Depth-first search.

@type  graph: graph, digraph
@param graph: Graph.

@type  root: node
@param root: Optional root node (will explore only root's connected component)

@rtype:  tuple
@return: A tupple containing a dictionary and two lists:
    1. Generated spanning tree
    2. Graph's preordering
    3. Graph's postordering