def run(self, G, O, mi, sigma2):
        """
        Main
        :param G: graph
        :param O: list of observers <<<< ACTIVE observers !
        :param mi: mean
        :param sigma2: variance
        :return:
        """
        # TODO : consider only active observers !
        first_node = O[0]

        # Compute the delay vector d relative to first_node
        d = self.observed_delay(G, O)

        # calculates F for the first node: fulfills max
        max = self.main_function(first_node, O, d, nx.bfs_tree(G, source=first_node), mi, sigma2)

        source = first_node  # SEE HOW WE CAN DO IT
        # calculates the maximum F
        for s in G:  # FIXME is this G_a ?
            # Compute the spanning tree rooted at s
            T = nx.bfs_tree(G, source=s)
            F = self.main_function(s, O, d, T, mi, sigma2)

            if F > max:
                max = F
                source = s
        return source

 def relations(self, sty1, sty2, rela, source_vocab=[]):
     """Return set of relations between provided semantic types"""
     # collect descendant/child types for each semantic type
     network = self.semantic_network.graph("isa")
     sty1 = [node for node in nx.bfs_tree(network, sty1)]
     sty2 = [node for node in nx.bfs_tree(network, sty2)]
     sty1 = " OR ".join(map(lambda x:"STY='%s'" % x, sty1))
     sty2 = " OR ".join(map(lambda x:"STY='%s'" % x, sty2))
     
     # override object default source vocabulary?
     if source_vocab:
         sab = self._source_vocab_sql(source_vocab)
     else:
         sab = self._source_vocab_sql(self.source_vocab)
     sab = "" if not sab else sab + " AND"
     
     sql = """
     SELECT DISTINCT CUI2,CUI1 FROM 
     (SELECT * FROM MRREL WHERE RELA='%s') AS R,
     (SELECT L.CUI FROM MRCONSO AS L, MRSTY AS LS WHERE (%s) AND L.CUI=LS.CUI) AS LARG,
     (SELECT R.CUI FROM MRCONSO AS R, MRSTY AS RS WHERE (%s) AND R.CUI=RS.CUI) AS RARG
     WHERE %s ((LARG.CUI=CUI2) AND (RARG.CUI=CUI1));"""
    
     sql = sql % (rela,sty1,sty2,sab)
     results = self.conn.query(sql)
     
     return results

def family_tree(digraph, target):
    """
    Subsets graph to return predecessors and successors with a blood relation
    to the target node
    """
    all_successors = nx.bfs_tree(digraph, target, reverse=False)
    all_predecessors = nx.bfs_tree(digraph, target, reverse=True)
    subdig = digraph.subgraph(itertools.chain(
            [target], all_successors, all_predecessors)).copy()
    return subdig

 def Algorithm(self, G, O, mi, sigma2):
     d = self.observed_delay(G, O)
     first_node = O[0]
     # calculates F for the first node: fulfills max
     MAX = self.main_function(first_node, O, d, nx.bfs_tree(G, source=first_node), mi, sigma2)
     source = first_node  # SEE HOW WE CAN DO IT
     # calculates the maximum F
     for s in G:
         T = nx.bfs_tree(G, source=s)
         F = self.main_function(s, d, T, mi)
         if F > MAX:
             MAX = F
             source = s
     return source

def bfs_heur(graph, query_nodes, a = 1, include_solution = False):
	""" Approximately maximize discrepancy on graph. """
	
	best_root = None
	best_d    = -1
	for root in query_nodes:
		sys.stderr.write('.')
		tree = nx.bfs_tree(graph, root)
		d, solution_graph = tree_offline(tree, query_nodes, root, a, False)
		if d > best_d:
			best_d = d
			best_root = root
	tree = nx.bfs_tree(graph, best_root)
	sys.stderr.write('\n')
	return tree_offline(tree, query_nodes, best_root, a, include_solution)

def objecttree_get_all_skeletons(request, project_id=None, node_id=None):
    """ Retrieve all skeleton ids for a given node in the object tree. """
    g = get_annotation_graph( project_id )
    potential_skeletons = nx.bfs_tree(g, int(node_id)).nodes()
    result = tuple(nid for nid in potential_skeletons if 'skeleton' == g.node[nid]['class'])
    json_return = json.dumps({'skeletons': result}, sort_keys=True, indent=4)
    return HttpResponse(json_return, content_type='text/json')

 def get_spanning_tree(self, node, use_infectors = False):
     ''' Returns a networkx spanning tree of the adjacency matrix
     rooted at node'''
     G = nx.bfs_tree(self.graph, node).to_undirected()
     if not nx.is_connected(G):
         return None
     return G

 def test_bfs_tree_isolates(self):
     G = nx.Graph()
     G.add_node(1)
     G.add_node(2)
     T = nx.bfs_tree(G, source=1)
     assert_equal(sorted(T.nodes()), [1])
     assert_equal(sorted(T.edges()), [])

