Message360022
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. |
|
Date |
User |
Action |
Args |
2020-01-15 03:51:31 | tim.peters | set | recipients:
+ 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:31 | tim.peters | set | messageid: <1579060291.51.0.0679034278944.issue17005@roundup.psfhosted.org> |
2020-01-15 03:51:31 | tim.peters | link | issue17005 messages |
2020-01-15 03:51:31 | tim.peters | create | |
|