Qiskit / rustworkx / 8571532908

94%

Build Type

push

github

Committed by web-flow

Commit Message

Add `initial` argument to topological sorters (#1128)

* Add `initial` argument to topological sorters

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.

* Improve comment wording

Co-authored-by: Edwin Navarro <enavarro@comcast.net>

* Fix typo in parameter documentation

* Update for PyO3 0.21

---------

Co-authored-by: Edwin Navarro <enavarro@comcast.net>

Run Details

56 of 65 new or added lines in 2 files covered. (86.15%)

7 existing lines in 2 files now uncovered.

17194 of 17816 relevant lines covered (96.51%)

1182909.72 hits per line