def _get_node_to_pset_same_transition_matrix(T, root, P,
        node_to_allowed_states=None):
    T_bfs = nx.bfs_tree(T, root)
    preorder_nodes = list(nx.dfs_preorder_nodes(T, root))
    sorted_states = sorted(P)

    # Put the tree into sparse boolean csr form.
    tree_csr_indices, tree_csr_indptr = _digraph_to_bool_csr(
            T_bfs, preorder_nodes)

    # Put the transition matrix into sparse boolean csr form.
    trans_csr_indices, trans_csr_indptr = _digraph_to_bool_csr(
            P, sorted_states)

    # Define the state mask.
    state_mask = _define_state_mask(
            node_to_allowed_states, preorder_nodes, sorted_states)

    # Update the state mask.
    pyfelscore.mcy_get_node_to_pset(
            tree_csr_indices,
            tree_csr_indptr,
            trans_csr_indices,
            trans_csr_indptr,
            state_mask)

    # Convert the updated state mask into a node_to_pset dict.
    node_to_pset = _state_mask_to_dict(
            state_mask, preorder_nodes, sorted_states)

    # Return the node_to_pset dict.
    return node_to_pset

def graph(ttl):
    T = nx.bfs_tree(G,ttl)


    edgeAccuracy = 0
    years = []
    for e in T.edges():
        t1 = e[0]
        t2 = e[1]
        y1 = 0
        y2 = 0
        for d in Data:
            if(d['title'] == t1):
                y1 = d['year']
            if(d['title'] == t2):
                y2 = d['year']
        #print e
        #print str(y1) + " | " + str(y2)
        if(y1 > y2):
            edgeAccuracy += 1
        if(years == []):
            years.append(y1)
            years.append(y2)
        else:
            years.append(y2)

    yearsAccuracy = 0
    for y in range(1,len(years)):
        if( years[y] > years[y-1]):
            yearsAccuracy +=1

    print(T.edges())
    #print years
    #print "edge Accuracy = " + str(edgeAccuracy)
    print ttl + " = " + str(yearsAccuracy)

def get_graph_compressed(graph_data):
    """
    Getting the Compressed Graph. A Compressed Graph is a DAG, after removing
    unreachable graph nodes, and getting bfs tree.
    """
    # Creating the directed graphs, for graph1.
    dgraph = nx.DiGraph(graph_data)
    if not dgraph.has_node(0):  # adding root node, on one node case.
        dgraph.add_node(0)
    # First, remove non reachable nodes, from the root.
    # assuming node 0 is the function root node.
    bfsy = nx.bfs_tree(dgraph, 0).nodes()
    if 0 not in bfsy:
        bfsy.append(0)
    for i in dgraph.nodes():
        if i not in bfsy:
            dgraph.remove_node(i)

    # Second, _collapse some vertices together...
    dgraph = _collapse(dgraph)

    # create DAG's (computing scc) from digraph before.
    compressed_graph = nx.condensation(dgraph)

    return compressed_graph.edges()

def all_dag_covers(_graph, condenseg, final_sccs, tree_type):
    initial_scc = _graph.node[_graph.graph["initial"]]["scc_index"]
    if tree_type=="bfs":
        condense_tree = networkx.bfs_tree(condenseg, initial_scc)
    elif tree_type=="dfs":
        condense_tree = networkx.dfs_tree(condenseg, initial_scc)
    rest_edges = [edge for edge in condenseg.edges() if edge not in condense_tree.edges()]

    all_tree_branch(_graph, condenseg, final_sccs, tree_type, condense_tree)
    dag_paths = condenseg.graph["condense_paths"]
    for rest_edge in rest_edges:
        path = networkx.shortest_path(condense_tree, initial_scc, rest_edge[0])
        _node = rest_edge[1]
        while True:
            if condense_tree.out_degree(_node)==0 and condense_tree.in_degree(_node)==1:
                if "_final" in str(_node):
                    path.append(_node)
                else:
                    path = path + condense_tree.node[_node]["continue_path"]
                break
            else:
                path.append(_node)
                _node = condense_tree.edge[_node].keys()[0]

        dag_paths.append(path)

    condenseg.graph["condense_paths"] = dag_paths
    return dag_paths

    def keep(self, areas=['all'], sexes=['male', 'female', 'total'], start_year=-pl.inf, end_year=pl.inf):
        """ Modify model to feature only desired area/sex/year(s)

        :Parameters:
          - `areas` : list of str, optional
          - `sexes` : list of str, optional
          - `start_year` : int, optional
          - `end_year` : int, optional

        """
        if 'all' not in areas:
            self.hierarchy.remove_node('all')
            for area in areas:
                self.hierarchy.add_edge('all', area)
            self.hierarchy = nx.bfs_tree(self.hierarchy, 'all')

            def relevant_row(i):
                area = self.input_data['area'][i]
                return (area in self.hierarchy) or (area == 'all')

            self.input_data = self.input_data.select(relevant_row)
            self.nodes_to_fit = set(self.hierarchy.nodes()) & set(self.nodes_to_fit)

        self.input_data = self.input_data.select(lambda i: self.input_data['sex'][i] in sexes)

        self.input_data = self.input_data.select(lambda i: self.input_data['year_end'][i] >= start_year)
        self.input_data = self.input_data.select(lambda i: self.input_data['year_start'][i] <= end_year)

        print 'kept %d rows of data' % len(self.input_data.index)

