def test_topological_sort_on_very_deep_graph(self):
     gr = pygraph.classes.graph.graph()
     gr.add_nodes(list(range(0,20001)))
     for i in range(0,20000):
         gr.add_edge((i,i+1))
     recursionlimit = getrecursionlimit()
     topological_sorting(gr)
     assert getrecursionlimit() == recursionlimit

	def _invalidate_caches(self):
		'invalidate the downstream caches of updated nodes'
		
		if len(self.updated) == 0:
			return
			
		# Sort the nodes in worklist and remove duplicates
		sg = topological_sorting(self.digraph) # sorted graph
		
		worklist = []
		# insert nodes into worklist in sorted order
		for node in sg:
			if node in self.updated:
				worklist.append(node)
		self.updated.clear()
		
		# iterate through worklist
		while worklist:
			node = worklist.pop() # one item at a time
			downstream = breadth_first_search(self.digraph, root=node)[1] # get all downstream labels
			for n in downstream:
				if n in worklist:
					# remove labels that will already be done
					worklist.remove(n)
				# remove cache entries
				self.cache[n] = None

 def testDigraph(self):
     
     def has_parent(node, list):
         for each in list:
             if gr.has_edge(each, node):
                 return True
         return (ts == [])
         
     gr = pygraph.digraph()
     gr.add_nodes([0,1,2,3,4,5,6,7,8])
     gr.add_edge(0,1)
     gr.add_edge(0,2)
     gr.add_edge(1,3)
     gr.add_edge(1,4)
     gr.add_edge(2,5)
     gr.add_edge(2,6)
     gr.add_edge(3,7)
     gr.add_edge(8,0)
     gr.add_edge(7,5)
     gr.add_edge(3,0)
     gr.add_edge(4,3)
     gr.add_edge(2,7)
     gr.add_edge(6,0)
     ts = topological_sorting(gr)
     while (ts):
         x = ts.pop()
         assert has_parent(x, ts)

def sort_nodes_topologically(graph, nodeLs):
    """
    Get a topological sort of a subset of the nodes of a graph
    
    @type  graph: graph_wrapper.GraphWrapper
    @param graph: a graph in which the nodes reside

    @type  nodeLs: list [node]
    @param nodeLs: a list of nodes from which to generate sorting. nodes must not be mutually accessive!
    
    @rtype:  list [node]
    @return: topological sort of the nodes
    """
    # uid_dic = dict([(node.uid,node) for node in nodeLs])
    # helperNodes = uid_dic.keys()
    helperGraph = graph.__class__(originalSentence="")  # TODO: efficiency - this is done this way to avoid circular dependency
    helperGraph.add_nodes(nodeLs)
    acc = accessibility(graph)
    
    for node1 in nodeLs:
            for node2 in acc[node1]:
                if node2 in nodeLs:
                    if node1.uid != node2.uid:  # TODO: efficiency 
                        helperGraph.add_edge((node1, node2))
    
    sorted_nodes = topological_sorting(helperGraph)
    return sorted_nodes

    def resolve_plugin_dependencies(self):
        graph = digraph()
        problems = defaultdict(list)

        def check_plugin_dependencies(plugin_id):
            result = True

            def add_problem(problem_type, plugin_id, dependency):
                problems[plugin_id].append(problem_type(plugin_id, dependency))
                result = False

            for dependency in self.plugin_dependencies(plugin_id):
                if dependency.id not in self.manifests:
                    add_problem(MissingDependency, plugin_id, dependency)
                elif dependency.version:
                    if manifests[required_id].version not in dependency.version:
                        add_problem(IncorrectVersion, plugin_id, dependency)
                elif dependency.id not in graph:
                    if dependency.id in self.enabled_plugins:
                        add_problem(IndirectDependency, plugin_id, dependency)
                    else:
                        add_problem(DisabledDependency, plugin_id, dependency)

            return result

        def remove_dependents(plugin_id):
            for node in traversal(graph, plugin_id, 'pre'):
                for dependent in graph[node]:
                    edge = node, dependent
                    problems[dependent].append(IndirectDependency(dependent, 
                        graph.get_edge_properties(edge)['dependency']))
                graph.del_node(node)

        graph.add_nodes(self.enabled_plugins)
        for plugin_id in self.enabled_plugins:
            if check_plugin_dependencies(plugin_id):
                for dependency in self.plugin_dependencies(plugin_id):
                    edge = dependency.id, plugin_id
                    graph.add_edge(edge)
                    graph.set_edge_properties(edge, dependency=dependency)
            else:
                remove_dependents(plugin_id)

        transitive_deps = accessibility(graph)
        cycle_nodes = [
            node
            for node in graph
            if any(
                (node in transitive_deps[dependent])
                for dependent in transitive_deps[node]
                if dependent != node)]
        for node in cycle_nodes:
            problems[node].append(CyclicDependency(node))
            graph.del_node(node)

        self.dependency_graph = graph
        self._dependency_problems = problems
        self._load_order = topological_sorting(graph)

 def allOff(self):
     '''Turn all servers off ungracefully
     '''
     nodeList = topological_sorting(self.graph)
     for node in nodeList:
         server = self.graph.node_attributes(node)
         for outlet in server.getOutlets():
             outlet.setState(False)
     return

	def evaluate_dag(self):
		'Force every node to be evaluated'
		# First invalidate all changed caches
		self._invalidate_caches()
		
		# Then call update on every node
		sg = topological_sorting(self.digraph) # sorted graph
		for label in sg:
			self._update_node(label)

 def getSortedNodeList(self):
     '''
     returns a list of the nodes topologically sorted
     
     :return: a list of the nodes topologically sorted
     '''
     nodeList = topological_sorting(self.graph)
     servers=[]
     for node in nodeList:
         servers.append(self.graph.node_attributes(node))
     return servers

def order_seq_only(graph):
    """
    A topological sort is performed on the graph. All actions are
    enclosed into a Sequence ISE structure.
    """
    _prepare(graph)
    nodes = topological_sorting(graph.reverse())
    actions = []
    for node in nodes:
        actions.extend(_create_actions_from(node, graph, create_deps=False))

    return _create_final_xml_from(actions, SEQ)

 def process(self):
     """ Process image processing flow for IPFGraph """
     
     # Invalidate all input ports in __blocks
     ((iport.invalidate() for iport in block.input_ports.values()) 
                          for block in self.__blocks.values())
     
     graph = self._make_flow_graph()
     
     # Apply topological sorting and execute processing blocks in
     # topological order 
     sorted_graph = topological_sorting(graph)
     for node in sorted_graph:
         node().process()

 def topo_up_down(graph):
     """
     Yield the nodes of the graph, starting with the leaf-most
     (latest topological) node, running up to the root-most
     (earliest topological) node, and pushing back down to the leaves,
     excepting the leaf-most node.
     
     Undefined behavior if the graph is not a DAG.
     
     graph: A->B->C
     yields: (C, B, A, B)
     """
     tsort = topological_sorting(graph)
     for node in reversed(tsort):
         yield node
     for node in tsort[1 : -1]:
         yield node

    def topo_sort_work(self):
        my_work = self.work

        work_dict = {}
        for w in my_work:
            work_dict[w.work_id] = w

        graph = digraph()
        graph.add_nodes(my_work)

        for w in my_work:
            for p in w.prereqs:
                if not work_dict.has_key(p):
                    continue
                if work_dict[p]:
                    graph.add_edge((work_dict[p], w))
        self.work = topological_sorting(graph)
        return

    def test_topological_sorting_on_tree(self):
        gr = testlib.new_graph()
        st, pre, post = depth_first_search(gr)
        tree = pygraph.classes.digraph.digraph()

        
        for each in st:
            if st[each]:
                if (each not in tree.nodes()):
                    tree.add_node(each)
                if (st[each] not in tree.nodes()):
                    tree.add_node(st[each])
                tree.add_edge((st[each], each))
        
        ts = topological_sorting(tree)
        for each in ts:
            if (st[each]):
                assert ts.index(each) > ts.index(st[each])

def find_connected_resources(resource, dependency_graph=None):
    """
    Collects all resources connected to the given resource and returns a
    dictionary mapping member resource classes to new collections containing
    the members found.
    """
    # Build a resource_graph.
    resource_graph = \
                build_resource_graph(resource,
                                     dependency_graph=dependency_graph)
    entity_map = OrderedDict()
    for mb in topological_sorting(resource_graph):
        mb_cls = get_member_class(mb)
        ents = entity_map.get(mb_cls)
        if ents is None:
            ents = []
            entity_map[mb_cls] = ents
        ents.append(mb.get_entity())
    return entity_map

 def test_topological_sorting_on_digraph(self):
     
     def is_ordered(node, list):
         # Has parent on list
         for each in list:
             if gr.has_edge((each, node)):
                 return True
         # Has no possible ancestors on list
         st, pre, post = depth_first_search(gr, node)
         for each in list:
             if (each in st):
                 return False
         return True
         
     gr = testlib.new_digraph()
     ts = topological_sorting(gr)
     
     while (ts):
         x = ts.pop()
         assert is_ordered(x, ts)

 def testTree(self):
     gr = pygraph.digraph()
     gr.add_nodes([0,1,2,3,4,5,6,7,8])
     gr.add_edge(0,1)
     gr.add_edge(0,2)
     gr.add_edge(1,3)
     gr.add_edge(1,4)
     gr.add_edge(2,5)
     gr.add_edge(2,6)
     gr.add_edge(3,7)
     gr.add_edge(8,0)
     ts = topological_sorting(gr)
     assert ts.index(8) < ts.index(0)
     assert ts.index(1) > ts.index(0)
     assert ts.index(2) > ts.index(0)
     assert ts.index(3) > ts.index(1)
     assert ts.index(4) > ts.index(1)
     assert ts.index(5) > ts.index(2)
     assert ts.index(6) > ts.index(2)
     assert ts.index(7) > ts.index(3)

