Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Merged
merged 21 commits into from May 16, 2024
Merged

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

merged 21 commits into from May 16, 2024

Conversation

IvanIsCoding
Copy link
Collaborator

@IvanIsCoding IvanIsCoding commented May 1, 2024 •
edited

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.

@IvanIsCoding IvanIsCoding marked this pull request as draft May 1, 2024 01:03
@coveralls
Copy link

coveralls commented May 1, 2024 •
edited

Pull Request Test Coverage Report for Build 9103568887

Details

  • 25 of 25 (100.0%) changed or added relevant lines in 1 file are covered.
  • 6 unchanged lines in 1 file lost coverage.
  • Overall coverage decreased (-0.01%) to 96.475%
Files with Coverage Reduction New Missed Lines %
src/shortest_path/all_pairs_bellman_ford.rs 6 95.53%
Totals Coverage Status
Change from base Build 9103534121: -0.01%
Covered Lines: 16748
Relevant Lines: 17360
💛 - Coveralls

@IvanIsCoding IvanIsCoding marked this pull request as ready for review May 1, 2024 03:47
@IvanIsCoding IvanIsCoding changed the title [WIP] Always return cycle in digraph_find_cycle if no node is specified and a cycle exists Always return a cycle in digraph_find_cycle if no node is specified and a cycle exists May 1, 2024
@IvanIsCoding IvanIsCoding added this to the 0.15.0 milestone May 1, 2024
mtreinish
mtreinish reviewed May 14, 2024
View reviewed changes
Copy link
Member

@mtreinish mtreinish left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

rustworkx-core/src/connectivity/find_cycle.rs Outdated Show resolved Hide resolved
releasenotes/notes/fix-digraph-find-cycle-141e302ff4a8fcd4.yaml Show resolved Hide resolved
rustworkx-core/src/connectivity/find_cycle.rs Outdated Show resolved Hide resolved
rustworkx-core/src/connectivity/find_cycle.rs Outdated Show resolved Hide resolved
@IvanIsCoding
Copy link
Collaborator Author

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

mtreinish
mtreinish approved these changes May 15, 2024
View reviewed changes
Copy link
Member

@mtreinish mtreinish left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM now, thanks for the quick update.

@mtreinish mtreinish added the automerge Queue a approved PR for merging label May 15, 2024
@IvanIsCoding IvanIsCoding merged commit 8e81911 into Qiskit:main May 16, 2024
28 of 31 checks passed
@IvanIsCoding IvanIsCoding deleted the find-arbitrary-cycle branch May 16, 2024 00:41
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@mtreinish mtreinish mtreinish approved these changes

Assignees
No one assigned
Labels
automerge Queue a approved PR for merging
Projects
None yet
Milestone
0.15.0
Development

Successfully merging this pull request may close these issues.

rx.digraph_find_cycle() does not find the cycle in a graph
3 participants
@IvanIsCoding @coveralls @mtreinish