def graph_search(nx_graph, target_species):
    """Search nodal graph and generate list of species to exclude

    Parameters
    ----------
    nx_graph : obj
        networkx graph object of solution\
    target_species : list
        List of target species to search from

    Returns
    -------
    essential_nodes : str
        String containing names of essential species
    """

    if len(target_species) > 1:
        essential_nodes = list()
        for target in target_species:
            essential = list(nx.dfs_preorder_nodes(nx_graph, target))
            for sp in essential:
                if sp not in essential_nodes:
                    essential_nodes.append(sp)
    else:
        essential_nodes = list(nx.dfs_preorder_nodes(nx_graph, target_species[0]))

    return essential_nodes

def convert_location_type(location, source_type, desired_type):
    """ Converts the provided location into the desired location_type

    This will perform a DFS on the location graph to find connected components
    to the supplied node and then filter by the desired location_type.
    Basically if we consider our datacenter layout a DAG, then this method will
    search any nodes connected to the source location looking for the proper
    type.

    Examples:
    Assume available_location_types() is ['ecosystem', 'region', 'habitat'],
    and the location graph is:
     - prod
       - uswest1-prod
         - uswest1aprod
         - uswest1bprod

    # convert a habitat to the containing ecosystem
    convert_location_type('uswest1aprod', 'habitat', 'ecosystem') -> ['prod']
    # convert a region to the member habitats
    convert_location_type('uswest1-prod', 'region', 'habitat') ->
        ['uswest1aprod', 'uswest1bprod']

    :param location: A string that represents a location, e.g. "devc"
    :param source_type: A string that should exist inside the list returned
        by available_location_types. This is the type of the provided location
        and is optional. This exists because the names in the DAG may not be
        unique across all levels, and providing this type will disambiguate
        between which "devc" you mean (ecosystem or habitat).
    :param desired_type: A string that should exist inside the
        list returned by available_location_types. This is the desired type
        that the caller wants.
    :returns: locations, A list of locations that are of the location_type.
        These will be connected components filtered by type. Note that
        these results are sorted for calling consistency before returning.
    :rtype: list of strings
    """
    search_node = '{0}_{1}'.format(location, source_type)

    direction = compare_types(desired_type, source_type)
    candidates = set()
    if direction < 0:
        # We are converting "up", and have to walk the tree backwards
        reversed_graph = nx.reverse(location_graph())
        candidates |= set(nx.dfs_preorder_nodes(reversed_graph, search_node))
    else:
        candidates |= set(nx.dfs_preorder_nodes(location_graph(), search_node))

    # Only return results that are of the correct type
    result = filter(lambda x: x.endswith('_' + desired_type), candidates)
    return sorted([loc[:loc.rfind('_')] for loc in result])

def triangulate_rectangular_contours(landscape):
    """
    Given an enumerated contour landscape tree, returns a list of the triangles in the landscape metaphor.
    """
    root_node = [n for n in landscape if landscape.in_degree(n) == 0][0]
    triangles = []

    # handle the root node
    child_node = landscape.successors(root_node)[0]
    outer_inds = landscape.node[root_node]["contour"].indices
    inner_inds = landscape.node[child_node]["contour"].indices
    triangles.extend(triangulate_nested_rectangle(outer_inds, inner_inds))

    # now work through the remaining nodes
    dfs_nodes = nx.dfs_preorder_nodes(landscape, root_node)
    dfs_nodes.next()
    for node in dfs_nodes:
        # we only do something if this is not a leaf
        is_leaf = landscape.out_degree(node) == 0
        if not is_leaf:
            outer_saddle_contour = landscape.node[node]["contour"]
            for inner_saddle_contour in outer_saddle_contour.children:
                child = inner_saddle_contour.child
                child_contour = landscape.node[child]["contour"]
                inner_saddle_indices = inner_saddle_contour.indices
                child_indices = child_contour.indices

                if child_contour.type == "leaf":
                    triangles.extend(triangulate_nested_point(inner_saddle_indices, child_indices[0]))
                else:
                    triangles.extend(triangulate_nested_rectangle(inner_saddle_indices, child_indices))

    return triangles
    return np.array(points)

