Skip to content

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

@jfinkels

Description

@jfinkels

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions