Closed mtreinish closed 6 months ago
Changes Missing Coverage | Covered Lines | Changed/Added Lines | % | ||
---|---|---|---|---|---|
src/steiner_tree.rs | 56 | 60 | 93.33% | ||
rustworkx-core/src/steiner_tree.rs | 340 | 350 | 97.14% | ||
<!-- | Total: | 396 | 410 | 96.59% | --> |
Files with Coverage Reduction | New Missed Lines | % | ||
---|---|---|---|---|
src/shortest_path/all_pairs_dijkstra.rs | 3 | 96.35% | ||
<!-- | Total: | 3 | --> |
Totals | |
---|---|
Change from base Build 8127117962: | -0.05% |
Covered Lines: | 17089 |
Relevant Lines: | 17721 |
This PR is the continuation of #916 that finishes the port of the
steiner_tree()
andmetric_closure()
functions to rustworkx-core to enable their reuse in rust. 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 typeG
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 and failing 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. Since this was a significant rewrite of #916 and only the core algorithm (which was ported from the original rustworkx code anyway) remained the same I opted to open up a separate PR built on top of #916's branch to avoid confusion.Closes #916 Co-authored-by: Ryuhei Yoshida yoshida0112@chem.s.u-tokyo.ac.jp