def find_connected_resources(resource, dependency_graph=None):
    """
    Collects all resources connected to the given resource and returns a 
    dictionary mapping member resource classes to new collections containing
    the members found.
    """
    # Build a resource_graph.
    resource_graph = \
                build_resource_graph(resource,
                                     dependency_graph=dependency_graph)
    # Build an ordered dictionary of collections.
    collections = OrderedDict()
    for mb in topological_sorting(resource_graph):
        mb_cls = get_member_class(mb)
        coll = collections.get(mb_cls)
        if coll is None:
            # Create new collection.
            coll = create_staging_collection(mb)
            collections[mb_cls] = coll
        coll.add(mb)
    return collections

def transitive_edges(graph):
    """
    Return a list of transitive edges.
    
    Example of transitivity within graphs: A -> B, B -> C, A ->  C
    in this case the transitive edge is: A -> C
    
    @attention: This function is only meaningful for directed acyclic graphs.
    
    @type graph: digraph
    @param graph: Digraph
    
    @rtype: List
    @return: List containing tuples with transitive edges (or an empty array if the digraph
        contains a cycle) 
    """
    #if the LoopGraph contains a cycle we return an empty array
    if not len(find_cycle(graph)) == 0:
        return []
    
    tranz_edges = [] # create an empty array that will contain all the tuples
    
    #run trough all the nodes in the LoopGraph
    for start in topological_sorting(graph):
        #find all the successors on the path for the current node
        successors = [] 
        for a in traversal(graph,start,'pre'):
            successors.append(a)
        del successors[0] #we need all the nodes in it's path except the start node itself
        
        for next in successors:
            #look for an intersection between all the neighbors of the 
            #given node and all the neighbors from the given successor
            intersect_array = _intersection(graph.neighbors(next), graph.neighbors(start) )
            for a in intersect_array:
                if graph.has_edge((start, a)):
                    ##check for the detected edge and append it to the returned array   
                    tranz_edges.append( (start,a) )      
    return tranz_edges # return the final array

    def get_levels(self):
        '''arrange the nodes in layers according to degree
        level 0 will have no outgoing edges, last level will have no incoming edges'''
        # Topological order: any strict order which satisfies the partial order
        # as established by the outgoing edges
        graph = self._graph
        ordered = topological_sorting(graph)
        ordered.reverse()
        # print 'ordered %s'%ordered
        result = []
        for elem in ordered:
            deps = graph.neighbors(elem)
            maximo = -1
            for i, level in enumerate(result):
                for d in deps:
                    if d in level and i > maximo:
                        maximo = i

            if maximo + 1 >= len(result):
                result.append(set())
            result[maximo + 1].add(elem)

        return result

def calculate_dependencies(configurers):
    """Given a dictionary of name -> DependencyConfigurer objects, returns a
    list with the leaf nodes of the implied dependencies first.
    """
    
    # We do this via graph theory rather than hard-coding a particular startup
    # order.
    config_graph = digraph()
    for configurer in configurers.values():
        config_graph.add_node(configurer)
    for configurer_name, configurer in configurers.items():
        # Add outbound dependencies for every node.
        for name in configurer.depends_on_names:
            _log.debug("%s depends on %s", configurer_name, name)
            config_graph.add_edge(configurer, configurers[name])
        # Add inbound dependencies for every node.
        for name in configurer.depended_on_names:
            _log.debug("%s depends on %s", name, configurer_name)
            config_graph.add_edge(configurers[name], configurer)
    
    # Reverse here because in topological sorting, nodes with no inbound are first
    # and nodes with no outbound edges are last. We actually want to do things the
    # other way around.
    return topological_sorting(config_graph.reverse())