Qiskit / rustworkx / 12365801109

96%

main: 94%

push

github

Migrate Johnson's algorithm to rustworkx-core (#1318)

* Migrate Johnson's algorithm to rustworkx-core

This commit adds Johnson's algorithm for computing simple cycles to
rustworkx-core. This implementation returns an iterator-like struct
which requires a reference to the graph for each step of the iterator.
This mirrors the structure of the Bfs and similar structs in petgraph.
While an implementor of Iterator could be used for this, this
complicates using it from Python because we can't have a shared
reference in a pyclass struct. This also has the advantage of enabling
mutable references while iterating over the cycles.

To facilitate this 2 traits are added `EdgeFindable` and `EdgeRemovable`
which add traits for `remove_edge()` and `find_edge()` to petgraph graph
types. The `EdgeRemovable` trait isn't actually used currently, it was
in an earlier local draft of the PR which attempted to remove self
cycles from a clone before changing direction of the interface. Since
the implementation was done and relatively simple, and the potential
general usefulness this was left in. `EdgeFindable` is actively used
by this new function however.

* Simplify python side logic

* Set name of pyclass to SimpleCycleIter for backwards compat

* Fix rustdoc warnings

---------

Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>
Co-authored-by: Ivan Carvalho <ivancarv@student.ubc.ca>

288 of 312 new or added lines in 4 files covered. (92.31%)

18360 of 19160 relevant lines covered (95.82%)

1137670.45 hits per line