日期:2014-05-16  浏览次数:20677 次

我使用过的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 ~]#