Qiskit / qiskit / 17971248229

88%

Build Type

push

github

Committed by web-flow

Commit Message

Unbias directionality in VF2 priority queue (#14859)

The previous implementation of the priority queue effective biased the
VF2 search heavily in favour of nodes that had outgoing edges from the
mapping.  The implementation of the VF2++ ordering heuristic was written
to match this.  The likely reason was that it made it easier to
completely compile out the cost for undirected searches, and to isolate
the "additional" handling for directionality.

This new implementation now treats outgoing and incoming edges
simultaneously, and chooses the next needle from the set of unmapped
neighbours in any direction to the partial mapping.  This comes at a
small unnecessary memory cost in the case of undirected graphs, but it
feels unlikely that it fill have any significant effect on performance
in those cases.  The VF2++ ordering heuristic is updated to treat
outgoing and incoming edges equally; for now, it sums the two sides,
though it's possible that there's a better metric of "difficulty to
match" than the sum of the two degrees.

Run Details

160 of 172 new or added lines in 1 file covered. (93.02%)

20 existing lines in 5 files now uncovered.

92782 of 105075 relevant lines covered (88.3%)

1178812.33 hits per line