def _validate_comp_pre(RG):
    ''' validates connection at a certain level '''

    # use topological sort to find root.
    root = nx.topological_sort(RG)[0]

    # try to solve each node.
    for p in nx.dfs_preorder_nodes(RG, source=root):

        # dive down.
        if RG.node[p]['graph'] != None:
            _validate_comp_pre(RG.node[p]['graph'])

        # skip if child.
        if len(RG.successors(p)) == 0:
            continue

        # check children.
        for q in RG.successors(p):

            # get sets.
            pcomp = RG.node[p]['comp']
            qcomp = RG.node[q]['comp']

            # compute cuts.
            cutGIVEN = RG[p][q]['cut']
            cutTEST = pcomp.intersection(qcomp)

            # test cut.
            if cutGIVEN != cutTEST:
                print "bad cut"
                print cutGIVEN, cutTEST
                print n, parent
                sys.exit()

 def reachable(self, source, observed):
     """
     Finds a set of reachable (in the sense of d-separation) nodes in graph.
     :param self: target graph
     :param source: source node name
     :param observed: a sequence of observed nodes
     :return: a set of reachable nodes
     """
     V = nx.number_of_nodes(self)
     A = set(sum([list(nx.dfs_preorder_nodes(self.reverse(), z)) for z in observed], []))
     Z = observed
     L = [(source, 'up')]
     V = set()
     result = set()
     while len(L) > 0:
         x, d = L.pop()
         if (x, d) in V:
             continue
         if x not in Z:
             result.add((x, d))
         V.add((x, d))
         if d == 'up' and x not in Z:
             for y in self.predecessors_iter(x):
                 L.append((y, 'up'))
             for y in self.successors_iter(x):
                 L.append((y, 'down'))
         elif d == 'down':
             if x in A:
                 for y in self.predecessors_iter(x):
                     L.append((y, 'up'))
             if x not in Z:
                 for y in self.successors_iter(x):
                     L.append((y, 'down'))
     result = set([x[0] for x in result])
     return result - {source}

def process_boosters(dag):

    dag_nx = utils.dag_to_nx(dag)

    processed_dag = dict()
    sub_dags = []
    for k, spec in dag.items():
        if spec[1][0] == 'booBegin':
            input_name = spec[0]
            for node in nx.dfs_preorder_nodes(dag_nx, k):
                node_type = dag[node][1][0]
                if node == k:
                    continue
                if node_type == 'booster':
                    sub_dags.append(dag[node][1][2])
                if node_type == 'booEnd':
                    sub_dags = [normalize_dag(sd) for sd in sub_dags]
                    processed_dag[k] = (input_name, ['booster', {'sub_dags': sub_dags}], dag[node][2])
                    sub_dags = []
                    break
        elif spec[1][0] in ['booster', 'booEnd']:
            continue
        else:
            processed_dag[k] = spec

    return processed_dag

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 transitive_closure(G):
    """ Returns transitive closure of a directed graph

    The transitive closure of G = (V,E) is a graph G+ = (V,E+) such that
    for all v,w in V there is an edge (v,w) in E+ if and only if there
    is a non-null path from v to w in G.

    Parameters
    ----------
    G : NetworkX DiGraph
        Graph

    Returns
    -------
    TC : NetworkX DiGraph
        Graph

    Raises
    ------
    NetworkXNotImplemented
        If G is not directed

    References
    ----------
    .. [1] http://www.ics.uci.edu/~eppstein/PADS/PartialOrder.py

    """
    TC = nx.DiGraph()
    TC.add_nodes_from(G.nodes())
    TC.add_edges_from(G.edges())
    for v in G:
        TC.add_edges_from((v, u) for u in nx.dfs_preorder_nodes(G, source=v)
                          if v != u)
    return TC

 def calc_ProjFeatures(self):
     #Add edges to projection Graph
     for node in self.gM.nodes():
         neighbours=self.G.neighbors(node)
         for item in neighbours:
             if self.gM.has_node(item):
                 try:
                     if node!=item:
                         self.gM.add_edge(node,item)
                 except:
                     pass
     
        
     #Initialize and Calculate features
     closed=[];self.gM_connComp=0;
     self.gM_maxDeg=0;self.gM_sizeMaxComp=0
     
     for node in self.gM.nodes():
         if node not in closed:
             x=nx.dfs_preorder_nodes(self.gM,node)
             pre=list(x)                
             closed=closed +pre      
             self.gM_connComp=  self.gM_connComp+1
             if len(pre)>self.gM_sizeMaxComp:
                 self.gM_sizeMaxComp=len(pre)
         if self.gM_maxDeg < self.gM.degree(node):
                 self.gM_maxDeg=self.gM.degree(node)
     return

    def _retrieve_skycoords(V):
        coords_l = []
        # Accessing the borders one by one. At this step, V_subgraphs contains a list of cycles
        # (i.e. one describing the external border of the MOC component and several describing the holes
        # found in the MOC component).
        V_subgraphs = nx.connected_component_subgraphs(V)
        for v in V_subgraphs:
            # Compute the MST for each cycle
            v = nx.convert_node_labels_to_integers(v)
            mst = nx.minimum_spanning_tree(v)
            # Get one end of the span tree by looping over its node and checking if the degree is one
            src = None
            for (node, deg) in mst.degree():
                if deg == 1:
                    src = node
                    break

            # Get the unordered lon and lat
            ra = np.asarray(list(nx.get_node_attributes(v, 'ra').values()))
            dec = np.asarray(list(nx.get_node_attributes(v, 'dec').values()))
            coords = np.vstack((ra, dec)).T
            # Get the ordering from the MST
            ordering = np.asarray(list(nx.dfs_preorder_nodes(mst, src)))
            # Order the coords
            coords = coords[ordering]
            # Get a skycoord containing N coordinates computed from the Nx2 `coords` array
            coords = SkyCoord(coords, unit="deg")
            coords_l.append(coords)

        return coords_l

