tsort: GNU test cases fail even though our output is still valid

[jfinkels]

For the test cases named tree-1 and tree-2 in the GNU test file tests/misc/tsort.pl, our implementation of tsort produces an output different from GNU tsort but still valid. (In general, there may be more than one valid topological ordering for a given directed acyclic graph.) The test cases will fail due to this difference.

One option is to use our build-gnu.sh script to modify the GNU test cases as follows:

diff --git a/tests/misc/tsort.pl b/tests/misc/tsort.pl
index f1ca28a08..1fb256139 100755
--- a/tests/misc/tsort.pl
+++ b/tests/misc/tsort.pl
@@ -41,9 +41,9 @@ my @Tests =
     {OUT => "a\nb\nc\nd\ne\nf\ng\n"}],
 
    ['tree-1', {IN => "a b b c c d d e e f f g\nc x x y y z\n"},
-    {OUT => "a\nb\nc\nx\nd\ny\ne\nz\nf\ng\n"}],
+    {OUT => "a\nb\nc\nd\nx\ne\ny\nf\nz\ng\n"}],
    ['tree-2', {IN => "a b b c c d d e e f f g\nc x x y y z\nf r r s s t\n"},
-    {OUT => "a\nb\nc\nx\nd\ny\ne\nz\nf\nr\ng\ns\nt\n"}],
+    {OUT => "a\nb\nc\nd\nx\ne\ny\nf\nz\ng\nr\ns\nt\n"}],
 
    # Before coreutils-5.0.1, given an odd number of input tokens,
    # tsort would accept that and treat the input as if an additional

Maybe there are other solutions as well.