def main(args):

    # read and validate the rate matrix info from the sqlite3 database file
    conn = sqlite3.connect(args.rates)
    cursor = conn.cursor()
    states, distn, Q = get_rate_matrix_info(cursor)
    conn.close()

    # Get a more convenient form of the rate matrix for forward simulation.
    rates, P = cmedbutil.decompose_rates(Q)

    # extract the unrooted tree from the tree db file
    conn = sqlite3.connect(args.tree)
    cursor = conn.cursor()
    G = get_unrooted_tree(cursor)
    conn.close()

    # Pick the smallest vertex of G as an arbitrary root for sampling.
    # This choice can be made arbitrarily
    # because the rate matrix is currently defined to be time-reversible.
    root = min(G.nodes())

    # Build a directed breadth first tree starting at the distinguished vertex.
    # Note that the tree built by nx.bfs_tree and the edges yielded
    # by nx.bfs_edges do not retain the edge attributes.
    G_dag = nx.bfs_tree(G, root)
    for a, b in G_dag.edges():
        G_dag[a][b]['blen'] = G[a][b]['blen']

    # sample the unconditional columns of the alignment
    conn = sqlite3.connect(args.outfile)
    build_alignment_table(
            args.length, args.only_leaves,
            conn, root, G_dag, distn, states, rates, P)
    conn.close()

def chiral_order(atoms, chiral_atom, depth=6):
  # Create a list of ordered atoms to be passed back
  ordered = []
  # Do a quick check whether there are multiple hydrogens
  neighbors = atoms.neighbors(chiral_atom)
  hydrogens = [atom for atom in neighbors if atom.element == "H"]
  if len(hydrogens) < 2:
    tree = nx.bfs_tree(atoms, chiral_atom)
    # Generate the list of shortest paths in the molecule, neglecting the trivial path [chiral_atom]
    paths = sorted(nx.single_source_shortest_path(tree, chiral_atom, depth).values(), reverse = True)[:-1]
    while paths:
      # Pop the first element (highest priority path) from the list of paths and remove any duplicates.
      path = paths.pop(0)
      paths_no_dups = [unpruned for unpruned in paths if unpruned != path]
      # If there are any duplicates, the paths list will be smaller and we can't resolve a highest priority yet.
      if len(paths_no_dups) != len(paths):
        paths = paths_no_dups
      # Otherwise, the path is higher priority than all the other paths, so its second atom is the neighbour with
      # highest priority.
      else:
        ranked_atom = path[1]
        ordered.append(ranked_atom)
        # Drop all the paths containing our ranked atom.
        paths = [unpruned for unpruned in paths if unpruned[1] is not ranked_atom]
  return ordered

 def generate_graph(self):
     #nodes
     n = int(self.lineEdit_2.text())
     self.graph = nx.balanced_tree(2, n)
     self.graph = nx.bfs_tree(self.graph, 0)
     #self.pos = nx.circular_layout(self.graph)
     self.pos = nx.graphviz_layout(self.graph, prog='dot')
     self.draw_graph()

