def _choose_spanhead_from_heuristics(self,span_nodes,pos_precedence_list):
        distancestoroot = [len(nx.ancestors(self,x)) for x in span_nodes]
        shortestdistancetoroot = min(distancestoroot)
        distance_counter = Counter(distancestoroot)

        highest_nodes_in_span = []
        # Heuristic Nr 1: If there is one single highest node in the span, it becomes the head
        # N.B. no need for the subspan to be a tree if there is one single highest element
        if distance_counter[shortestdistancetoroot] == 1:
            spanhead = span_nodes[distancestoroot.index(shortestdistancetoroot)]
            return spanhead

        # Heuristic Nr 2: Choose by POS ranking the best head out of the highest nodes
        for x in span_nodes:
            if len(nx.ancestors(self,x)) == shortestdistancetoroot:
                highest_nodes_in_span.append(x)

        best_rank = len(pos_precedence_list) + 1
        candidate_head = - 1
        span_upos  = [self.node[x]["cpostag"]for x in highest_nodes_in_span]
        for upos, idx in zip(span_upos,highest_nodes_in_span):
            if pos_precedence_list.index(upos) < best_rank:
                best_rank = pos_precedence_list.index(upos)
                candidate_head = idx
        return candidate_head

    def _find_necessary_steps(self, outputs, inputs):
        """
        Determines what graph steps need to pe run to get to the requested
        outputs from the provided inputs.  Eliminates steps that come before
        (in topological order) any inputs that have been provided.  Also
        eliminates steps that are not on a path from the provided inputs to
        the requested outputs.

        :param list outputs:
            A list of desired output names.  This can also be ``None``, in which
            case the necessary steps are all graph nodes that are reachable
            from one of the provided inputs.

        :param dict inputs:
            A dictionary mapping names to values for all provided inputs.

        :returns:
            Returns a list of all the steps that need to be run for the
            provided inputs and requested outputs.
        """

        if not outputs:

            # If caller requested all outputs, the necessary nodes are all
            # nodes that are reachable from one of the inputs.  Ignore input
            # names that aren't in the graph.
            necessary_nodes = set()
            for input_name in iter(inputs):
                if self.graph.has_node(input_name):
                    necessary_nodes |= nx.descendants(self.graph, input_name)

        else:

            # If the caller requested a subset of outputs, find any nodes that
            # are made unecessary because we were provided with an input that's
            # deeper into the network graph.  Ignore input names that aren't
            # in the graph.
            unnecessary_nodes = set()
            for input_name in iter(inputs):
                if self.graph.has_node(input_name):
                    unnecessary_nodes |= nx.ancestors(self.graph, input_name)

            # Find the nodes we need to be able to compute the requested
            # outputs.  Raise an exception if a requested output doesn't
            # exist in the graph.
            necessary_nodes = set()
            for output_name in outputs:
                if not self.graph.has_node(output_name):
                    raise ValueError("graphkit graph does not have an output "
                        "node named %s" % output_name)
                necessary_nodes |= nx.ancestors(self.graph, output_name)

            # Get rid of the unnecessary nodes from the set of necessary ones.
            necessary_nodes -= unnecessary_nodes

        # Return an ordered list of the needed steps.
        return [step for step in self.steps if step in necessary_nodes]

	def ancestors(self, nbunch):
		self.validate_input_nodes(nbunch)
		if not self.acceptable_iterable(nbunch):	# single input node
			return nx.ancestors(self, nbunch)
		else:
			if len(nbunch) == 1:	# still a single node
				return nx.ancestors(self, nbunch[0])
			else:	# multiple input nodes
				DG = self.copy()
				t = DG.add_node_unique()
				for node in nbunch:
					DG.add_edge(node, t) # this automatically adds t to DG too
				return nx.ancestors(DG, t) - set(nbunch) # returns a SET

    def backward_reachable(self, state):
        """Return states from which the given state can be reached.

        A wrapper of networkx.ancestors.
        """
        ancestors = nx.ancestors(self, state)
        return ancestors

    def as_dependency_list(self, limit_to=None):
        """returns a list of list of nodes, eg. [[0,1], [2], [4,5,6]]. Each element contains nodes whose
        dependenices are subsumed by the union of all lists before it. In this way, all nodes in list `i`
        can be run simultaneously assuming that all lists before list `i` have been completed"""

        if limit_to is None:
            graph_nodes = set(self.graph.nodes())
        else:
            graph_nodes = set()
            for node in limit_to:
                graph_nodes.add(node)
                if node in self.graph:
                    graph_nodes.update(nx.descendants(self.graph, node))
                else:
                    raise RuntimeError("Couldn't find model '{}' -- does it exist or is it diabled?".format(node))

        depth_nodes = defaultdict(list)

        for node in graph_nodes:
            num_ancestors = len(nx.ancestors(self.graph, node))
            depth_nodes[num_ancestors].append(node)

        dependency_list = []
        for depth in sorted(depth_nodes.keys()):
            dependency_list.append(depth_nodes[depth])

        return dependency_list

 def get_ancestor_groups(self, pipeline_name):
     groups = []
     ancestors = nx.ancestors(self.value_stream.pipeline_graph, pipeline_name)
     for ancestor in ancestors:
         logger.debug('ancestor of %s: %s', pipeline_name, ancestor)
         groups.append(self.pipeline_groups.pipelines[ancestor][0])
     return list(set(groups))

    def __init__(self, go_server, pipeline_name, label = None):
        self.go_server = go_server
        self.pipeline = gocd_parser.pipeline.Pipeline(pipeline_name, go_server)

        if label is None:
            # get the last passing pipeline
            label = self.pipeline.get_last_passing()['label']
        self.label = label

        self.value_stream = value_stream.ValueStream(
                self.go_server, self.pipeline.name, self.label)
        self.ancestors = nx.ancestors(self.value_stream.pipeline_graph,
                self.pipeline.name)

        self.dashboard = gocd_parser.handler.dashboard.Dashboard(go_server)
        self.pipeline_groups = pipeline_groups.PipelineGroups(go_server)
        self.pipeline.set_from_groups_handler(self.pipeline_groups)
        self.pipeline.set_failing_comparison()

        self.set_blockers()

        self.status = 'passing'
        if len(self.blockers) > 0:
            self.status = 'blocked'
        if self.pipeline.is_failing():
            self.status = 'failing'

 def filter_graph(graph):
     from_s = nx.descendants(graph, start_id)
     from_s.add(start_id)
     to_e = nx.ancestors(graph, end_id)
     to_e.add(end_id)
     del_cross = (from_s | to_e) - (from_s & to_e)
     graph.remove_nodes_from(del_cross)

