Useful if fiddling with this code.
# cross check sorted_names = list(self.iter_topo_order()) for index in range(len(sorted_names)): rev = sorted_names[index] for left_index in range(index): if rev in self.original_graph[sorted_names[left_index]]: print "revision in parent list of earlier revision" import pdb;pdb.set_trace()
Yield the nodes of the graph in a topological order. After finishing iteration the sorter is empty and you cannot continue iteration.
: """Yield the nodes of the graph in a topological order. After finishing iteration the sorter is empty and you cannot continue iteration. """ while self._graph: # now pick a random node in the source graph, and transfer it to the # top of the depth first search stack. node_name, parents = self._graph.popitem() self._push_node(node_name, parents) while self._node_name_stack: # loop until this call completes. parents_to_visit = self._pending_parents_stack[-1] # if all parents are done, the revision is done if not parents_to_visit: # append the revision to the topo sorted list # all the nodes parents have been added to the output, now # we can add it to the output. yield self._pop_node() else: while self._pending_parents_stack[-1]: # recurse depth first into a single parent next_node_name = self._pending_parents_stack[-1].pop() if next_node_name in self._completed_node_names: # this parent was completed by a child on the # call stack. skip it. continue if next_node_name not in self._visitable: continue # otherwise transfer it from the source graph into the # top of the current depth first search stack. try: parents = self._graph.pop(next_node_name) except KeyError: # if the next node is not in the source graph it has # already been popped from it and placed into the # current search stack (but not completed or we would # have hit the continue 4 lines up. # this indicates a cycle. raise GraphCycleError(self._node_name_stack) self._push_node(next_node_name, parents) # and do not continue processing parents until this 'call' # has recursed. break