You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
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.
What is the expected enhancement?
The VF2 implementation in
dag_isomorphism.rs
was forked from the upstream petgraph project and modified to handlePyDiGraph
. As was previously reported in #27 and worked around in #115 that implementation didn't work with the petgraphStableGraph
type used in retworkx on node removals because there could be holes in the list of node ids (so thatnode_bound()
on 2 isomorphic graphs aren't the same) which isn't possible in the petgraphGraph
type but is inStableGraph
. This was causing a hard failure in the isomorphism functions if a node was removed from aPyDiGraph
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.
The text was updated successfully, but these errors were encountered: