Qiskit / rustworkx / 8576567307

push

github

Add node-removal methods linear in node degree (#1083)

* Add node-removal methods linear in node degree

The existing method, `PyDiGraph.remove_node_retain_edges` is quadratic
in node degree, because the ``condition`` function takes in pairs of
edges.  This poses a problem for extreme-degree nodes (for example
massive barriers in Qiskit).

This commit adds two methods based on making edge-retention decisions by
hashable keys, making it linear in the degree of the node (at least;
the MIMO broadcasting can make it quadratic again if all edges have the
same key, but that's fundamental to the output, rather than the
algorithm).

The ideal situation (for performance) is that the edges can be
disambiguated by Python object identity, which doesn't require
Python-space calls to retrieve or hash, so can be in pure Rust.  This is
`remove_node_retain_edges_by_id`.

The more general situation is that the user wants to supply a Python key
function, which naturally returns a Python object that we need to use
Python hashing and equality semantics for.  This means using Python
collections to do the tracking, which impacts the performance (very
casual benchmarking using the implicit identity function as the key
shows it's about 2x slower than using the identity).  This method is
`remove_node_retain_edges_by_key`.

* Format

* Update conversion actions to be by `Bound` reference

This is partly a PyO3 0.21 upgrade, partly fixing a dodgy `extract` in
favour of `downcast`.

* Update out-of-date comment

---------

Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>

113 of 115 new or added lines in 1 file covered. (98.26%)

17305 of 17929 relevant lines covered (96.52%)

1174213.14 hits per line