Fix GraphFlow cycle detection to properly clean up recursion state #7026
+49
−3
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
The
has_cycles_with_exit()method in GraphFlow had a bug where the DFS algorithm would returnTrueimmediately upon finding a cycle with valid exit conditions, without properly cleaning up the recursion state (rec_stackandpath). This left stale data that could cause incorrect behavior when processing subsequent unvisited nodes in graphs with multiple components.Problem
Consider a graph structure like this:
When the DFS processes the cycle
A → B → C → A, it would find the valid exit condition and returnTrueimmediately. However, this skipped the cleanup code (rec_stack.remove(node_name)andpath.pop()), leaving nodes A, B, and C in the recursion stack. When processing the disconnected component E later, this stale state could cause incorrect behavior.Solution
Changed the DFS algorithm to use a local
cyclevariable to accumulate results instead of returning immediately:Before (buggy):
After (fixed):
Testing
Added
test_cycle_detection_cleanup_bug()to the test suite to prevent regression of this issue. All existing cycle detection tests continue to pass, ensuring no regressions were introduced.Fixes #6985.
💬 Share your feedback on Copilot coding agent for the chance to win a $200 gift card! Click here to start the survey.