Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
1.03k stars 145 forks source link

Add `initial` argument to topological sorters #1128

Closed jakelishman closed 5 months ago

jakelishman commented 6 months ago

This adds a way for the topological sorters to recieve a set of initial nodes to begin the search from. This can allow the topological iteration to begin from a mid-point of the order, or to simply provide Rustworkx with the already-known set of initial nodes, skipping the iteration over each node to find the full set. Especially in TopologicalSorter, where one may be using the on-line search to find only the first handful of nodes in the topological order in an inner loop of a mutating graph, this can be a complexity improvement.

The initial nodes are required to have no topological ordering between themselves, and it is an error if they do. There are other possible conventions to choose here, but this one is the easiest to state / understand and the fastest to execute; most other sensible conventions would require some amount of initial walking of the DAG to determine the partial topological order between the nodes before beginning, which would get in the way of the complexity improvements for inner-loop topological sorts.

For similar complexity reasons, the behaviour surrounding zero-in-degree nodes that are not in initial is chosen such that only nodes dominated by the initial set will be returned. In other words, if a node has zero in degree, but is not in the initial set, it won't be returned as part of the order. This is easily understandable and documentable ("the returned topological order is of all nodes dominated by initial"), and removes the need for the all-node iteration to locate any potential zero-in-degree nodes.

Close #1106 - the motivation in there is that we end up building and using many TopologicalSorters in a loop while adding nodes to one particular graph, and being able to pass the initial nodes lets us avoid a quadratic complexity in doing so.

jakelishman commented 5 months ago

I've pushed up the docs fixes and an update to make it PyO3-0.21 compatible. What sorts of randomised tests were you thinking of? I was having a little bit of a hard time imagining a randomised test that I could a) write (making a randomised DAG that actually samples the space of potential node orders well seemed like a non-trivial problem) and b) verify cleanly in a test seems not super easy to me.

If you've got any ideas, I'm happy to expand the tests.

coveralls commented 5 months ago

Pull Request Test Coverage Report for Build 8571151224

Details


Changes Missing Coverage Covered Lines Changed/Added Lines %
src/dag_algo/mod.rs 25 29 86.21%
src/toposort.rs 31 36 86.11%
<!-- Total: 56 65 86.15% -->
Files with Coverage Reduction New Missed Lines %
src/toposort.rs 1 94.39%
src/shortest_path/all_pairs_bellman_ford.rs 6 95.53%
<!-- Total: 7 -->
Totals Coverage Status
Change from base Build 8570880241: -0.07%
Covered Lines: 17196
Relevant Lines: 17816

💛 - Coveralls