def find_subgraph(self, start=None, end=None):
        """Find subgraph by provided start and end endpoints

        :param end: task name
        :param start: task name
        :param include: iterable with task names
        :returns: DeploymentGraph instance (subgraph from original)
        """
        working_graph = self

        if start:
            # simply traverse starting from root,
            # A->B, B->C, B->D, C->E
            working_graph = self.subgraph(
                nx.dfs_postorder_nodes(working_graph, start))

        if end:
            # nx.dfs_postorder_nodes traverses graph from specified point
            # to the end by following successors, here is example:
            # A->B, C->D, B->D , and we want to traverse up to the D
            # for this we need to reverse graph and make it
            # B->A, D->C, D->B and use dfs_postorder
            working_graph = self.subgraph(nx.dfs_postorder_nodes(
                working_graph.reverse(), end))

        return working_graph

    def _analyze(self):

        region = self._region.recursive_copy()

        # visit the region in post-order DFS
        parent_map = { }
        stack = [ region ]

        while stack:
            current_region = stack[-1]

            has_region = False
            for node in networkx.dfs_postorder_nodes(current_region.graph, current_region.head):
                if type(node) is GraphRegion:
                    stack.append(node)
                    parent_map[node] = current_region
                    has_region = True

            if not has_region:
                # pop this region from the stack
                stack.pop()

                # Get the parent region
                parent_region = parent_map.get(current_region, None)
                # structure this region
                st = self.project.analyses.Structurer(current_region, parent_region=parent_region)
                # replace this region with the resulting node in its parent region... if it's not an orphan
                if not parent_region:
                    # this is the top-level region. we are done!
                    self.result = st.result
                    break
                else:
                    self._replace_region(parent_region, current_region, st.result)

def dfs_edges(G):
    """
    (source,target) for edges in directed spanning tree resulting from depth
    first search
    """
    DG = nx.dfs_tree(G)
    return [(src,targ) for targ in nx.dfs_postorder_nodes(DG) for src in DG.predecessors(targ)]

    def extract_genes(self):
        """
        Returns all genes located in the matchtree

        :return: List of gene names
        """

        genes = []

        # iterate through the graph
        for node_id in list(nx.dfs_postorder_nodes(self.g, source=1)):
            node = self.g.node[node_id]
            if node['type'] == 'genomic':
                if 'hugo_symbol' in node['value']:

                    gene = node['value']['hugo_symbol']

                    if 'wildtype' in node['value'] and node['value']['wildtype'] is True:
                        continue

                    variant = None
                    for k in ['protein_change', 'wildcard_protein_change']:
                        if k in node['value']:
                            variant = node['value'][k].replace('p.', '')

                    if variant and variant.startswith('!'):
                        continue
                    if 'variant_category' in node['value'] and node['value']['variant_category'].startswith('!'):
                        continue

                    if node['value']['hugo_symbol'] not in genes:
                        genes.append(gene)

        return genes

    def extract_cancer_types(self):
        """
        Returns all cancer types located in the match tree

        :param g: DiGraph match tree
        :return: List of cancer types
        """

        diagnoses = []
        cancer_types_expanded = []
        primary_cancer_types = []
        excluded_cancer_types = []
        onco_tree = oncotreenx.build_oncotree(file_path=TUMOR_TREE)
        liquid_children_txt, solid_children_txt = expand_liquid_oncotree(onco_tree)

        # iterate through the graph
        for node_id in list(nx.dfs_postorder_nodes(self.g, source=1)):
            node = self.g.node[node_id]
            if node['type'] == 'clinical':
                if 'oncotree_primary_diagnosis' in node['value']:

                    diagnosis = node['value']['oncotree_primary_diagnosis']

                    n = oncotreenx.lookup_text(onco_tree, diagnosis.replace('!', ''))
                    children = list(nx.dfs_tree(onco_tree, n))

                    if diagnosis == '_SOLID_':
                        children_txt = solid_children_txt
                        primary_parent = 'All Solid Tumors'
                        parents_txt = ['All Solid Tumors']
                    elif diagnosis == '_LIQUID_':
                        children_txt = liquid_children_txt
                        primary_parent = 'All Liquid Tumors'
                        parents_txt = ['All Liquid Tumors']
                    else:
                        children_txt = [onco_tree.node[nn]['text'] for nn in children]

                        if n is not None:
                            parents, parents_txt, primary_parent = get_parents(onco_tree, n)
                        else:
                            parents_txt = []
                            primary_parent = ''

                    diagnoses.append(diagnosis)
                    if diagnosis.startswith('!'):
                        excluded_cancer_types.append(diagnosis.replace('!', ''))
                        excluded_cancer_types.extend(children_txt)
                    else:
                        primary_tumors = get_primary_tumors()
                        cancer_types_expanded.append(parse_diagnosis(diagnosis))
                        cancer_types_expanded.extend(children_txt)
                        cancer_types_expanded.extend([i for i in parents_txt if i.split()[0] not in primary_tumors])
                        primary_cancer_types.append(primary_parent)

        return {
            'diagnoses': list(set(i for i in diagnoses if i.strip() != 'root')),
            'cancer_types_expanded': list(set(i for i in cancer_types_expanded if i.strip() != 'root')),
            'primary_cancer_types': list(set(i for i in primary_cancer_types if i.strip() != 'root')),
            'excluded_cancer_types': list(set(i for i in excluded_cancer_types if i.strip() != 'root'))
        }

