def depth_first_search_with_parent_data(graph, root_node = None, adjacency_lists = None):
ordering = []<EOL>parent_lookup = {}<EOL>children_lookup = defaultdict(lambda: [])<EOL>all_nodes = graph.get_all_node_ids()<EOL>if not all_nodes:<EOL><INDENT>return ordering, parent_lookup, children_lookup<EOL><DEDENT>stack = deque()<EOL>discovered = defaultdict(lambda: False)<EOL>unvisited_nodes = set(all_nodes)<EOL>if root_node is None:<EOL><INDENT>root_node = all_nodes[<NUM_LIT:0>]<EOL><DEDENT>if adjacency_lists is None:<EOL><INDENT>adj = lambda v: graph.neighbors(v)<EOL><DEDENT>else:<EOL><INDENT>adj = lambda v: adjacency_lists[v]<EOL><DEDENT>stack.appendleft(root_node)<EOL>parent_lookup[root_node] = root_node<EOL>while True:<EOL><INDENT>while len(stack) > <NUM_LIT:0>:<EOL><INDENT>u = stack.popleft()<EOL>if not discovered[u]:<EOL><INDENT>discovered[u] = True<EOL>if u in unvisited_nodes:<EOL><INDENT>unvisited_nodes.remove(u)<EOL><DEDENT>ordering.append(u)<EOL>neighbors = adj(u)<EOL>for n in neighbors[::-<NUM_LIT:1>]:<EOL><INDENT>if discovered[n]:<EOL><INDENT>continue<EOL><DEDENT>stack.appendleft(n)<EOL>parent_lookup[n] = u<EOL>children_lookup[u].append(n)<EOL><DEDENT><DEDENT><DEDENT>if len(unvisited_nodes) > <NUM_LIT:0>:<EOL><INDENT>u = unvisited_nodes.pop()<EOL>stack.appendleft(u)<EOL><DEDENT>else:<EOL><INDENT>break<EOL><DEDENT><DEDENT>return ordering, parent_lookup, children_lookup<EOL>
Performs a depth-first search with visiting order of nodes determined by provided adjacency lists,
     and also returns a parent lookup dict and a children lookup dict.