tsort: fix minimal cycle reporting and precise back-edge removal (no refactors) #8786
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
GNU testsuite comparison: |
naoNao89
force-pushed
the
pr1-tsort-minimal-cycle
branch
from
7a4ae04 to
e590069
Compare
|
GNU testsuite comparison: |
CodSpeed Performance ReportMerging #8786 will improve performances by 46.74%Comparing Summary
Benchmarks breakdown
Footnotes |
|
GNU testsuite comparison: |
|
GNU testsuite comparison: |
Contributor
|
@naoNao89 this looks good, but there's an open PR for handling a stack overflow in the cycle code that will impact this PR |
naoNao89
force-pushed
the
pr1-tsort-minimal-cycle
branch
2 times, most recently
from
36249db to
5f0c697
Compare
|
GNU testsuite comparison: |
anastygnome
suggested changes
Nov 3, 2025
Contributor
anastygnome
left a comment
anastygnome
left a comment
There was a problem hiding this comment.
Looks good, just one thing that should be fixed :)
…oval with iterative DFS - Implement iterative DFS to prevent stack overflows (from PR uutils#8737) - Fix minimal cycle reporting to show only actual cycle nodes - Remove redundant back-edge from last cycle node to first - Update test expectations for corrected cycle handling
naoNao89
force-pushed
the
pr1-tsort-minimal-cycle
branch
from
5f0c697 to
4d6fdea
Compare
|
GNU testsuite comparison: |
anastygnome
approved these changes
Nov 3, 2025
|
GNU testsuite comparison: |
asder8215
pushed a commit
to asder8215/coreutils
that referenced
this pull request
Nov 8, 2025
…oval with iterative DFS (uutils#8786) - Implement iterative DFS to prevent stack overflows (from PR uutils#8737) - Fix minimal cycle reporting to show only actual cycle nodes - Remove redundant back-edge from last cycle node to first - Update test expectations for corrected cycle handling
naoNao89
added a commit
to naoNao89/coreutils
that referenced
this pull request
Nov 8, 2025
…oval with iterative DFS (uutils#8786) - Implement iterative DFS to prevent stack overflows (from PR uutils#8737) - Fix minimal cycle reporting to show only actual cycle nodes - Remove redundant back-edge from last cycle node to first - Update test expectations for corrected cycle handling
naoNao89
added a commit
to naoNao89/coreutils
that referenced
this pull request
Nov 9, 2025
…oval with iterative DFS (uutils#8786) - Implement iterative DFS to prevent stack overflows (from PR uutils#8737) - Fix minimal cycle reporting to show only actual cycle nodes - Remove redundant back-edge from last cycle node to first - Update test expectations for corrected cycle handling
romanstingler
pushed a commit
to romanstingler/coreutils
that referenced
this pull request
Dec 14, 2025
…oval with iterative DFS (uutils#8786) - Implement iterative DFS to prevent stack overflows (from PR uutils#8737) - Fix minimal cycle reporting to show only actual cycle nodes - Remove redundant back-edge from last cycle node to first - Update test expectations for corrected cycle handling
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
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.
Fixies #8743
This PR fixes incorrect loop reporting in tsort by reporting only the minimal cycle subpath and removing the precise back-edge that closes the cycle. No performance refactors or unrelated changes are included.