• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

Qiskit / qiskit / 17133963441
88%
main: 88%

Build:
Build:
LAST BUILD BRANCH: fix-hls-qubit-tracking
DEFAULT BRANCH: main
Ran 21 Aug 2025 05:55PM UTC
Jobs 1
Files 845
Run time 2min
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

21 Aug 2025 05:12PM UTC coverage: 88.271% (-0.07%) from 88.342%
17133963441

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)

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

36 existing lines in 5 files now uncovered.

88508 of 100268 relevant lines covered (88.27%)

504754.92 hits per line

New Missed Lines in Diff

Lines Coverage ∆ File
1
85.26
0.01% crates/circuit/src/dag_circuit.rs
215
69.63
-7.63% crates/circuit/src/vf2.rs

Uncovered Existing Lines

Lines Coverage ∆ File
1
85.26
0.01% crates/circuit/src/dag_circuit.rs
4
74.58
-0.16% crates/circuit/src/parameter/symbol_expr.rs
7
91.75
-0.77% crates/qasm2/src/lex.rs
12
69.63
-7.63% crates/circuit/src/vf2.rs
12
96.62
-0.94% crates/qasm2/src/parse.rs
Jobs
ID Job ID Ran Files Coverage
1 17133963441.1 21 Aug 2025 05:55PM UTC 845
88.27
GitHub Action Run
Source Files on build 17133963441
  • Tree
  • List 845
  • Changed 7
  • Source Changed 3
  • Coverage Changed 7
Coverage ∆ File Lines Relevant Covered Missed Hits/Line
  • Back to Repo
  • Github Actions Build #17133963441
  • a1efba86 on github
  • Prev Build on gh-readonly-queue/main/pr-14931-25c8a9312b9f92d54c05c27aa32ecd30cae15301 (#17130803216)
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc