我使用过的Linux命令之tsort – 拓扑排序
我使用过的Linux命令之tsort – 拓扑排序
本文链接：http://codingstandards.iteye.com/blog/834572
? （转载请注明出处）
用途说明
tsort命令通常用于解决一种逻辑问题，即必须通过观察到的部分次序预测出整个次序。tsort命令可以对保存在文本文件中的数据进行拓扑排序，只要你按照一定的规则把数据写在文本文件中，然后使用tsort命令进行排序。
?
拓扑排序是对有向无环图的一种排序。表示了顶点按边的方向出现的先后顺序。如果有环，则无法表示两个顶点的先后顺序。
在现实生活中，也会有不少应用例子，比如学校课程布置图，要先修完一些基础课，才可以继续修专业课。
在软件开发中，比如多个模块之间的依赖关系、编译顺序，函数之间的调用关系等。
在项目管理中，各个任务之间的先后次序，某些任务完成之后才能进行另外的任务等。
一个简单的求拓扑排序的算法：首先要找到任意入度为0的一个顶点，删除它及所有相邻的边，再找入度为0的顶点，以此类推，直到删除所有顶点。顶点的删除顺序即为拓扑排序。
?
常用参数
无。
使用示例
示例一 来自info tsort的例子：根据部分顺序预测整体顺序
tsort输入数据的规则，把每两个数据作为一组，这两个数据就表明了一种部分顺序，每个数据之间以空白分隔，tsort处理结果就是根据这些部分顺序来推导出整体顺序来（`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.）。比如下面的数据，从上到下，a b是一组，c d又是一组，e f是一组，b c是一组，d e是一组。
[root@new55 ~]# tsort <<EOF
> a b c
> d
> e f
> b c d e
> EOF
a
b
c
d
e
f
[root@new55 ~]#
?
示例二 来自info tsort的例子：函数之间的调用关系
下面例子中的call-graph文件中保存了一个C程序中函数之间的调用关系（依赖关系），这个程序看起来像是tail命令的实现，文件第一行表明 main函数调用了 parse_options函数，第二行表明 main函数调用了tail_file函数，以此类推。后面使用tsort排序再采用tac逆序排列得到的结果就是在C文件中各个函数的顺序，比如先定义dump_remainder函数，再定义start_lines函数等。
[root@new55 ~]# cat call-graph
???? main parse_options
???? main tail_file
???? main tail_forever
???? tail_file pretty_name
???? tail_file write_header
???? tail_file tail
???? tail_forever recheck
???? tail_forever pretty_name
???? tail_forever write_header
???? tail_forever dump_remainder
???? tail tail_lines
???? tail tail_bytes
???? tail_lines start_lines
???? tail_lines dump_remainder
???? tail_lines file_lines
???? tail_lines pipe_lines
???? tail_bytes xlseek
???? tail_bytes start_bytes
???? tail_bytes dump_remainder
???? tail_bytes pipe_bytes
???? file_lines dump_remainder
???? recheck pretty_name
[root@new55 ~]# tsort call-graph | tac
dump_remainder
start_lines
file_lines
pipe_lines
xlseek
start_bytes
pipe_bytes
tail_lines
tail_bytes
pretty_name
write_header
tail
recheck
parse_options
tail_file
tail_forever
main
[root@new55 ~]#
?
示例三 比较sort和tsort
下面的happybirthday.txt中，Happy Birthday是一组，to You!是一组，Dear Tux!是一组，每组都表明了一种顺序，因为各个组之间的数据关联性不大，所以tsort的输出结果只是拓扑排序的一种可能结果而已。这个例子来自ibm的一篇文章，对于 tsort 的使用来说，这并非一个非常有用的演示，只是举例说明了这两个命令输出的不同。
[root@new55 ~]# cat happybirthday.txt
Happy Birthday to You!
Happy Birthday to You!
Happy Birthday Dear Tux!
Happy Birthday to You!
[root@new55 ~]# sort happybirthday.txt
Happy Birthday Dear Tux!
Happy Birthday to You!
Happy Birthday to You!
Happy Birthday to You!
[root@new55 ~]# tsort happybirthday.txt
Dear
Happy
to
Tux!
Birthday
You!
[root@new55 ~]#
?
实例四 根据jquery/js组件的依赖关系确定加载顺序
下面的例子中js.txt中保存了js脚本之间的依赖关系，每行的第一个文件依赖于后面的一个或多个文件。但这种格式显然不符合tsort的输入数据要求，因此编写脚本deps.sh把它转换成tsort要求的格式，即每行两个文件，前一个文件依赖于后一个文件。转换之后用tsort拓扑排序，然后用tac逆序输出之后就得到了这些js文件的正确加载顺序。
[root@new55 ~]# <s
