Logo Search packages:      
Sourcecode: xdeb version File versions  Download package

def tsort::TopoSorter::iter_topo_order (   self )

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.

Definition at line 118 of file tsort.py.

                             :
        """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


Generated by  Doxygen 1.6.0   Back to index