def labelWithSubnodes( T, root, lostNodes ):
    """
    For each node in the tree T, we add two vertex properties:
    1) leaves -- A set containing all of the leaves rooted at this subtree
    2) subnodes -- A set containing all of the nodes (internal & leaves) in this subtree
    3) enets -- A set containing network identifiers for all extant networks which exist as some leaf in this subtree
    """
    lost = 'LOST'
    
    def enet(nodes):
        r = set([])
        for n in nodes:
            if n not in lostNodes:
            #   if n.find("LOST") != -1:
            #    r.add(n[:2])
            #else:
                r.add(n[-2:])
            else:
                r.add(lost)
        return r

    for n in nx.dfs_postorder_nodes(T, root) :
        successors = T.successors(n)
        if len(successors) == 0 :
            T.node[n]['subnodes'] =  set([n])
            T.node[n]['leaves'] = T.node[n]['leaves'].union( set([n]) )
            T.node[n]['enets'] = enet([n])
        else :
            subnodes = [ set([n]) ] + [ set([s]) for s in successors ] + [ T.node[s]['subnodes'] for s in successors ]
            for sn in subnodes:
                T.node[n]['subnodes'] = T.node[n]['subnodes'].union( sn )

            leaves = [ T.node[s]['leaves'] for s in successors ]
            T.node[n]['leaves'] = T.node[n]['leaves'].union( *leaves )
            T.node[n]['enets'] = enet( T.node[n]['leaves'] )

def induceTreeOnLeaves(nxtree, leaves):
    leaves = set(leaves)
    dg = nxtree.nxDg
    nodesToKeep = []
    for node in dg.nodes():
        succ = set([nxtree.getName(i) for i in nx.dfs_postorder_nodes(dg, node) if nxtree.hasName(i)])
        if len(succ.intersection(leaves)) != 0:
            nodesToKeep.append(node)
    return NXTree(dg.subgraph(nodesToKeep))

def reduce_node_expr( n, network):
    """reduce_node_expr Reduce the expression on network node. Replace local

    :param n: The node of network currently being processed.
    :param network: Whole network.
    """

    global keys_with_expressions_ 
    global globals_

    attr = network.node[n]
    # Create the expression graph.
    expG = nx.DiGraph( )
    for k, v in attr.items():
        expG.add_node(k, expr = v )
        
    for k, v in attr.items():
        st = build_ast( v )
        if st is None:
            continue
        if reduce_expr(v)[1]:
            expG.node[k]['reduced'] =  reduce_expr(v)[0] 
        for d in get_identifiers( st ):
            expG.add_edge( k, d )

    # Once the dependencies graph is build, we need to reduce it.
    for x in nx.dfs_postorder_nodes( expG ):
        # If its expr is not available locally, look-up in global graph. If we
        # don't find it in global also, then  it must be another node.
        if 'expr' not in expG.node[x]:
            if x in globals_: 
                # Copy its value from globals.
                expG.node[x]['expr'] = globals_[x]
            elif x in network.nodes():
                # x is another node in network. Its expression is itself.
                expG.node[x]['expr'] = x
            else: pass

        # By now we might have an expression on this node. If not, then we just
        # continue. 
        if 'expr' in expG.node[x]:
            expr = expG.node[x]['expr']
            for xx in expG.successors(x):
                if 'expr' in expG.node[xx]:
                    expr = expr.replace( xx, expG.node[xx]['expr'] )
                else: pass
                expG.node[x]['expr'] = reduce_expr( expr )[0]

            # Now only if this key is in keys_with_expressions_ list, then only
            # reduce it. Put the reduced expression into node attribute.
            if x in keys_with_expressions_:
                newExpr = reduce_expr( expr )[0]
                attr[x] = newExpr
                logger_.debug( '@node %s, reduced expr = %s' % (x, newExpr) )
        else:
            logger_.debug( "No expression found for node %s, %s" % (x,
                expG.node[x]))

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 get_node_to_subtree_thickness(T, root):
    thickness = {}
    for node in nx.dfs_postorder_nodes(T, root):
        successors = T.successors(node)
        if not successors:
            thickness[node] = 1
        else:
            w = sorted((thickness[n] for n in successors), reverse=True)
            thickness[node] = max(w + i for i, w in enumerate(w))
    return thickness

    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 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 hdag(N):
    for G in N:
        lst = list(nx.dfs_postorder_nodes(G))[::-1]
        mk = True
        for v in lst[:-1]:
            if not nx.has_path(G, v, lst[lst.index(v) + 1]):  # much faster
                print -1
                mk = False
                break
        if mk:
            print 1, " ".join(map(str, lst))

