Topological Sort with Make

It should be no surprise to anyone who has ever written a Makefile that it is possible to use make to perform topological sort. After all, make is typically used as a build automation tool where certain target files are built based on other prerequisites. This dependency between target files and prerequisites are expressed as target rules in the Makefile. The prerequisites themselves may appear as targets in other target rules.

To build a target, make must determine the order in which the various targets should be built so that all prerequisites of a target are built before building the targef itself. If we consider each target and its prerequisites to be vertices such that there is a directed edge from the target to each of its vertices, then we have a directed graph. Therefore, naturally, ordering the targets in such a way that the prerequisites of each target come before the target is equivalent to topologically sorting the directed graph.

Let us see the topological sort in action with a fictitious example. Imagine its Friday and you want to complete your work and enjoy a cup of tea.