Adrian Garcia Badaracco <adr...@adriangb.com> added the comment:
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). ---------- nosy: +adriangb _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue17005> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
