This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients dam1784, eric.smith, python-dev, rhettinger, tim.peters
Date 2022-01-20.21:57:14
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1642715834.77.0.799191692735.issue46071@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2022-01-20 21:57:14tim.peterssetrecipients: + tim.peters, rhettinger, eric.smith, python-dev, dam1784
2022-01-20 21:57:14tim.peterssetmessageid: <1642715834.77.0.799191692735.issue46071@roundup.psfhosted.org>
2022-01-20 21:57:14tim.peterslinkissue46071 messages
2022-01-20 21:57:14tim.peterscreate