def main():
    g = networkx.DiGraph()
    
    with Timer('Tree Generation'):
        root = generateTree(g, 4, 127)
        
    print 'Number of nodes: ', nodeNumber
    
    with Timer('Tree Traversal'):
        nNodes = sum(1 for n in networkx.dfs_postorder_nodes(g, root))
    
    print 'Number of nodes traversed: ', nNodes

    def max_repeated(self, k):
        '''Return the node of maximum prefix length with #leaves >= k under it.'''
        g = self._g
        num_leaves = [0] * g.number_of_nodes()
        for node in nx.dfs_postorder_nodes(g): num_leaves[node] = 1 if g.out_degree(node) == 0 else sum(num_leaves[child] for child in g.successors_iter(node))
        
        prefix_len = np.zeros((g.number_of_nodes(),), dtype=int)
        for node in nx.dfs_preorder_nodes(g):
            node_prefix_len = prefix_len[node]
            for child, e_attr in g[node].iteritems(): prefix_len[child] = node_prefix_len + e_attr['weight'][1]

        try: return max(it.ifilter(lambda x: x[0][1] >= k, ((v, k) for k, v in enumerate(zip(prefix_len, num_leaves)))))[1]
        except ValueError: return None

def detailed_connection_graph(start_with=None, end_with=None):
    g = nx.MultiDiGraph()

    clients = Connections.read_clients()

    for emitter_name, destination_values in clients.items():
        for emitter_input, receivers in destination_values.items():
            for receiver_name, receiver_input in receivers:
                label = '{}:{}'.format(emitter_input, receiver_input)
                g.add_edge(emitter_name, receiver_name, label=label)

    ret = g

    if start_with is not None:
        ret = g.subgraph(
            nx.dfs_postorder_nodes(ret, start_with)
        )
    if end_with is not None:
        ret = g.subgraph(
            nx.dfs_postorder_nodes(ret.reverse(), end_with)
        )

    return ret

def flatten_global_expressions( network ):
    global global_expr_g_ 
    g = global_expr_g_
    for x in nx.dfs_postorder_nodes( g ):
        logger_.debug("Trying to reduce expression on node %s" % x)
        if 'expr' not in g.node[x]:
            logger_.debug("Node %s does not have any expr" % x)
            logger_.debug("Not doing anything.")
        else:
            expr = flatten_expression_on_node(x, g )
            # update the value global variables.
            if x in network.graph['graph']:
                network.graph['graph'][x] = expr
    return True

 def buildSceneGraph(self, atNode):
     """
     Evaluate the DAG in a postorder fashion to create a list of the data
     packets in the scene graph sorted by execution order.
     """
     dagPathList = list()
     nodeEvalOrder = networkx.dfs_postorder_nodes(self.network, atNode)
     for dagNode in nodeEvalOrder:
         # Retrieve specialized output types
         specializationDict = dict()
         #for output in dagNode.outputs():
         #    specializationDict[output.name] = self.nodeOutputType(dagNode, output)
         dagPathList.extend(dagNode.scene_graph_handle(specializationDict))
     return dagPathList

def dendrogram_to_ultrametric(dendrogram):
    """Returns the ultrametric corresponding to the dendrogram.

    Args:
        dendrogram (networkx.DiGraph): The dendrogram to be converted. Each
        node should have a 'distance' attribute, which denotes the threshold
        at which the children are merged.
        
    Returns:
        (ndarray): The ultrametric as a condensed distance matrix.
    """
    t = dendrogram.copy()

    leaf_nodes = [x for x in t if t.out_degree(x) == 0]

    n = sum(1 for _ in leaf_nodes)
    ultrametric = _np.zeros((n,n))

    for u in leaf_nodes:
        t.node[u]['leafy_ancestors'] = set([u])

    for u in list(_nx.dfs_postorder_nodes(t)):
        if t.out_degree(u) == 0:
            continue

        leafy_ancestors = []
        for child in t.successors(u):
            leafy_ancestors.append(t.node[child]['leafy_ancestors'])
            t.remove_node(child)

        d = t.node[u]['distance']

        for i in range(len(leafy_ancestors)):
            for j in range(len(leafy_ancestors)):
                if i == j:
                    continue
                
                left_set = leafy_ancestors[i]
                right_set = leafy_ancestors[j]

                for x,y in _itertools.product(left_set, right_set):
                    ultrametric[x][y] = ultrametric[y][x] = d

        ancestors = set()
        for x in leafy_ancestors:
            ancestors |= x

        t.node[u]['leafy_ancestors'] = ancestors

    return _distance.squareform(ultrametric)

def get_dag(dag):
    sorted_dag = dag.copy()

    # The children of a node are traversed in a random order. Therefore,
    # copy the graph, sort the children and then traverse it
    for adj in sorted_dag.adj:
        sorted_dag.adj[adj] = OrderedDict(
            sorted(sorted_dag.adj[adj].items(), key=lambda item: item[0]))

    nodes = nx.dfs_postorder_nodes(sorted_dag,
                                   source='__HPOlib_configuration_space_root__')
    nodes = [node for node in nodes if node !=
             '__HPOlib_configuration_space_root__']
    return nodes