Qiskit / qiskit
88%
main: 88%

LAST BUILD BRANCH: gh-readonly-queue/main/pr-15122-bfd268c1b109b7023bf0b294f289c96d55000a00
DEFAULT BRANCH: main
Repo Added
Files 872
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

LAST BUILD ON BRANCH gh-readonly-queue/main/pr-14856-7bb681024d1fc1bae370ce75c706138235204491
branch: gh-readonly-queue/main/pr-14856-7bb681024d1fc1bae370ce75c706138235204491
CHANGE BRANCH
x

coverage: 88.33% (-0.06%) from 88.388%
17433410138

push

github

web-flow 
Add on-the-fly score pruning to VF2 (#14856)

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 imposs... (continued)

356 of 572 new or added lines in 3 files covered. (62.24%)

27 existing lines in 6 files now uncovered.

91300 of 103362 relevant lines covered (88.33%)

481897.71 hits per line

Relevant lines Covered
103362 RELEVANT LINES 91300 COVERED LINES
481897.71 HITS PER LINE
Source Files on gh-readonly-queue/main/pr-14856-7bb681024d1fc1bae370ce75c706138235204491

Recent builds

Builds Branch Commit Type Ran Committer Via Coverage
17433410138 gh-readonly-queue/main/pr-14856-7bb681024d1fc1bae370ce75c706138235204491 Add on-the-fly score pruning to VF2 (#14856) 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 capab... push web-flow github
88.33
See All Builds (14220)