tsort: -: input contains an odd number of tokens

Question

coreutils manual says

tsort reads its input as pairs of strings, separated by blanks, indicating a partial ordering. The output is a total ordering that corresponds to the given partial ordering. For example

tsort <<EOF
a b c
d
e f
b c d e
EOF

will produce the output

a
b
c
d
e
f

What does "tsort reads its input as pairs of strings" mean, and what requirements does that put on the input? In the example, does the first line a b c mean nothing itself, but a and b are paired, and so are c and d?

Why does this not work?

$ tsort <<EOF
> a b c
> b c d e
> EOF
tsort: -: input contains an odd number of tokens

Answer 1

tsort does a topological sorting of a directed graph. It gets the graph as pairs of nodes. These constitute a partial ordering of the graph and tsort gives you a total ordering as the result (there may be more than one total ordering of the graph though, see the documentation for the -f and -h options on BSD systems (not available on GNU systems AFAIK)).

Example of a real graph (these are the OpenBSD packages required to build the shells/bash package on an OpenBSD system):

$ make -C /usr/ports/shells/bash build-dir-depends
shells/bash devel/ccache
shells/bash devel/gettext
devel/gettext devel/ccache
devel/gettext archivers/xz
archivers/xz devel/ccache
devel/gettext converters/libiconv
converters/libiconv devel/ccache
devel/gettext converters/libiconv

A pair, A B, in this list means "A is connected to B" (in that order, since it's a directed graph), and in the particular case shown here it means "A depends on B" (converters/libiconv needs to be built before devel/gettext because the latter depends on the former).

tsort takes the the partial ordering of pairs of nodes and returns a list of nodes in a total ordering compatible with that partial ordering:

$ make -C /usr/ports/shells/bash build-dir-depends | tsort -r
devel/ccache
archivers/xz
converters/libiconv
devel/gettext
shells/bash

Here, I've instructed tsort to reverse the resulting ordering (not possible on GNU systems as -r is not an option to GNU tsort), which gives me the order in which the system needs to build the packages while at the same time honouring the dependencies between them (ending up with building the final shells/bash package).

If tsort gets an input line

a b c d

then this is the same as

a b
c d

and as

a b c
d

That is, it always reads the nodes of the graph in pairs, no matter whether these are separated by spaces or newlines. The issue with your data,

a b c
b c d e

is that it can't be read as a list of pairs as it contains an odd number of nodes.

Answer 2

Yes, tsort reads its inputs in pairs separated by any whitespace, including newlines.

So the example from the tsort documentation:

tsort <<EOF
a b c
d
e f
b c d e
EOF

Defines the following pairs of orderings:

• a < b
• c < d
• e < f
• b < c
• d < e

And putting these all together, you get to a ordering of a < b < c < d < e < f, which in this case is a total ordering.

A reading of the source code confirms that, tsort uses readtoken() from gnulib with a set of delimiters comprised by space, tab and newline, in other words, any whitespace.

(My initial interpretation of that tsort example, to answer your other question, was that a line with b c d e created three implicit pairs, b < c, c < d and d < e, but that's really not the case, all whitespace is interpreted the same, including newlines, and a single pair is read at a time.)