2024-02-07 - By Robert Elder
I use the 'tsort' command to perform a topological sort:
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:
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:
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:
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:
tsort: has-cycles.txt: input contains a loop:
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:
‘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
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.
A Surprisingly Common Mistake Involving Wildcards & The Find Command
A Guide to Recording 660FPS Video On A $6 Raspberry Pi Camera
Intro To 'stty' Command In Linux
The Most Confusing Grep Mistakes I've Ever Made
Intro To 'comm' Command In Linux
Use The 'tail' Command To Monitor Everything
How To Force The 'true' Command To Return 'false'
Why Bother Subscribing?