def descendants(G, x):
    """
    Set of all descendants of node in a graph, not including itself.
    :param G: target graph
    :param x: target node
    :return: set of descendants
    """
    return set(nx.dfs_preorder_nodes(G, x)) - {x}

 def recalculateDependent(self, node, returnResult=False):
     if self.dependencyGraph.has_node(node):
         generator = dfs_preorder_nodes(self.dependencyGraph, node)
         next(generator )   # skip the first, that is us
         nodelist = list(generator)  # make a list, we need it twice 
         result = [ self.recalculateNode(node) for node in nodelist ]                
         return (nodelist, result) if returnResult else nodelist     # return which ones were re-calculated, so gui can be updated 
     return (list(), list()) if returnResult else list()

    def propose(self):
        self.oldgraph = self.graph.copy()
        self.memo_entropy = None

        g = self.graph
        if g.edges():
            scheme = np.random.randint(3)
        else:
            scheme = np.random.randint(2)

        nodes = g.nodes()

        if scheme == 0: # Perturb probabilities
            n1 = np.random.randint(len(nodes))
            if g.predecessors(n1):
                g.node[n1]['delta'] = st.beta.rvs(0.4,0.4)
                g.node[n1]['eta'] = st.beta.rvs(0.4,0.4)
                g.node[n1]['marginal'] = np.nan
            else: 
                g.node[n1]['delta'] = np.nan
                g.node[n1]['eta'] = np.nan
                g.node[n1]['marginal'] = np.random.rand()

        if scheme == 1: # Add or change edge 'backwards'
            while True:
                random.shuffle(nodes) #inefficient
                n0 = nodes[0]
                n1 = nodes[1]
                if g.predecessors(n1):
                    g.remove_edge(g.predecessors(n1)[0], n1)
                g.add_edge(n0, n1)

                if nx.is_directed_acyclic_graph(g):
                    break
                else:
                    g = self.graph = self.oldgraph.copy()

            g.node[n1]['delta'] = st.beta.rvs(0.4,0.4)
            g.node[n1]['eta'] = st.beta.rvs(0.4,0.4)
            g.node[n1]['marginal'] = np.nan

        if scheme == 2: # Remove edge
            edges = g.edges()
            edge = edges[np.random.randint(len(edges))]
            n1 = edge[1]
            g.remove_edge(*edge)

            g.node[n1]['delta'] = np.nan
            g.node[n1]['eta'] = np.nan
            g.node[n1]['marginal'] = np.random.rand()

        #print len(g.edges())
        trav = nx.dfs_preorder_nodes(g,n1) # FIXME, this may be a problem, dfs_preorder 
        # was not what I thought it was before
        trav.next()
        for node in trav:
            g.node[node]['marginal'] = np.nan #invalidate downstream cached marginals

def kosaraju_strongly_connected_components(G, source=None):
    """Generate nodes in strongly connected components of graph.

    Parameters
    ----------
    G : NetworkX Graph
        An directed graph.

    Returns
    -------
    comp : generator of sets
        A genrator of sets of nodes, one for each strongly connected
        component of G.

    Raises
    ------
    NetworkXNotImplemented:
        If G is undirected.

    Examples
    --------
    Generate a sorted list of strongly connected components, largest first.

    >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
    >>> nx.add_cycle(G, [10, 11, 12])
    >>> [len(c) for c in sorted(nx.kosaraju_strongly_connected_components(G),
    ...                         key=len, reverse=True)]
    [4, 3]

    If you only want the largest component, it's more efficient to
    use max instead of sort.

    >>> largest = max(nx.kosaraju_strongly_connected_components(G), key=len)

    See Also
    --------
    connected_components
    weakly_connected_components

    Notes
    -----
    Uses Kosaraju's algorithm.

    """
    with nx.utils.reversed(G):
        post = list(nx.dfs_postorder_nodes(G, source=source))

    seen = set()
    while post:
        r = post.pop()
        if r in seen:
            continue
        c = nx.dfs_preorder_nodes(G, r)
        new = {v for v in c if v not in seen}
        yield new
        seen.update(new)

 def getStructure(self):
     nodes = []
     for n in nx.dfs_preorder_nodes(self.structure, self.root):
         p = self.structure.in_edges(n)
         if len(p) == 0:
             p = ""
         else:
             p = p[0][0]
         nodes.append((n, self.structure.node[n]['name'], p))
     return nodes