def get_state_segmentation(G_in):
    """
    Segment the tree according to state.
    This does not use the branch lengths or the layout.
    @param G_in: undirected graph with state annotation on edges
    @return: segment_isostate_list, isostate_to_parity
    """

    # get leaf vertices
    # pick an arbitrary leaf as a distinguished (root) vertex
    vertices = list(G_in)
    leaves = sorted(v for v in vertices if len(G_in.neighbors(v)) == 1)
    root = leaves[0]

    # Build a directed breadth first tree starting at the distinguished vertex.
    # Note that the tree built by nx.bfs_tree and the edges yielded
    # by nx.bfs_edges do not retain the edge attributes.
    G_dag = nx.bfs_tree(G_in, root)

    # initialize the tree of isostate adjacencies
    G_isostate = nx.Graph()

    # Each contig is defined by a set of edges.
    root_state = G_in[root][G_dag.successors(root)[0]]['state']
    root_edge_list = []
    root_contig_index = 0
    contig_states = [root_state]
    contig_edge_lists = [root_edge_list]
    vertex_to_contig_index = {root : root_contig_index}
    for node in nx.topological_sort(G_dag):
        ci = vertex_to_contig_index[node]
        ci_state = contig_states[ci]
        successors = G_dag.successors(node)
        for v in successors:
            state = G_in[node][v]['state']
            if state == ci_state:
                contig_edge_lists[ci].append((node, v))
                vertex_to_contig_index[v] = ci
            else:
                ci_next = len(contig_states)
                G_isostate.add_edge(ci, ci_next)
                vertex_to_contig_index[v] = ci_next
                contig_states.append(state)
                contig_edge_lists.append([(node, v)])

    # Convert the G_isostate graph into a map from
    # isostate labels to parities.
    isostate_to_parity = {0 : 0}
    for va, vb in nx.bfs_edges(G_isostate, 0):
        isostate_to_parity[vb] = 1 - isostate_to_parity[va]
    
    # Get the isostate label associated with each edge.
    va_vb_isostate_list = []
    for isostate_label, edge_list in enumerate(contig_edge_lists):
        for va, vb in edge_list:
            va_vb_isostate_list.append((va, vb, isostate_label))
    return va_vb_isostate_list, isostate_to_parity

def simply_bfs(_graph, condenseg, final_sccs):
    initial_scc = _graph.node[_graph.graph["initial"]]["scc_index"]
    condense_tree = networkx.bfs_tree(condenseg, initial_scc)
    dag_paths = []
    for final_scc in final_sccs:
        path = networkx.shortest_path(condense_tree, initial_scc, final_scc)
        dag_paths.append(path)

    condenseg.graph["condense_paths"] = dag_paths
    return dag_paths

def BFS_levels_comm(G, s):
  if G:
    T = nx.bfs_tree(G,s)
    nextlevel = set()
    succ = T.successors(s)
    prevlevel = set()
    prevlevel.add(s)
    level = 0
    
    children = [set() for proc in range(gnumprocs)] # ALL children
    failedchildren = [0 for proc in range(gnumprocs)]
    peers = [set() for proc in range(gnumprocs)]
    failed_parents = [set() for proc in range(gnumprocs)]

    while (len(succ) > 0):
      level += 1
      comm = 0
      hidegedges = 0
      for node in succ:
        node_succ = set(T.successors(node))
        nodeproc = proc_of_node(node)
        nodeneighbs = set(G.neighbors(node))
        # all children
        children[nodeproc] = children[nodeproc].union(nodeneighbs.intersection(node_succ))      
        # number of failed children
        failedchildren[nodeproc] += len(children[nodeproc].intersection(nodeneighbs.intersection(node_succ))) 
        # peer
        peers[nodeproc] = peers[nodeproc].union(nodeneighbs.intersection(succ))
        # failed parent
        failed_parents[nodeproc] = failed_parents[nodeproc].union(nodeneighbs.intersection(prevlevel)) 
        for targnode in nodeneighbs:
          if (G.degree(targnode) > ghideg):
            hidegedges += 1
        for targnode in node_succ:
          if (share_same_proc(node, targnode) != 1) :
            comm += 1
        nextlevel = nextlevel.union(node_succ)
      prevlevel = succ
      succ = list(nextlevel)
      nextlevel.clear()
      if (level < gmaxlevels):
        #vec_children[level] += len(succ)
        vec_hideg[level] += hidegedges
        for i in range(gnumprocs):
          vec_failedchildren[level] += failedchildren[i]
          vec_children[level] += len(children[i])
          vec_peers[level] += len(peers[i])
          vec_parents[level] += len(failed_parents[i])

          children[i].clear()
          peers[i].clear()
          failed_parents[i].clear()
          failedchildren[i] = 0
          hidegedges = 0
      yield comm

def noTimingComponentSizes(vanillaDiGraph):
    distributionOfSizes = []

    for guy in vanillaDiGraph.nodes():
        tree = nx.bfs_tree(vanillaDiGraph, guy)
        distributionOfSizes.append(len(tree.nodes()))
        
        if len(tree.nodes())>10:
            print guy
    
    return distributionOfSizes