[issue17005] Add a topological sort algorithm

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

Oh, it's fine!  Kahn's algorithm is what I meant when I wrote the "bog-standard implementation" before.

I don't believe I've ever seen a context in real life where topsort speed made a lick of real difference, so I expect any linear-time (in the sum of the number of nodes and edges) would be fine.  Nevertheless, for recording a node's successors ("children" in your code), I've always used a list rather than a set.  Lists run faster and require less memory than sets, and - unlike sets - in Python inherently preserve insertion order.  Iteration order can become visible (e.g., if B, C, and D depend on A, what's "the" topsort order?  it depends on the order A's children appear when iterating over them - predictable with a list, "it depends" with a set).

Note:  "but we have to guard against redundant edges!" would be a red herring.  Kahn's algorithm couldn't care less, provided that predecessor counts accurately reflect the number of edges (redundant or not) entering a node.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue17005>
_______________________________________