Qiskit / qiskit / 17755812814

88%

Build Type

push

github

Committed by web-flow

Commit Message

Make VF2 fully generic over index types and semantics (#14858)

* Make VF2 fully generic over index types and semantics

This reworks several major parts of the generics structure of the VF2
implementation and is a substantial change to the interface.  In
particular:

* The trait requirements on graphs that can be used with VF2 are wrapped
  into internal alias metatraits (with blanket implementations) to avoid
  needing to repeat the same bounds everywhere.  This matters more
  because of other changes, which require us to repeat the bounds in
  more places now.  The `for<'a>` bound on graph references (implying
  the underlying object must be `'static`) remains: we can either
  require borrowed objects (in which case we could avoid the `'static`
  but would struggle with the node reordering) or require owned objects
  (which we do).  If/when `petgraph` supplies GAT-based traits on
  references for `IntoEdgeReferences` etc, we could relax that bound,
  which in turn would allow input graphs that already implement
  `NodeCompactIndexable` to avoid being rewritten in default ordering.

* The `reorder` method was moved out of the `NodeSorter` trait, leaving
  only the `sort` method.  This lets the output graph type be controlled
  separately; sorting does not inherently affect impact the resulting
  graph structure that can be built with it, which lets us default the
  rewriting to using `Graph` even when given a `StableGraph`, letting us
  avoid `Option` unwrapping on `NodeIndex` lookups.

* The score/matching semantics impl on a 2-tuple is separated out into
  two separate implementations of `Semantics`, with scoring consistency
  now managed via a generic `NoSemantics`, and the `Vf2` struct itself
  ensuring scoring-consistency during its construction, via trait bounds
  on the generics.  There are now two wrapper structs, `Scorer` and
  `Matcher`, that disambiguate `Fn(&NeedleWeight, &HaystackWeight) ->
  Result<S, E>` inputs:

  - where `S: Vf2Scor... (continued)

Run Details

483 of 624 new or added lines in 3 files covered. (77.4%)

14 existing lines in 4 files now uncovered.

92729 of 105030 relevant lines covered (88.29%)

854529.01 hits per line