Tim Peters <t...@python.org> added the comment:
For the purpose of topological sorting, yes, it's by far most natural to give,
for each node, the collection of that node's predecessors. And that's the way
topsort applications typically collect their data to begin with, like, "here,
for each recipe, is a list of ingredients needed first" or "before we can begin
this job, here are the other jobs that need to complete first". or, as in
makefiles, "here's a list of the targets that need to be built before we can
start building the current target".
I definitely don't want to change the wording, because it's bog standard as is.
For example, Wikipedia's "topological sorting" entry is typical:
"""
In computer science, a topological sort or topological ordering of a directed
graph is a linear ordering of its vertices such that for every directed edge uv
from vertex u to vertex v, u comes before v in the ordering.
"""
It's what topsort _means_. We did not intend to implement a "reverse topsort"
algorithm, and I see no attraction to doing so, neither in pretending we did so.
If the way the user collects their data stores only successor links (which, as
above, seems odd in applications that actually use topsorts), then they need
something like this instead:
ts = TopologicalSorter()
for u, successors in my_forward_graph.items():
for v in successors:
ts.add(v, u)
But that's something I never needed.
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue46071>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
