Tim Peters <[email protected]> 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 <[email protected]>
<https://bugs.python.org/issue17005>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
