Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reimplement VF2 to handle StableGraph node index holes #125

Closed
mtreinish opened this issue Aug 25, 2020 · 1 comment
Closed

Reimplement VF2 to handle StableGraph node index holes #125

mtreinish opened this issue Aug 25, 2020 · 1 comment
Labels
enhancement New feature or request

Comments

@mtreinish
Copy link
Member

What is the expected enhancement?

The VF2 implementation in dag_isomorphism.rs was forked from the upstream petgraph project and modified to handle PyDiGraph. As was previously reported in #27 and worked around in #115 that implementation didn't work with the petgraph StableGraph type used in retworkx on node removals because there could be holes in the list of node ids (so that node_bound() on 2 isomorphic graphs aren't the same) which isn't possible in the petgraph Graph type but is in StableGraph. This was causing a hard failure in the isomorphism functions if a node was removed from a PyDiGraph obejct and was worked around in #115. However, this workaround introduces overhead in the case of node removals because it is cloning and reindexing the graph to not have holes in the index list. The next step here is to reimplement the vf2 algorithm to natively handle holes in the node index so that we don't need this cloning and reindexing step.

It also would probably be good to push an improved vf2 back upstream to petgraph after it is implemented here. We'll still need the local fork in retworkx, but if we fix VF2 support for StableGraph we should make sure to contribute that back to petgraph too.

@mtreinish
Copy link
Member Author

As was discussed in #267 it turns out that to fix this we need to use a different data structure (a map or set instead of a vec) which ends up adding significantly more overhead than the current workaround where we just reindex the graph before using it. Since this the reindexing is internal to retworkx and not user facing I think we'd rather have faster runtime performance than slightly cleaner code. So I'm going to close this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant