Open kevinhartman opened 1 week ago
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.
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 | 89.75% | --> |
Totals | |
---|---|
Change from base Build 9718474595: | -0.4% |
Covered Lines: | 18280 |
Relevant Lines: | 19159 |
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.
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 | 89.75% | --> |
Totals | |
---|---|
Change from base Build 9718474595: | -0.4% |
Covered Lines: | 18280 |
Relevant Lines: | 19159 |
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.
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 | 89.75% | --> |
Totals | |
---|---|
Change from base Build 9718474595: | -0.4% |
Covered Lines: | 18280 |
Relevant Lines: | 19159 |
Summary
Ports Rustworkx's modified VF2 algorithm to
rustworkx-core
, supporting genericpetgraph
types likeStableGraph
.Details
This implementation should work for
petgraph
'sStableGraph
,Graph
, andGraphMap
(though IIRC there is a bug inpetgraph
's implementation of theirEdgeCount
trait forGraphMap
~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 traitsNodeMatcher
andEdgeMatcher
and structsVf2Algorithm
andVf2State
, 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 onVf2Algorithm
andVf2State
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
IsIsomorphicError
is introduced, which encapsulates the error types returned by the user providedNodeMatcher
andEdgeMatcher
.Vf2Algorithm
now formally implementsIterator
, with anItem
type ofResult
.To-do