KEMBAR78
Fix GraphFlow cycle detection to properly clean up recursion state by Copilot · Pull Request #7026 · microsoft/autogen · GitHub
Skip to content

Conversation

Copy link
Contributor

Copilot AI commented Sep 16, 2025

The has_cycles_with_exit() method in GraphFlow had a bug where the DFS algorithm would return True immediately upon finding a cycle with valid exit conditions, without properly cleaning up the recursion state (rec_stack and path). 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:

graph = DiGraph(
    nodes={
        "A": DiGraphNode(name="A", edges=[
            DiGraphEdge(target="B"),
            DiGraphEdge(target="D")  # This branch could be affected
        ]),
        "B": DiGraphNode(name="B", edges=[DiGraphEdge(target="C")]),
        "C": DiGraphNode(name="C", edges=[DiGraphEdge(target="A", condition="loop")]),  # Valid cycle
        "D": DiGraphNode(name="D", edges=[]),
        "E": DiGraphNode(name="E", edges=[])  # Disconnected component
    }
)

When the DFS processes the cycle A → B → C → A, it would find the valid exit condition and return True immediately. However, this skipped the cleanup code (rec_stack.remove(node_name) and path.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 cycle variable to accumulate results instead of returning immediately:

Before (buggy):

def dfs(node_name: str) -> bool:
    # ... setup code ...
    for edge in self.nodes[node_name].edges:
        if target not in visited:
            if dfs(target):
                return True  # Early return without cleanup
        elif target in rec_stack:
            # ... cycle validation ...
            return True  # Early return without cleanup
    
    rec_stack.remove(node_name)  # Only reached if no cycles found
    path.pop()
    return False

After (fixed):

def dfs(node_name: str) -> bool:
    # ... setup code ...
    cycle = False  # Track cycle detection locally
    for edge in self.nodes[node_name].edges:
        if target not in visited:
            if dfs(target):
                cycle = True  # Continue processing instead of early return
        elif target in rec_stack:
            # ... cycle validation ...
            cycle = True  # Continue processing instead of early return
    
    rec_stack.remove(node_name)  # Always executed
    path.pop()
    return cycle  # Return accumulated result

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.

- Modified has_cycles_with_exit() DFS algorithm to use local cycle variable instead of early returns
- Ensures rec_stack and path are always cleaned up before returning from each DFS call
- Added comprehensive test case to prevent regression of the cleanup bug

The original bug: when a cycle with valid exit condition was found, the function returned True immediately without cleaning up rec_stack and path, leaving stale state that could affect processing of subsequent unvisited nodes.

Co-authored-by: ekzhu <320302+ekzhu@users.noreply.github.com>
Copilot AI changed the title [WIP] GraphFlow: Checking a cycle is Wrong Fix GraphFlow cycle detection to properly clean up recursion state Sep 16, 2025
Copilot AI requested a review from ekzhu September 16, 2025 08:27
Copilot finished work on behalf of ekzhu September 16, 2025 08:27
@ekzhu ekzhu marked this pull request as ready for review September 16, 2025 08:39
@codecov
Copy link

codecov bot commented Sep 16, 2025

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 80.93%. Comparing base (79d5d6a) to head (c4dc252).
⚠️ Report is 1 commits behind head on main.

Additional details and impacted files
@@           Coverage Diff           @@
##             main    #7026   +/-   ##
=======================================
  Coverage   80.93%   80.93%           
=======================================
  Files         237      237           
  Lines       18240    18241    +1     
=======================================
+ Hits        14762    14763    +1     
  Misses       3478     3478           
Flag Coverage Δ
unittests 80.93% <100.00%> (+<0.01%) ⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
  • 📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

@ekzhu ekzhu merged commit 14809f5 into main Sep 16, 2025
34 checks passed
@ekzhu ekzhu deleted the copilot/fix-6985 branch September 16, 2025 09:12
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

GraphFlow: Checking a cycle is Wrong

2 participants