def in_component(G, target):
    r'''creates the in_component by basically reversing out_component.

    Parameters
    ----------
    G : NetworkX Graph
        The network the disease will transmit through.
    target : a target node
        The node whose infection we are interested in.

        In principle target could be an iterable, but in this case we would be finding those possible
        sources whose infection leads to infection of at least one target, not all.

    Returns
    -------
    source_nodes : set
        the set of nodes (including target) from which target is reachable
    '''
    try:
        #testing whether this is an iterable
        iterator = iter(target)
    except TypeError:
        #It's not an iterable.  It "must" be a node.
        if G.has_node(target):
            target_nodes = set([target])
    else:
        #it's an iterable.  
        target_nodes = set(target)
    source_nodes = set([])
    for node in target_nodes:
        source_nodes = source_nodes.union(set(nx.ancestors(G, node)))
    return source_nodes

def subtree(G, node):
    GS = G.copy()
    GS.remove_node(node)
    sd = nx.descendants(G, node)
    sd.add(node)
    s = set(sd)
    S = G.subgraph(s).copy()

    for n in sd:
        if n == node:
            continue
        ns = nx.ancestors(GS, n)
        if not ns.issubset(sd):
            S.remove_node(n)
            s.discard(n)

    pn = set(G.predecessors_iter(node))

    gs = set(
        itertools.chain.from_iterable(
            nx.shortest_path(G, "REPO", n) for n in pn
        ))

    GS = G.subgraph(gs.union(s)).copy()

    for n in pn.difference(s):
        GS.node[n]["fontcolor"] = "#FF0000"

    for n in s:
        GS.node[n]["fontcolor"] = "#006600"

    GS.remove_node("REPO")

    return S, GS

    def subgraph_needed_for(self, start_at, end_at):
        """Find the subgraph of all dependencies to run these tasks. Returns a
        new graph.
        """
        assert start_at or end_at, "one of {start_at,end_at} must be a task id"
        start, end = map(self.task_dict.get, [start_at, end_at])
        if None in [start, end]:
            graph = self.get_networkx_graph()
            if start:
                task_subset = nx.descendants(graph, start)
                task_subset.add(start)
            elif end:
                task_subset = nx.ancestors(graph, end)
                task_subset.add(end)
        elif start == end:
            task_subset = set([start])
        else:
            graph = self.get_networkx_graph()
            task_subset = set()
            for path in nx.all_simple_paths(graph, start, end):
                task_subset.update(path)

        # make sure the tasks are added to the subgraph in the same
        # order as the original configuration file
        tasks_kwargs_list = [task.yaml_data for task in self.task_list
                             if task in task_subset]
        subgraph = TaskGraph(self.config_path, tasks_kwargs_list)
        return subgraph

