tsort: fix minimal cycle reporting and precise back-edge removal (no refactors)#8786
Merged
sylvestre merged 1 commit intouutils:mainfrom Nov 7, 2025
Merged
Conversation
|
GNU testsuite comparison: |
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 |
36249db to
5f0c697
Compare
|
GNU testsuite comparison: |
anastygnome
suggested changes
Nov 3, 2025
Contributor
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
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
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
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.