- 浏览: 4754763 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
bzhao:
你也应该可以这样:(not tested)./rbtunnel ...
在Bash脚本中怎么关闭文件描述符? -
bzhao:
如果有A进程原代码情况下,通过如下调用,把他的子进程继承关闭则 ...
在Bash脚本中怎么关闭文件描述符? -
Master-Gao:
楼主咋没分析下源码呢?
我使用过的Linux命令之dirname - 截取给定路径的目录部分 -
jiedushi:
tail -F 就可以吧
Linux下实时跟踪log4j日志文件的bash脚本 - 增强了tail -f的功能 -
java_is_new:
新手学习了,就是不明白为一个网卡配多个ip有什么用
我使用过的Linux命令之ifconfig - 网络配置命令
我使用过的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 ~]# cat js.txt
pagination.js jquery.js
xheditor.js jquery.js
AreaData.js jquery.js
jquery.progressbar.js jquery.js
jquery.cookie.js jquery.js
hotkeys.js jquery.js
jsTree.js jquery.js
jquery.contextMenu.js jquery.js
jquery.messager.js jquery.js
jquery.jtemplates.js jquery.js
jquery.sound.js jquery.js
jquery.bgiframe.js jquery.js
jquery.ui.core.js jquery.js
jquery.ui.widget.js jquery.ui.core.js jquery.bgiframe.js
jquery.ui.mouse.js jquery.ui.core.js jquery.ui.widget.js
jquery.ui.draggable.js jquery.ui.core.js jquery.ui.mouse.js jquery.ui.widget.js
jquery.ui.position.js jquery.ui.core.js jquery.js jquery.bgiframe.js
jquery.ui.resizable.js jquery.ui.core.js jquery.ui.mouse.js jquery.ui.widget.js
jquery.ui.button.js jquery.ui.widget.js jquery.js
jquery.metadata.js jquery.js
jquery.msgc.js jquery.js json2.js
ajaxfileupload.js jquery.js
jquery.ui.dialog.js jquery.bgiframe.js jquery.ui.core.js jquery.ui.widget.js jquery.ui.button.js jquery.ui.draggable.js jquery.ui.mouse.js jquery.ui.position.js jquery.ui.resizable.js
[root@new55 ~]# cat deps.sh
#!/bin/sh
# 输入数据格式:每行的第一个文件依赖于本行后面其他的文件
# 输出数据格式:符合tsort要求的数据格式,每行两个文件,前面一个依赖于后面那个。
while read js deps
do
for dep in $deps
do
echo $js $dep
done
done
[root@new55 ~]# dos2unix js.txt
dos2unix: converting file js.txt to UNIX format ...
[root@new55 ~]# cat js.txt | ./deps.sh | tsort | tac
jquery.js
jquery.ui.core.js
jquery.bgiframe.js
jquery.ui.widget.js
jquery.ui.mouse.js
json2.js
xheditor.js
pagination.js
jsTree.js
jquery.ui.resizable.js
jquery.ui.position.js
jquery.ui.draggable.js
jquery.ui.button.js
jquery.sound.js
jquery.progressbar.js
jquery.msgc.js
jquery.metadata.js
jquery.messager.js
jquery.jtemplates.js
jquery.cookie.js
jquery.contextMenu.js
hotkeys.js
ajaxfileupload.js
AreaData.js
[root@new55 ~]#
问题思考
相关资料
【1】IBM developerworks 技巧: 用 sort 和 tsort 对文件进行排序
【2】维基百科 tsort (Unix)
【3】百度百科 拓扑排序
【4】gqf2008 图论算法——拓扑排序
【5】熟能生巧 拓扑排序
【6】维基百科 拓扑排序
【7】景高专 拓扑排序演示动画
发表评论
-
在Linux用tar归档压缩文件时忽略某些文件和目录
2013-02-01 10:19 17055在Linux下,常用tar对文 ... -
使用nmap扫描服务器端口的一次操作
2012-11-01 17:00 15143使用nmap扫描服务器端口的一次操作 本文来自:http ... -
我使用过的Linux命令之wget - ooo
2011-09-14 13:10 0我使用过的Linux命令之wg ... -
推荐一篇学习Vim使用的好文:酷壳 - 简明 Vim 练级攻略
2011-09-09 12:53 9151简明 Vim 练级攻略 http://coolshell.c ... -
推荐一篇学习Vim使用的好文:酷壳 - 简明 Vim 练级攻略
2011-09-09 12:49 1简明 Vim 练级攻略 http://coolshell.c ... -
我使用过的Linux命令之:(冒号) - 啥也不做(除了……)
2011-08-29 13:18 12104我使用过的Linux命令之: ... -
我使用过的Linux命令之date - 显示、修改系统日期时间
2011-08-25 09:21 41987我使用过的Linux命令之da ... -
我使用过的Linux命令之declare - 声明shell变量(不知道没关系、知道了就更好的内建命令)
2011-08-16 09:22 21836我使用过的Linux命令之declare - 声明shell变 ... -
我使用过的Linux命令之alias - 设置命令的别名,让 Linux 命令更简练
2011-08-11 09:31 28831我使用过的Linux命令之alias - 设置命令的别名,让 ... -
我使用过的Linux命令之ar - 创建静态库.a文件
2011-08-08 10:40 51936我使用过的Linux命令之ar - 创建静态库.a文件 本 ... -
我使用过的Linux命令之crontab - 设置例行任务(类似于Windows中的任务计划)
2011-08-04 22:26 9754我使用过的Linux命令之crontab - 设置例行任务(类 ... -
我使用过的Linux命令之chmod - 改变文件/目录的访问权限
2011-08-03 21:33 10709我使用过的Linux命令之chmod - 改变文件/目录的访问 ... -
我使用过的Linux命令之export - 设置或显示环境变量
2011-08-02 19:55 25442我使用过的Linux命令之export - 设置或显示环境变量 ... -
我使用过的Linux命令之wc - 统计文件行数、单词数或字节数
2011-07-26 10:50 29020我使用过的Linux命令之wc - 统计文件行数、单词数或字节 ... -
我使用过的Linux命令之groupdel - 删除群组
2011-07-22 22:13 9695我使用过的Linux命令之gr ... -
我使用过的Linux命令之ifconfig - 网络配置命令
2011-07-21 20:43 60560我使用过的Linux命令之ifconfig - 网络配置命令 ... -
我使用过的Linux命令之ll - 列出文件/目录的详细信息
2011-07-20 21:22 7210我使用过的Linux命令之ll ... -
我使用过的Linux命令之mkdir - 创建目录
2011-07-20 20:58 13690我使用过的Linux命令之mkdir - 创建目录 本文链 ... -
我使用过的Linux命令之perror - 解释错误代码
2011-07-18 20:29 25085我使用过的Linux命令之perror - 解释错误代码 ... -
我使用过的Linux命令之ping - 测试与目标主机的连通性
2011-07-16 10:46 26617我使用过的Linux命令之ping - 测试与目标主机的连通性 ...
相关推荐
Sort 命令可以对文件中的行进行排序、合并文件、查看是否需要排序等操作,而 Tsort 命令则可以对文件中的行进行拓扑排序。 Sort 命令的基本用法是使用 sort 命令后跟着要排序的文件名,例如 sort /etc/passwd 将对 ...
拓扑排序, 读取以空格分隔的有序对, 并且依靠输入模式进行排序. 三. uniq 这个过滤器将会删除一个已排序文件中的重复行. 这个命令经常出现在sort命令的管道后边. 四. expand, unexpand ... ...
在实际使用中,开发者可以通过阅读 tsort 的文档,了解如何创建有向图对象,添加边,以及调用拓扑排序方法。此外,通过 tsort-master 压缩包中的源代码,开发者可以深入学习其内部实现,这对于提升对数据结构和算法...
除了基本的`sort`命令,Linux还有`tsort`,它是拓扑排序工具,适用于处理依赖关系。比如在软件安装顺序的规划或者任务调度中,`tsort`可以确定任务间的依赖关系并给出正确的执行顺序。 在编程环境中,`sort`命令还...
使用方法,解压到本地目录,配置path,即可在dos下使用linux命令。 windows下能直接执行的linux命令,基本包括日常所有,如:[.exe grolbp.exe regtool.exe a2p.exe grolj4.exe rm.exe a2p5.10.0.exe grops.exe ...
linux 核心命令源码(cp mv cat chgrp chown cut date df du echo env expand expr find force fs group head hostname join kill link ls mkdir mv nice od paste printf ptx rm selinux seq sleep sort split stat...
linux下大部分常用命令源码,偶正要开始学习-_- base64.c basename.c c99-to-c89.diff cat.c chcon.c chgrp.c chmod.c chown.c chown-core.c chown-core.h chroot.c cksum.c comm.c copy.c cp.c cp-hash.c csplit.c ...
标题中的“让windowscmd也用上linux命令.pdf”指的是在Windows命令行环境下使用Linux命令,这一操作通常是通过安装模拟Linux环境的工具来实现的。描述中提到的问题是用户需要查看大文件的内容,但在Windows中直接...
104. **tsort=TopologicalSort**:拓扑排序。 105. **uname=UNixName**:显示系统信息。 106. **uncompress=UnCompress**:解压缩文件。 107. **uniq=Unique**:过滤重复的行。 108. **unzip=UnZIP**:解压ZIP格式的...
tsort 命令 ttt 命令 tty 命令 tunchange 命令 tuncheck 命令 tundefault 命令 tunrestore 命令 tunsave 命令 turnacct 命令 turnoff 命令 turnon 命令 tvi 命令 twconvdict 命令 twconvfont 命令 type 命令 ucfgif ...
对给定的文件进行拓扑排序 tty 显示标准输出设备连接终端的文件名 uname 打印系统信息 unexpand 把空格符转换成 tab uniq 抛弃指定文件或者标准输入中内容重复的行 unlink 删除指定文件 users 显示在...
图的应用 拓扑排序 TSort 关键路径 CritPath Dijkstra算法 DIJ Floyd算法 FLOYD 10 查找 静态查找 顺序查找、折半查找 SSearch 动态查找 二叉排序树 BSTSearch 散列查找 开放定址 LineHSearch 11 排序 插入...
它的默认操作是像tsort(1)一样工作,除了它按纯pkg / make依赖关系进行排序(tsort按语法拓扑排序:请参阅有关差异的注释)。 示例:$ echo -e“ be \ ne \ nc b” | 排序-k1,1 | gdeptrace [opts] ebc(b取决于e...
右下显示拓扑排序过程中入度为零的顶点的栈S,右上显示的栈 T 存放拓扑序列,其入栈顺序和栈 S 的出栈顺序相同,从栈顶到栈底的顶点顺序即为顶点的逆拓扑序列。算法执行结束后将弹出窗口列出全部结果,其中红色字体...
用函数模板方式设计一个函数模板sort,采用直接插入排序方式对数据进行 排序,并对整数序列和字符序列进行排序
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_...
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_...
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(shortpath_...
拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径 弗洛伊德算法(short...