dag_isomorphism::is_isomorphic_matching checks don't work on PyDAG with removed node #27
Comments
|
Hi @mtreinish! I was wondering what the status of this bug is, since it's referenced here I'm wondering because from my testing, it looks like Aqua's operator flow ( |
|
There haven't been any updates on this since I initially opened the issue. I hadn't treated it as a priority because I thought |
|
Unfortunately I don't know anything about Rust, but it seems like something good to learn at some point. For now though I don't think I'll be able to fix it. Also maybe @Cryoris would be interested in this issue as well. But thanks for the info, this is helpful! |
|
So I've come up with a simple test case in case to reproduce this easily if someone wants to take a crack at it. I took a quick look at it yesterday and it wasn't the 2 line fix I initially thought it would be, but I still don't think it should be too bad to solve. def test_isomorphic_compare_nodes_with_removals(self):
dag_a = retworkx.PyDAG()
dag_b = retworkx.PyDAG()
qr_0_in = dag_a.add_node('qr[0]')
qr_1_in = dag_a.add_node('qr[1]')
cr_0_in = dag_a.add_node('cr[0]')
qr_0_out = dag_a.add_node('qr[0]')
qr_1_out = dag_a.add_node('qr[1]')
cr_0_out = dag_a.add_node('qr[0]')
cu1 = dag_a.add_child(qr_0_in, 'cu1', 'qr[0]')
dag_a.add_edge(qr_1_in, cu1, 'qr[1]')
measure_0 = dag_a.add_child(cr_0_in, 'measure', 'cr[0]')
dag_a.add_edge(cu1, measure_0, 'qr[0]')
measure_1 = dag_a.add_child(cu1, 'measure', 'qr[1]')
dag_a.add_edge(measure_0, measure_1, 'cr[0]')
dag_a.add_edge(measure_1, qr_1_out, 'qr[1]')
dag_a.add_edge(measure_1, cr_0_out, 'cr[0]')
dag_a.add_edge(measure_0, qr_0_out, 'qr[0]')
dag_a.remove_node(cu1)
dag_a.add_edge(qr_0_in, measure_0, 'qr[0]')
dag_a.add_edge(qr_1_in, measure_1, 'qr[1]')
qr_0_in = dag_b.add_node('qr[0]')
qr_1_in = dag_b.add_node('qr[1]')
cr_0_in = dag_b.add_node('cr[0]')
qr_0_out = dag_b.add_node('qr[0]')
qr_1_out = dag_b.add_node('qr[1]')
cr_0_out = dag_b.add_node('qr[0]')
measure_0 = dag_b.add_child(cr_0_in, 'measure', 'cr[0]')
dag_b.add_edge(qr_0_in, measure_0, 'qr[0]')
measure_1 = dag_b.add_child(qr_1_in, 'measure', 'qr[1]')
dag_b.add_edge(measure_1, qr_1_out, 'qr[1]')
dag_b.add_edge(measure_1, cr_0_out, 'cr[0]')
dag_b.add_edge(measure_0, measure_1, 'cr[0]')
dag_b.add_edge(measure_0, qr_0_out, 'qr[0]')
self.assertTrue(
retworkx.is_isomorphic_node_match(
dag_a, dag_b, lambda x, y: x == y))
def test_isomorphic_compare_nodes_with_removals_deepcopy(self):
dag_a = retworkx.PyDAG()
dag_b = retworkx.PyDAG()
qr_0_in = dag_a.add_node('qr[0]')
qr_1_in = dag_a.add_node('qr[1]')
cr_0_in = dag_a.add_node('cr[0]')
qr_0_out = dag_a.add_node('qr[0]')
qr_1_out = dag_a.add_node('qr[1]')
cr_0_out = dag_a.add_node('qr[0]')
cu1 = dag_a.add_child(qr_0_in, 'cu1', 'qr[0]')
dag_a.add_edge(qr_1_in, cu1, 'qr[1]')
measure_0 = dag_a.add_child(cr_0_in, 'measure', 'cr[0]')
dag_a.add_edge(cu1, measure_0, 'qr[0]')
measure_1 = dag_a.add_child(cu1, 'measure', 'qr[1]')
dag_a.add_edge(measure_0, measure_1, 'cr[0]')
dag_a.add_edge(measure_1, qr_1_out, 'qr[1]')
dag_a.add_edge(measure_1, cr_0_out, 'cr[0]')
dag_a.add_edge(measure_0, qr_0_out, 'qr[0]')
dag_a.remove_node(cu1)
dag_a.add_edge(qr_0_in, measure_0, 'qr[0]')
dag_a.add_edge(qr_1_in, measure_1, 'qr[1]')
qr_0_in = dag_b.add_node('qr[0]')
qr_1_in = dag_b.add_node('qr[1]')
cr_0_in = dag_b.add_node('cr[0]')
qr_0_out = dag_b.add_node('qr[0]')
qr_1_out = dag_b.add_node('qr[1]')
cr_0_out = dag_b.add_node('qr[0]')
measure_0 = dag_b.add_child(cr_0_in, 'measure', 'cr[0]')
dag_b.add_edge(qr_0_in, measure_0, 'qr[0]')
measure_1 = dag_b.add_child(qr_1_in, 'measure', 'qr[1]')
dag_b.add_edge(measure_1, qr_1_out, 'qr[1]')
dag_b.add_edge(measure_1, cr_0_out, 'cr[0]')
dag_b.add_edge(measure_0, measure_1, 'cr[0]')
dag_b.add_edge(measure_0, qr_0_out, 'qr[0]')
self.assertTrue(
retworkx.is_isomorphic_node_match(
copy.deepcopy(dag_a), copy.deepcopy(dag_b),
lambda x, y: x == y))Fwiw, deep rust experience shouldn't be required to solve this and I'll gladly help anyone that was interested in diving in on it. It would probably actually be a good intro to rust project (except for that the code in |
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 Qiskit#27
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
The __eq__ method of the dagcircuit class was previously deep copying the retworkx PyDAG objects for both self and other to force a reindexing of the node indices in the graphs to acvoid a bug in retworkx (see Qiskit/rustworkx#27 for more details). In the next retworkx a workaround for that bug was introduced which removes the need for doing the deepcopy calls. This commit does that and removes the deep copies which should improve the performance of run __eq__ o dagcircuit objects.
The __eq__ method of the dagcircuit class was previously deep copying the retworkx PyDAG objects for both self and other to force a reindexing of the node indices in the graphs to acvoid a bug in retworkx (see Qiskit/rustworkx#27 for more details). In the next retworkx a workaround for that bug was introduced which removes the need for doing the deepcopy calls. This commit does that and removes the deep copies which should improve the performance of run __eq__ o dagcircuit objects.
retworkx::dag_isomorphism::is_isomorphic_matching was written by copy and pasting petgraph's isomorphism functions and changing the input type to be PyDAG instead of petgraph's
Graph. However, the code wasn't 100% compatible as originally assumed because of node removals. The function assumes that an isomorphic graph will always have the same number of node indexes, however in the case of petgraph'sStableGraph(which PyDAG uses internally) this is not the case. A stable graph's number of indexes increases on each node add, and if a node is removed the old index is not used again, unlikeGraph. This will cause a panic like:thread '<unnamed>' panicked at 'index out of bounds: the len is 4 but the index is 4'when trying to compare a graph with removals to a graph without any.A temporary workaround for this is to use deepcopy (or pickle and unpickle) the pydags. This will reset the index counters so they'll be the same. This is not a great answer, it's just a workaround until the function is updated.
The text was updated successfully, but these errors were encountered: