Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
981 stars 141 forks source link

Always return a cycle in `digraph_find_cycle` if no node is specified and a cycle exists #1181

Closed IvanIsCoding closed 2 months ago

IvanIsCoding commented 2 months ago

Closes #1171

Instead of picking an arbitrary node if it is not provided, we find a smarter pick that is in a strongly-connected component with more than one node. It also handles the case of self-loops in case there is a SCC with a single node.

coveralls commented 2 months ago

Pull Request Test Coverage Report for Build 9103568887

Details


Files with Coverage Reduction New Missed Lines %
src/shortest_path/all_pairs_bellman_ford.rs 6 95.53%
<!-- Total: 6 -->
Totals Coverage Status
Change from base Build 9103534121: -0.01%
Covered Lines: 16748
Relevant Lines: 17360

💛 - Coveralls
IvanIsCoding commented 2 months ago

Overall I like the idea here it makes sense to me to use a connected component function to get a node in a cycle and go from there. I just have some concerns about the backwards compatibility implications. They're likely unavoidable to use the scc functions, but we should document it as an upgrade change then.

I removed most of the traits but petgraph::visit::Visitable is a requirement for kosaraju_scc and by https://docs.rs/petgraph/latest/petgraph/visit/trait.Visitable.html most graphs implement that