[issue46071] Graphlib documentation (edge direction)

Tim Peters report at bugs.python.org
Thu Jan 20 16:57:14 EST 2022


Tim Peters <tim at 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 <report at bugs.python.org>
<https://bugs.python.org/issue46071>
_______________________________________


More information about the Python-bugs-list mailing list