Qiskit / rustworkx / 8141406179

94%

Build Type

push

github

Committed by web-flow

Commit Message

Add steiner tree functionality to rustworkx-core (#1103)

* Implement deduplicate edge

* Move MetricClousureEdge

* Add definition of _metric_clousure_edges

* Add definition of metric_clousure

* Add definition of fast_metric_edges

* Add definition of steiner_tree

* Add mod steiner_tree to lib.rs

* Add necessary crate

* correct type

* change MetricClousureEdge to generic

* Update steiner_tree

* Finish rustworkx-core port

This commit finishes the rustworkx-core port of the steiner tree and
metric closure functions. In particular this was especially tricky
because the petgraph traits make it exceedingly difficult to have a
generic function that takes in a graph for analysis and modifies it as
most of the traits required for visiting/iteration that are used for
analysis are only defined on borrowed graphs, and the limited traits for
modifying graphs are defined on owned graph types. This causes a
conflict where you can't easily express that a generic type G created in
a function from a user input is both mutated using a trait and analyzed
as there is a type mismatch between G and &G. After spending far too
long to fail to find a pattern to express this, I opted to just use a
discrete type for the return and leave the actual graph mutation up to
the rustworkx-core user because we're lacking the ability to cleanly
express what is needed via petgraph.

* Add back checking on valid weights and terminal nodes

---------

Co-authored-by: Ryuhei Yoshida <yoshida0112@chem.s.u-tokyo.ac.jp>

Run Details

396 of 410 new or added lines in 2 files covered. (96.59%)

3 existing lines in 1 file now uncovered.

17095 of 17721 relevant lines covered (96.47%)

1217683.9 hits per line