coreutils手册说
tsort 将其输入读取为字符串对,用空格分隔,表示部分排序。输出是与给定的部分排序相对应的全排序。例如
tsort <<EOF a b c d e f b c d e EOF
将产生输出
a b c d e f
“tsort 将其输入读取为字符串对”是什么意思,这对输入有什么要求?在这个例子中,第一行a b c
本身没有任何意义,但是a
和b
是成对的,所以c
和 也是成对的d
吗?
为什么这不起作用?
$ tsort <<EOF
> a b c
> b c d e
> EOF
tsort: -: input contains an odd number of tokens
答案1
是的,tsort 成对读取由任何空格(包括换行符)分隔的输入。
所以 tsort 文档中的示例:
tsort <<EOF
a b c
d
e f
b c d e
EOF
定义以下排序对:
- a < b
- c < d
- e < f
- b < c
- d < e
将这些放在一起,您可以得到 a < b < c < d < e < f 的排序,在本例中是全排序。
阅读源代码证实,tsort 使用来自 gnulib 的 readtoken()包含一组分隔符空格、制表符和换行符,换句话说,任何空白。
(我对那个 tsort 例子的初步解释,回答你的另一个问题,是一行b c d e
创建了三个隐式对,b < c,c < d 和 d < e,但事实并非如此,所有空白都被解释为相同,包括换行符,并且一次读取一对。 )
答案2
tsort
对有向图进行拓扑排序。它将图作为节点对获取。这些构成了图形的部分排序,并tsort
为您提供了总排序作为结果(不过,图形的总排序可能不止一个,请参阅BSD 系统上的-f
和选项的文档-h
(AFAIK 在 GNU 系统上不可用))。
真实图表示例(这些是shells/bash
在 OpenBSD 系统上构建软件包所需的 OpenBSD 软件包):
$ 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 B
此列表中的一对表示“A
连接到B
”(按该顺序,因为它是有向图),在此处显示的特定情况下,它表示“A
依赖于B
”(converters/libiconv
需要之前构建,devel/gettext
因为后者依赖于以前的)。
tsort
获取节点对的部分排序并返回与该部分排序兼容的全排序的节点列表:
$ make -C /usr/ports/shells/bash build-dir-depends | tsort -r
devel/ccache
archivers/xz
converters/libiconv
devel/gettext
shells/bash
在这里,我指示tsort
反转结果顺序(在 GNU 系统上不可能,因为-r
不是 GNU 的选项tsort
),这为我提供了系统构建包所需的顺序,同时尊重它们之间的依赖关系(最终构建最终shells/bash
包)。
如果tsort
得到输入线
a b c d
那么这与
a b
c d
并作为
a b c
d
也就是说,它总是读取图中的节点对,无论它们是用空格还是换行符分隔。您的数据有问题,
a b c
b c d e
是它不能被读取为对列表,因为它包含奇数个节点。