tsort: UNIX / Linux Perform Topological Sort

Q. How do I perform topological sort or topological ordering without writing code in C or other programming language? How do I performs a topological sort on the given FILE using a shell script?

A. A topological sort or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts. Consider following sample input data (input.txt):

ADVERTISEMENTS

     a b c
     d
     e f
     b c d e

topological sort should produce output as follows:

     a
     b
     c
     d
     e
     f

tsort command

Use tsort command for topological sort:
$ tsort input.txt
$ tsort input.txt > output.txt

A note about tsort

tsort exists because very early versions of the Unix linker processed an archive file exactly once, and in order. As ld read each object in the archive, it decided whether it was needed in the program based on whether it defined any symbols which were undefined at that point in the link. This utility has lost its importance and for any serious / complex data sorting usage your should use C or other programming language.

🐧 Get the latest tutorials on SysAdmin, Linux/Unix, Open Source/DevOps topics:
CategoryList of Unix and Linux commands
File Managementcat
FirewallCentOS 8 OpenSUSE RHEL 8 Ubuntu 16.04 Ubuntu 18.04 Ubuntu 20.04
Network Utilitiesdig host ip nmap
OpenVPNCentOS 7 CentOS 8 Debian 10 Debian 8/9 Ubuntu 18.04 Ubuntu 20.04
Package Managerapk apt
Processes Managementbg chroot cron disown fg jobs killall kill pidof pstree pwdx time
Searchinggrep whereis which
User Informationgroups id lastcomm last lid/libuser-lid logname members users whoami who w
WireGuard VPNCentOS 8 Debian 10 Firewall Ubuntu 20.04

ADVERTISEMENTS
1 comment… add one
  • subhash Oct 8, 2009 @ 5:06

    to send details me of all linux commands

Leave a Reply

Your email address will not be published.

Use HTML <pre>...</pre>, <code>...</code> and <kbd>...</kbd> for code samples.