def breadth_first_search(graph, root=None, filter=null()):
def bfs():<EOL><INDENT>"""<STR_LIT>"""<EOL>while (queue != []):<EOL><INDENT>node = queue.pop(<NUM_LIT:0>)<EOL>for other in graph[node]:<EOL><INDENT>if (other not in spanning_tree and filter(other, node)):<EOL><INDENT>queue.append(other)<EOL>ordering.append(other)<EOL>spanning_tree[other] = node<EOL><DEDENT><DEDENT><DEDENT><DEDENT>queue = []            <EOL>spanning_tree = {}    <EOL>ordering = []<EOL>filter.configure(graph, spanning_tree)<EOL>if (root is not None):<EOL><INDENT>if filter(root, None):<EOL><INDENT>queue.append(root)<EOL>ordering.append(root)<EOL>spanning_tree[root] = None<EOL>bfs()<EOL><DEDENT>return spanning_tree, ordering<EOL><DEDENT>for each in graph:<EOL><INDENT>if (each not in spanning_tree):<EOL><INDENT>if filter(each, None):<EOL><INDENT>queue.append(each)<EOL>ordering.append(each)<EOL>spanning_tree[each] = None<EOL>bfs()<EOL><DEDENT><DEDENT><DEDENT>return spanning_tree, ordering<EOL>
Breadth-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 tuple containing a dictionary and a list.
    1. Generated spanning tree
    2. Graph's level-based ordering