Source code online books for professionals by professionals

Figure 4-5.  A directed acyclic graph (DAG) and its nodes in topologically sorted order
The problem of topological sorting occurs in many circumstances in any moderately complex computer system. 
Things need to be done, and they depend on other things ... where to start? A rather obvious example is installing 
software. Most modern operating systems have at least one system for automatically installing software components 
(such as applications or libraries), and these systems can automatically detect when some dependency is missing and 
then download and install it. For this to work, the components must be installed in a topologically sorted order.
12
There are also algorithms (such as the one for finding shortest paths in DAGs and, in a sense, most algorithms 
based on dynamic programming) that are based on a DAG being sorted topologically as an initial step. However, 
while standard sorting algorithms are easy to encapsulate in standard libraries and the like, abstracting away graph 
algorithms so they work with any kind of dependency structure is a bit harder ... so the odds aren’t too bad that you’ll 
need to implement it at some point.
Tip
 
■
  If you’re using a unix system of some sort, you can play around with topological sorting of graphs described in 
plain-text files, using the 
tsort
 command.
We already have a good representation of the structures in our problem (a DAG). The next step is to look for some 
useful reduction. As before, our first intuition should probably be to remove a node and solve the problem (or assume 
that it is already solved) for the remaining n–1. This reasonably obvious reduction can be implemented in a manner 
similar to insertion sort, as shown in Listing 4-9. (I’m assuming adjacency sets or adjacency dicts or the like here; see 
Chapter 2 for details.)
12
The description “detect when some dependency is missing, download and install it” is, in fact, almost a literal description of 
another algorithm topological sorting, which is discussed in Chapter 5.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
83