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):

     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.

Featured Articles:

• 20 Linux System Monitoring Tools Every SysAdmin Should Know
• 20 Linux Server Hardening Security Tips
• My 10 UNIX Command Line Mistakes
• Linux: 20 Iptables Examples For New SysAdmins
• 25 PHP Security Best Practices For Sys Admins
• The Novice Guide To Buying A Linux Laptop
• 10 Greatest Open Source Software Of 2009
• Top 5 Email Client For Linux, Mac OS X, and Windows Users
• Top 20 OpenSSH Server Best Security Practices
• Top 10 Open Source Web-Based Project Management Software
• Top 5 Linux Video Editor Software