Intro To 'tsort' Command In Linux

2024-02-07 - By Robert Elder

     I use the 'tsort' command to perform a topological sort:

cat dependencies.txt

c d
a b
b c
f g
e f
d e

tsort dependencies.txt

a
b
c
d
e
f
g

Example Use Case Of Topological Sorting

     Here, I have a file called 'recipes.txt' that contains a list of crafting recipes for a certain block mining simulation game.  For this example, we'd like to find out the required order for crafting all items in this list:

Stone Stone_Pickaxe
Diamond Diamond_Pickaxe
Stick Wooden_Pickaxe
Stone_Pickaxe Metallic_Iron
Wooden_Pickaxe Stone
Iron_Pickaxe Diamond
Wooden_Block Stick
Metallic_Iron Iron_Pickaxe

     The list above shows which items in the game can be used to craft other items.  For example, the first line indicates that 'Stone' can be used to produce 'Stone_Pickaxe', and the second line indicates that 'Diamond' can be used to produce 'Diamond_Pickaxe' and so on.

     The following diagram shows a representation of the unordered crafting recipes in this list:

     Now, our goal is to find the 'ordered' list of items so we can start crafting the first item that doesn't rely on anything else, and then move down the list.  This can be done by using the 'tsort' command to topologically sort the list:

tsort recipes.txt

     The 'tsort' command will internally figure out how to traverse all edges of the graph so that every vertex can be visited in order:

     The final output is a condensed list that looks like this:

Wooden_Block
Stick
Wooden_Pickaxe
Stone
Stone_Pickaxe
Metallic_Iron
Iron_Pickaxe
Diamond
Diamond_Pickaxe

     Using the above list, you can now beat the game in the fastest way possible and become a famous speed runner!

Theory Of Topological Sorting

     A topological sort is a type of ordering that can be applied to a set of edges in a directed graph.

     In the context of graph theory, a set of directed edges can be described as topologically sorted when the source vertex always comes before the destination vertex in the ordering.

     Topological sorting may not possible if the graph contains cycles:

cat has-cycles.txt

a b
b c
c a

tsort has-cycles.txt

tsort: has-cycles.txt: input contains a loop:
tsort: a
tsort: b
tsort: c
a
b
c

Historical Origin Of 'tsort' Command

     According to info pages, the 'tsort' command exists because early versions of the Unix linker required object symbols to be topologically sorted.  However, this requirement has been obsolete since the early 1980s:

info 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 whole procedure has been obsolete since about 1980, because Unix
archives now contain a symbol table (traditionally built by ‘ranlib’,
now generally built by ‘ar’ itself), and the Unix linker uses the symbol
table to effectively make multiple passes over an archive file.
...

     And that's why the 'tsort' command is my favourite Linux command.