def order_intervals(intervals, start):
	""" computes the intersection graph of the intervals, takes the data attribute
		of the intervals as nodes, hence intervals belonging to the same segment
		correspond to one node in the graph.
		returns a traversal starting from start. """
	G = dict(((i.data, []) for i in intervals)) 

	#right to left sweep according to left endpoints
	#linear time with proper sorting
	stack = []
	for i in sorted(intervals, reverse = True, key = lambda i: i.endpoints):
		l, r = i.endpoints

		while stack and r>stack[-1].endpoints[1]:
			i2 = stack.pop()

		if stack and r>= stack[-1].endpoints[0]:
			G[i.data].append(stack[-1].data)
			G[stack[-1].data].append(i.data)

		stack.append(i)

	#left to right sweep according to right endpoints
	stack = []
	for i in sorted(intervals, key = lambda i: (i.endpoints[1], i.endpoints[0])):
		l, r = i.endpoints

		while stack and l<stack[-1].endpoints[0]:
			i2 = stack.pop()

		if stack and l<= stack[-1].endpoints[1]:
			G[i.data].append(stack[-1].data)
			G[stack[-1].data].append(i.data)
		stack.append(i)

	order = list(nx.dfs_preorder_nodes(G,start))

	if not len(order) == len(G):
		seen = set(order)
		for v in G:
			if v in seen: continue
			raise IntervalException(list(nx.dfs_preorder_nodes(G,v)))
	return order

def transitiveReduction(g):
    ''' from http://stackoverflow.com/questions/17078696/im-trying-to-perform-the-transitive-reduction-of-directed-graph-in-python'''
    for n1 in g.nodes_iter():
        if g.has_edge(n1, n1):
            g.remove_edge(n1, n1)
        for n2 in g.successors(n1):
            for n3 in g.successors(n2):
                for n4 in nx.dfs_preorder_nodes(g, n3):
                    if g.has_edge(n1, n4):
                        g.remove_edge(n1, n4) 

    def describe(self, data_type):
        G = self.hierarchy
        df = self.get_data(data_type)

        for n in nx.dfs_postorder_nodes(G, "all"):
            G.node[n]["cnt"] = len(df[df["area"] == n].index) + pl.sum([G.node[c]["cnt"] for c in G.successors(n)])
            G.node[n]["depth"] = nx.shortest_path_length(G, "all", n)

        for n in nx.dfs_preorder_nodes(G, "all"):
            if G.node[n]["cnt"] > 0:
                print " *" * G.node[n]["depth"], n, int(G.node[n]["cnt"])

 def _find_ship_and_adjacents(self, i):
     """DFS work to find adjacent ships comprising the new larger ship."""
     ship, adj_decks, adj_ships = [i], [], []
     for adj_tile in self._adjacent_tiles(i):
         if adj_tile in self._decks:
             adj_decks.append(adj_tile)
             adj_ship = list(networkx.dfs_preorder_nodes(self._decks,
                                                         adj_tile))
             adj_ships.append(adj_ship)
             ship.extend(adj_ship)
     return sorted(ship), adj_decks, adj_ships

def _esd_get_node_to_set(T, root,
        node_to_allowed_states=None, P_default=None):
    # Construct the bfs tree, preserving transition matrices on the edges.
    T_bfs = nx.DiGraph()
    for na, nb in nx.bfs_edges(T, root):
        T_bfs.add_edge(na, nb)
        edge_object = T[na][nb]
        P = edge_object.get('P', None)
        if P is not None:
            T_bfs[na][nb]['P'] = P

    # Get the ordered list of nodes in preorder.
    preorder_nodes = list(nx.dfs_preorder_nodes(T, root))

    # Get the set of all states in all transition matrices.
    state_set = set()
    for na, nb in T_bfs.edges():
        edge_object = T_bfs[na][nb]
        P = edge_object.get('P', P_default)
        state_set.update(set(P))
    sorted_states = sorted(state_set)

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

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

    # Construct the edge-specific transition matrix as an ndim-3 numpy array.
    esd_transitions = _get_esd_transitions(
            T_bfs, preorder_nodes, sorted_states, P_default=P_default)

    # Backward pass to update the state mask.
    pyfelscore.mcy_esd_get_node_to_pset(
            tree_csr_indices,
            tree_csr_indptr,
            esd_transitions,
            state_mask)

    # Forward pass to update the state mask.
    pyfelscore.esd_get_node_to_set(
            tree_csr_indices,
            tree_csr_indptr,
            esd_transitions,
            state_mask)

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

    # Return the node_to_set dict.
    return node_to_set