tsort: UNIX / Linux Perform Topological Sort

See all UNIX related articles/faq
How do I perform topological sort or topological ordering without writing code in C or other programming languages? Using a shell script, how do I perform a topological sort on the given FILE?

Tsort is a Linux and Unix command-line tool that performs a topological sort on the input provided. This sort arranges the vertices in a directed acyclic graph (DAG) linearly. This means that for every edge uv, vertex u appears before vertex v in the ordering. Let us see how to use the tsort command in Linux and Unix.
Tutorial details
Difficulty level Easy
Root privileges No
Requirements Linux or Unix terminal
Category Linux shell scripting
OS compatibility BSD Linux macOS Unix
Est. reading time 3 minutes
Advertisement

Uisng tsort command in Linux and Unix to perform topological sort

As I said, 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 the 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

For example, if task A must be completed before task B can start, then there is an edge from vertex A to vertex B. So, imagine you have two tasks, A and B, and A needs to be completed before B can begin. In this scenario, there is an “edge” from A to B. To use the tsort tool, provide it with a list of pairs of strings separated by spaces, where each pair represents a dependency. For instance, if you want to express the dependency that A must be finished before B, you should pass the following pair to tsort:

A B

tsort command examples

Let us try out some example. Use the tsort command for topological sort:
$ tsort input.txt
$ tsort input.txt > output.txt

Here is another example. Create a new file using the cat command:
$ cat >test.txt
Add the following tasks:

a b
c d
b c

Now run the tsort:
$ tsort test.txt
tsort: UNIX Linux Perform Topological Sort at command Line

Summing up

To put it simply, tsort can help you figure out the correct sequence for performing tasks that rely on each other without causing any issues. For instance, it can assist in determining the order for compiling a group of source files or installing a set of software packages. For more info see the tsort command manual page by tying the man command:
$ man tsort

A note about tsort

The tsort command 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 that were undefined at that point in the link. For example:
$ ar cr my-library.a $(lorder ${MY_OBJS} | tsort)
The ar cr my-library.a $(lorder ${MY_OBJS} | tsort) command creates a static library called my-library.a from the object files listed in the variable $MY_OBJS. The lorder command orders the object files in a way that ensures that all dependencies are satisfied. The tsort command sorts the output of lorder in topological order, which ensures that the object files are archived in the correct order. For example, if the variable $MY_OBJS contains the following object files:

a.o b.o c.o d.o

And the lorder command produces the following output:

a.o b.o c.o d.o

Then the tsort command will sort the output of lorder in topological order, as follows:

a.o
c.o
b.o
d.o

Over time tsort utility has lost its importance, and for any serious/complex data sorting usage, you should use C or other programming languages.

🥺 Was this helpful? Please add a comment to show your appreciation or feedback.

nixCrat Tux Pixel Penguin
Hi! 🤠
I'm Vivek Gite, and I write about Linux, macOS, Unix, IT, programming, infosec, and open source. Subscribe to my RSS feed or email newsletter for updates.

4 comments… add one
  • subhash Oct 8, 2009 @ 5:06

    to send details me of all linux commands

  • Anonymous Nov 11, 2009 @ 7:13
    # Create a list of object files
    object_files_list="obj1.o obj2.o obj3.o obj3.o"
    
    # Sort the object files using tsort
    sorted_object_files=$(tsort <<< "$object_files_list")
    
    # Create a library archive from the sorted object files
    ar rcs libmyapplib.a $sorted_object_files
  • Nitya Kumari Mar 12, 2012 @ 1:45

    Create a new library file at command prompt:

    echo "libA.o libB.o" > lib.txt
    echo "libB.o libC.o" >> lib.txt
    echo "libC.o libD.o" >> lib.txt
    echo "libD.o libA.o" >> lib.txt

    Sort the library file using tsort command:

    tsort library.txt

    My outputs:

    libA.o
    libC.o
    libB.o
    libD.o
  • TechnicalMass Sep 21, 2023 @ 18:16

    This would be a lot more helpful if you explained what the original input represents in terms of the DAG.

Leave a Reply

Your email address will not be published. Required fields are marked *

Use HTML <pre>...</pre> for code samples. Your comment will appear only after approval by the site admin.