Skip to content

tsort: fails to print all nodes to stdout when a cycle is found #7074

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
Closed
jfinkels opened this issue Jan 4, 2025 · 1 comment · Fixed by #7093
Closed

tsort: fails to print all nodes to stdout when a cycle is found #7074

jfinkels opened this issue Jan 4, 2025 · 1 comment · Fixed by #7093
Labels
U - tsort

Comments

@jfinkels
Copy link
Collaborator

jfinkels commented Jan 4, 2025 •
edited
Loading

Environment: Ubuntu 20.04, uutils main branch (git commit 20b5365), GNU coreutils v8.30

Steps to reproduce: run topological sort on a graph that has a cycle, like this:

# the graph looks like: a --> b <==> c --> d
printf "a b\nb c\nc b\nc d\n" | tsort

What happens now: uutils tsort prints the cycle to stderr, but does not print the "best effort" ordering of the nodes to stdout:

tsort: -: input contains a loop:
tsort: b
tsort: c
b
c

(The first three lines are on stderr, the next two lines are on stdout.)

What I expected to happen: GNU tsort prints the cycle to stderr when it is discovered during graph traversal, but then continues the traversal and prints all the nodes to stdout:

a
tsort: -: input contains a loop:
tsort: b
tsort: c
b
c
d

Notes: this is causing a failure in the GNU test file tests/misc/tsort.pl.
@jfinkels
Copy link
Collaborator Author

jfinkels commented Jan 7, 2025

It prints multiple loops as well:

# The graph looks like this:
# 
#       a
#       |
#       V
# c <=> b <=> d
#
$ printf "a b b c c b b d d b" | tsort
a
tsort: -: input contains a loop:
tsort: b
tsort: c
tsort: -: input contains a loop:
tsort: b
tsort: d
b
d
c

I'm not sure how it decides which edge to delete to break the loops.

jfinkels added a commit to jfinkels/coreutils that referenced this issue Jan 8, 2025
@jfinkels
tsort: print nodes and cycles as they are visited
daf846d 
Update `tsort` so that

* nodes are printed as they are visited,
* cycles are printed as they are discovered,
* finding a cycle doesn't terminate the traversal,
* multiple cycles can be found and displayed.

Fixes uutils#7074
@jfinkels jfinkels mentioned this issue Jan 8, 2025
Merged
jfinkels added a commit to jfinkels/coreutils that referenced this issue Jan 8, 2025
@jfinkels
tsort: print nodes and cycles as they are visited
a666c58 
Update `tsort` so that

* nodes are printed as they are visited,
* cycles are printed as they are discovered,
* finding a cycle doesn't terminate the traversal,
* multiple cycles can be found and displayed.

Fixes uutils#7074
jfinkels added a commit to jfinkels/coreutils that referenced this issue Jan 8, 2025
@jfinkels
tsort: print nodes and cycles as they are visited
af99952 
Update `tsort` so that

* nodes are printed as they are visited,
* cycles are printed as they are discovered,
* finding a cycle doesn't terminate the traversal,
* multiple cycles can be found and displayed.

Fixes uutils#7074
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
U - tsort
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

tsort: print nodes and cycles as they are visited jfinkels/coreutils
1 participant
@jfinkels