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.