tsort: UNIX / Linux Perform Topological Sort

Posted on in Categories , , , , , , , , last updated December 9, 2008

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
     e f
     b c d e

topological sort should produce output as follows:


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.

1 comment

Leave a Comment