Qiskit / rustworkx / 8576567307 / 1
94%
main: 94%

DEFAULT BRANCH: main
Ran
Files 98
Run time 2s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 96.52% (+0.01%) from 96.509%
8576567307.1

push

github

web-flow 
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>

17305 of 17929 relevant lines covered (96.52%)

1174213.14 hits per line

Source Files on job 8576567307.1