def print_impacted_modules(single_node=None, json_out=None):
    """
     For each module, print a list of modules that depend on the module, i.e.
     modules that would be impacted by a change in this module. The function
     shows all levels of dependency, not just the immediately impacted
     modules.  If the json_out argument is not None, then the output will be
     recorded there rather than printed on stdout.
    :return:
    """
    if json_out is None:
        print('\n===Impacted Modules===')
    else:
        json_out['impacted_modules'] = {}
    for node_name in G.nodes_iter():
        if single_node and (node_name!=single_node):
            continue
        ancestors = nx.ancestors(G, node_name)
        if len(ancestors) > 0:
            if json_out is None:
                print(augment_format_string(node_name, '\n%s:') % node_name)
            else:
                json_out['impacted_modules'][node_name] = []
            for a in ancestors:
                if json_out is None:
                    print(augment_format_string(a, '    %s') % a)
                else:
                    json_out['impacted_modules'][node_name].append(a)

    def OnClick(self, node_id):
        self.color_nodes()
        self._current_node_id = node_id
        node_ea = self[node_id]

        self._remove_target_handler.unregister()
        self._disable_source_handler.unregister()
        self._enable_source_handler.unregister()

        if node_ea in self._targets:
            self._remove_target_handler.register()
            self._attach_to_popup(self._remove_target_handler.get_name())

            for ea in nx.ancestors(self._lca_graph, node_ea):
                if ea not in self._targets and ea not in self._sources:
                    self._set_node_bg_color(self._node_ids[ea], COLOR_PATH)

        if node_ea in self._sources:
            if node_ea in self._disabled_sources:
                self._enable_source_handler.register()
                self._attach_to_popup(self._enable_source_handler.get_name())
            else:
                self._disable_source_handler.register()
                self._attach_to_popup(self._disable_source_handler.get_name())

                for ea in nx.descendants(self._lca_graph, node_ea):
                    if ea not in self._targets and ea not in self._sources:
                        self._set_node_bg_color(self._node_ids[ea], COLOR_PATH)

        return False

    def ensure_dependencies(request):
        r"""
        CommandLine:
            python -m dtool.base --exec-BaseRequest.ensure_dependencies

        Example:
            >>> # ENABLE_DOCTEST
            >>> from dtool.base import *  # NOQA
            >>> from dtool.example_depcache import testdata_depc
            >>> depc = testdata_depc()
            >>> request = depc.new_request('vsmany', [1, 2], [2, 3, 4])
            >>> request.ensure_dependencies()
        """
        import networkx as nx
        depc = request.depc
        if False:
            dependencies = nx.ancestors(depc.graph, request.tablename)
            subgraph = depc.graph.subgraph(set.union(dependencies, {request.tablename}))
            dependency_order = nx.topological_sort(subgraph)
            root = dependency_order[0]
            [nx.algorithms.dijkstra_path(subgraph, root, start)[:-1] +
             nx.algorithms.dijkstra_path(subgraph, start, request.tablename)
             for start in dependency_order]
        graph = depc.graph
        root = list(nx.topological_sort(graph))[0]
        edges = graph.edges()
        #parent_to_children = ut.edges_to_adjacency_list(edges)
        child_to_parents = ut.edges_to_adjacency_list([t[::-1] for t in edges])
        to_root = {request.tablename:
                   ut.paths_to_root(request.tablename, root, child_to_parents)}
        from_root = ut.reverse_path(to_root, root, child_to_parents)
        dependency_levels_ = ut.get_levels(from_root)
        dependency_levels = ut.longest_levels(dependency_levels_)

        true_order = ut.flatten(dependency_levels)[1:-1]
        #print('[req] Ensuring %s request dependencies: %r' % (request, true_order,))
        ut.colorprint(
            '[req] Ensuring request %s dependencies: %r' % (request, true_order,), 'yellow')
        for tablename in true_order:
            table = depc[tablename]
            if table.ismulti:
                pass
            else:
                # HACK FOR IBEIS
                all_aids = ut.flat_unique(request.qaids, request.daids)
                depc.get_rowids(tablename, all_aids)
                pass
            pass

        #zip(depc.get_implicit_edges())
        #zip(depc.get_implicit_edges())

        #raise NotImplementedError('todo')
        #depc = request.depc
        #parent_rowids = request.parent_rowids
        #config = request.config
        #rowid_dict = depc.get_all_descendant_rowids(
        #    request.tablename, root_rowids, config=config)
        pass

 def descends(self, e, root):
     """Does the envo term `e` descend from the node `root`?
     Returns True or False."""
     # Auto conversion #
     if isinstance(e,    int):    e = "ENVO:%08d" % e
     if isinstance(root, int): root = "ENVO:%08d" % root
     # Return #
     return e in networkx.ancestors(self.networkx, root)

