tsort: UNIX / Linux Perform Topological Sort

by on December 9, 2008 · 1 comment· LAST UPDATED December 9, 2008

in , ,

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.

TwitterFacebookGoogle+PDF versionFound an error/typo on this page? Help us!

{ 1 comment… read it below or add one }

1 subhash October 8, 2009 at 5:06 am

to send details me of all linux commands

Reply

Leave a Comment

Tagged as: , , , , , , , , ,

Previous Faq:

Next Faq: