Author tim.peters
Recipients belopolsky, christian.heimes, eric.smith, gdr@garethrees.org, lukasz.langa, martin.panter, orsenthil, pablogsal, remi.lapeyre, rhettinger, terry.reedy, tim.peters, tshepang
Date 2020-01-15.03:51:31
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1579060291.51.0.0679034278944.issue17005@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2020-01-15 03:51:31tim.peterssetrecipients: + tim.peters, rhettinger, terry.reedy, belopolsky, orsenthil, eric.smith, christian.heimes, lukasz.langa, tshepang, gdr@garethrees.org, martin.panter, pablogsal, remi.lapeyre
2020-01-15 03:51:31tim.peterssetmessageid: <1579060291.51.0.0679034278944.issue17005@roundup.psfhosted.org>
2020-01-15 03:51:31tim.peterslinkissue17005 messages
2020-01-15 03:51:31tim.peterscreate