Qiskit / retworkx / 741

97%

push

travis-ci-com

Workaround isomorphism failure with node removals (#115)

The dag_isomorphism module was forked from upstream petgraph to handle
the PyDiGraph type and also to enable handling exceptions in the python
check functions gracefully. However, when this was done it neglected
that here were limitations with that module which causes failures in
certain scenarios after node removals. This was because the upstream
petgraph implementation was built on the Graph type instead of the
StableGraph type. The only difference between these types is that
StableGraph does not reuse indexes on removals but Graph does. This
can cause there to be holes in the list of node ids. This breaks
assumptions in multiple places of the VF2 implementation causing a
panic if isomorphism checks are run on a PyDiGraph that has nodes
removed. This commit worksaround this limitation by checking if we've
removed nodes from the PyDiGraph object and if we have it iterates over
the graph and clones it into a copy with a condensed set of node ids.

This fix is less than ideal in that it results in a copy of the graph
which will potentially have performance implications, especially for
larger graphs. But after attempting to fix the VF2 implementation that
seems to be a more involved project than I originally hoped. This will
at least workaround the bug until a better more robust VF2
implementation can be written (and likely should be contributed back
upstream to petgraph).

Fixes #27

33 of 33 new or added lines in 1 file covered. (100.0%)

1593 of 1742 relevant lines covered (91.45%)

5608.35 hits per line