rustworkx
rustworkx copied to clipboard
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
.
Using a small vec for the edge data (as opposed to Vec
) kept the performance of the case where in- and out-edges are close to a bijection sufficiently similar in my casual benchmarking to assuming a bijection and not allowing broadacsting at all. Using a Vec
(and consequently always having pointer indirection to retrieve the nodes) came with a performance penalty (although I stupidly didn't actually write down the numbers on that).
Pull Request Test Coverage Report for Build 8576435630
Details
- 113 of 115 (98.26%) changed or added relevant lines in 1 file are covered.
- No unchanged relevant lines lost coverage.
- Overall coverage increased (+0.01%) to 96.52%
Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
---|---|---|---|
src/digraph.rs | 113 | 115 | 98.26% |
<!-- | Total: | 113 | 115 |
Totals | |
---|---|
Change from base Build 8571532908: | 0.01% |
Covered Lines: | 17305 |
Relevant Lines: | 17929 |