def getcentral(g1):
    # get different centrality
    return pd.DataFrame({
        u'anc': {x: len(nx.ancestors(g1, x)) for x in g1.nodes()},
        u'des': {x: len(nx.descendants(g1, x)) for x in g1.nodes()},
        u'indeg': g1.in_degree(),
        u'outdeg': g1.out_degree()
        })

def filter_recipe_dag(dag, names):
    name_set = set(names)
    nodes = set()
    for recipe in dag:
        if recipe.reldir in name_set and recipe not in nodes:
            nodes.add(recipe)
            nodes |= nx.ancestors(dag, recipe)
    return nx.subgraph(dag, nodes)

    def get_upstream_paths(self, *requested_paths):
        subgraph_members = set(requested_paths)
        for path in requested_paths:
            subgraph_members.update(nx.ancestors(self._graph, path))

        subgraph_paths = self._paths.intersection(subgraph_members)
        full_subgraph = nx.subgraph(self._graph, subgraph_members)
        path_subgraph = nx.projected_graph(full_subgraph, subgraph_paths)
        return(nx.topological_sort(path_subgraph))

 def _transfer_graph_as_worker(self, graph):
     worker = GWorker(debug=self._debug, priority=1)
     for node in graph.nodes():
         worker.add_node(node, {'ptr': graph.node[node]['ptr']})
         if not nx.ancestors(graph, node):
             worker.set_start_to_run(node)
     for edge in graph.edges():
         u, v = edge
         worker.add_edge(u, v, weight=1)
     return worker

 def architecture_subtree_names(self, node_name):
     """
     returns an unordered set of descendant names of the current node in the
     architectural tree
     """
     # NOTE: this is actually the descendants, despite the name, because
     # of the way we set up the tree
     descendant_names = nx.ancestors(self.architectural_tree, node_name)
     subtree_names = descendant_names | {node_name}
     return subtree_names