rustworkx
rustworkx copied to clipboard
Qiskit
Port VF2 to `rustworkx-core`
Summary
Ports Rustworkx's modified VF2 algorithm to rustworkx-core, supporting generic petgraph types like StableGraph.
Details
This implementation should work for petgraph's StableGraph, Graph, and GraphMap (though IIRC there is a bug in petgraph's implementation of their EdgeCount trait for GraphMap ~which would likely cause issues until it gets fixed~ edit: I believe it only triggers if edges are removed, so it'd likely be fine).
In contrast with the original petgraph::algo::isomorphism API which hides the fact that VF2 is used under the hood for isomorphism, this PR introduces the VF2 internals as a public interface (i.e. rustworkx_core::isomorphism::vf2), exposing traits NodeMatcher and EdgeMatcher and structs Vf2Algorithm and Vf2State, which can be used to further customize how VF2 is executed. We now use this in our Python API's implementation of (Di|)GraphVF2Mapping, for example. (...the only sort of "kludge" regarding the above is that I had to make a few fields on Vf2Algorithm and Vf2State public in order to support Python garbage collection requirements. If you've got a better idea, please leave a comment.)
Changes from the Python impl
- To support generic fail-able node and edge matching, the error type
IsIsomorphicErroris introduced, which encapsulates the error types returned by the user providedNodeMatcherandEdgeMatcher. Vf2Algorithmnow formally implementsIterator, with anItemtype ofResult.
To-do
- [x] Release note.
- [X] Fix edge matcher regression (I'm aware of the issue, working on fix).
- [X] Add more detailed PR description 🙂.
Pull Request Test Coverage Report for Build 9751462927
Warning: This coverage report may be inaccurate.
This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.
- For more information on this, see Tracking coverage changes with pull request builds.
- To avoid this issue with future PRs, see these Recommended CI Configurations.
- For a quick fix, rebase this PR at GitHub. Your next report should be accurate.
Details
- 954 of 1063 (89.75%) changed or added relevant lines in 3 files are covered.
- No unchanged relevant lines lost coverage.
- Overall coverage decreased (-0.4%) to 95.412%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| src/isomorphism/mod.rs | 82 | 100 | 82.0% |
| rustworkx-core/src/isomorphism/vf2.rs | 830 | 868 | 95.62% |
| src/isomorphism/vf2_mapping.rs | 42 | 95 | 44.21% |
| <!-- | Total: | 954 | 1063 |
| Totals | |
|---|---|
| Change from base Build 9718474595: | -0.4% |
| Covered Lines: | 18280 |
| Relevant Lines: | 19159 |
💛 - Coveralls
Pull Request Test Coverage Report for Build 9755097325
Warning: This coverage report may be inaccurate.
This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.
- For more information on this, see Tracking coverage changes with pull request builds.
- To avoid this issue with future PRs, see these Recommended CI Configurations.
- For a quick fix, rebase this PR at GitHub. Your next report should be accurate.
Details
- 954 of 1063 (89.75%) changed or added relevant lines in 3 files are covered.
- No unchanged relevant lines lost coverage.
- Overall coverage decreased (-0.4%) to 95.412%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| src/isomorphism/mod.rs | 82 | 100 | 82.0% |
| rustworkx-core/src/isomorphism/vf2.rs | 830 | 868 | 95.62% |
| src/isomorphism/vf2_mapping.rs | 42 | 95 | 44.21% |
| <!-- | Total: | 954 | 1063 |
| Totals | |
|---|---|
| Change from base Build 9718474595: | -0.4% |
| Covered Lines: | 18280 |
| Relevant Lines: | 19159 |
💛 - Coveralls
Pull Request Test Coverage Report for Build 9765697514
Warning: This coverage report may be inaccurate.
This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.
- For more information on this, see Tracking coverage changes with pull request builds.
- To avoid this issue with future PRs, see these Recommended CI Configurations.
- For a quick fix, rebase this PR at GitHub. Your next report should be accurate.
Details
- 954 of 1063 (89.75%) changed or added relevant lines in 3 files are covered.
- No unchanged relevant lines lost coverage.
- Overall coverage decreased (-0.4%) to 95.412%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| src/isomorphism/mod.rs | 82 | 100 | 82.0% |
| rustworkx-core/src/isomorphism/vf2.rs | 830 | 868 | 95.62% |
| src/isomorphism/vf2_mapping.rs | 42 | 95 | 44.21% |
| <!-- | Total: | 954 | 1063 |
| Totals | |
|---|---|
| Change from base Build 9718474595: | -0.4% |
| Covered Lines: | 18280 |
| Relevant Lines: | 19159 |
💛 - Coveralls
Thanks for the review, @IvanIsCoding!
Regarding the Python GIL acquisition in the PyMatcher implementations of NodeMatcher and EdgeMatcher, I think assuming the GIL is acquired is the best thing we can do.
The main issue with threading the actual GIL into those callbacks is that the callbacks get moved into the (Di|)GraphVF2Mapping pyclass structs, which means they can't have any lifetime parameters (pyclass structs cannot have lifetime parameters in PyO3) and thus can't hold a Python<'py> token. In the original Python-only code, this was worked around by having the next method on VF2Mapping take a Python<'py> token, which was then threaded down to the callbacks when pumping the iterator. But this isn't appropriate in rustworkx-core, of course.
We certainly could use Python::with_gil instead of Python::assume_gil_acquired, but my expectation is that this would introduce a performance regression, since PyO3 would be checking for the GIL for every single comparison, be it a node or an edge.
Given that the matchers are only invoked while we're pumping the iterator from Python, we should be safe to assume the GIL is acquired, as long as we aren't using Rayon (or other multithreading) to perform matching on other threads.
I think unsafe as a last-resource is OK and with Matthew's +1 we can merge it as is.
However, before we do that: can you try using a PyFunction similar to how we use it in here: https://github.com/Qiskit/rustworkx/blob/2734eee56f246da0d1618f0302268d5f66d38bbd/src/lib.rs#L312?
We pass PyFunction's to Dijkstra. Couldn't we do the same here? Then the calls would be fn.call1((a, b)) instead of requiring the py argument
Thanks for the additional review @IvanIsCoding!
We pass PyFunction's to Dijkstra. Couldn't we do the same here? Then the calls would be fn.call1((a, b)) instead of requiring the py argument
I'm not sure I'm finding / understanding exactly what you're describing here. It looks like CostFn is an enum that can be either a default f64 value or a PyObject callable from the user. In the impl for CostFn, the call method appears to require a py token.
I think the only way to really get a Python token into the matchers would be to remove them from the VF2Algorithm struct and pass them in to the call to next every time, i.e. inject the Python token into node_matcher and edge_matcher closures and use a custom next method that takes them as parameters. But, that feels like a bad API design to me, since it allows the user to change the definition of what constitutes a match with every pump of the "iterator" (in quotes because we'd also no longer be able to implement Iterator since we'd need a custom signature for next).
Let me know if I'm misunderstanding the example you mentioned. It'd be neat to get things working without unsafe, but I'm not optimistic it is possible without making serious concessions to the integrity of the Rust API for this. And, I'm not worried about what we're doing here with unsafe because it is tightly controlled and entirely encapsulated from our users.