This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author adriangb
Recipients Jim Fasarakis-Hilliard, Paddy McCarthy, Zahari.Dim, adriangb, belopolsky, christian.heimes, eric.smith, gaborjbernat, gdr@garethrees.org, lukasz.langa, maresb, martin.panter, miss-islington, orsenthil, pablogsal, remi.lapeyre, rhettinger, terry.reedy, tim.peters, tshepang, vstinner, wim.glenn
Date 2021-11-29.19:13:16
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1638213197.28.0.539284844581.issue17005@roundup.psfhosted.org>
In-reply-to
Content
As part of working on a tool that deals with dependencies, I was building my own topological sort. I iterated through various APIs (iterable of tasks, iterable of parallelizable groups of tasks, etc.) until I found the (now stdlib) version which ended up being exactly the API I needed to most efficiently execute dependencies. So, kudos on the design!

I actually ended up re-writing it in Rust, partly because I wanted a good project to learn Rust, partly because I wanted to be able to modify the API a bit. Namely:
1. I needed the ability to re-execute the same DAG multiple times without re-checking for cycles and re-adding all nodes (so basically copying `npredecessors` before executing).
2. I needed the ability to remove nodes from the graph. The real-world application is removing pruning subgraphs corresponding to cached dependencies. Again, I wanted to do this without rebuilding the entire thing (removing nodes can never lead to a cycle, and it is possible to keep track of new leaf nodes as you remove them instead of iterating over the entire graph again to find leaf nodes).

Here's the implementation in case anyone is interested: https://github.com/adriangb/graphlib2

The algorithm is the same, but I had to change the data structures somewhat to cope w/ Rusts' borrowing rules (namely I can't hold a mutable reference to two values in `node2nodeinfo` at the same time, which the current implementation does here https://github.com/python/cpython/blob/32f1491a9770b7f2989507ecf8f13ef35dd95b0b/Lib/graphlib.py#L190, so I split them out into two separate mappings).
History
Date User Action Args
2021-11-29 19:13:17adriangbsetrecipients: + adriangb, tim.peters, rhettinger, terry.reedy, belopolsky, orsenthil, vstinner, eric.smith, christian.heimes, lukasz.langa, tshepang, gdr@garethrees.org, martin.panter, wim.glenn, Zahari.Dim, Paddy McCarthy, Jim Fasarakis-Hilliard, pablogsal, miss-islington, remi.lapeyre, gaborjbernat, maresb
2021-11-29 19:13:17adriangbsetmessageid: <1638213197.28.0.539284844581.issue17005@roundup.psfhosted.org>
2021-11-29 19:13:17adriangblinkissue17005 messages
2021-11-29 19:13:16adriangbcreate