Qiskit / qiskit / 17133963441 / 1
88%
main: 88%

LAST BUILD BRANCH: fix-hls-qubit-tracking
DEFAULT BRANCH: main
Ran
Files 845
Run time 31s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 88.271% (-0.07%) from 88.342%
17133963441.1

push

github

jakelishman 
Add on-the-fly score pruning to VF2

This is a complete rewrite of the VF2 codebase, also adding the concept
of "score" to the semantic matchers for nodes and edges.  Nothing in the
current codebase is updated to use the new scoring capabilities in this
patch, though the modifications to how the node-matching functions need
to be supplied are respected.

The on-the-fly scoring is to support the use-case of our `VF2Layout` and
`VF2PostLayout` passes, which are a minimising reduction over all
possible subgraph isomorphisms.  The current logic generates each
isomorphism, keys that to a score, then finds the minimal mapping based
on that key.  The benefits of on-the-fly scoring are:

1. The VF2 search tree can be eagerly pruned as soon as the score of the
   partial mapping exceeds the current known minimal value.  In terms of
   the code structure here, we claim a candidate mapping pair is
   "unfeasible" if it increases the score past the minimum.  This allows
   us to terminate entire branches of the algorithm, potentially with
   many levels of depth still unmapped.  This can be a combinatoric
   improvement on the complete iterator.

2. A given pair of layouts generated "close" together (in terms of the
   loop over isomorphisms) will usually share most of their node
   mappings.  This means that they also share almost all of their score
   calculation.  By tracking the score on-the-fly, and backtracking the
   score to a previous state as we pop pairs out of the mapping, we
   avoid recalculating much of the score.  If there are many available
   subgraph isomorphisms, differing only by small numbers of qubits at
   one end, this can improve the asymptotic complexity of the scoring
   significantly.

The scoring, as implemented here, does come at a cost: if enabled, but
there is _no_ isomorphism, we'll waste time by scoring partial layouts
all the way through, only for the regular structural checks to show that
everything was already impossible.  Th... (continued)

88508 of 100268 relevant lines covered (88.27%)

504754.92 hits per line

Source Files on job 17133963441.1