Source code online books for professionals by professionals

Listing 4-9.  A Naïve Algorithm for Topological Sorting
def naive_topsort(G, S=None):
    if S is None: S = set(G)                    # Default: All nodes
    if len(S) == 1: return list(S)              # Base case, single node
    v = S.pop()                                 # Reduction: Remove a node
    seq = naive_topsort(G, S)                   # Recursion (assumption), n-1
    min_i = 0
    for i, u in enumerate(seq):
        if v in G[u]: min_i = i+1               # After all dependencies
    seq.insert(min_i, v)
    return seq
 
Although I hope it’s clear (by induction) that naive_topsort is correct, it is also clearly quadratic (by recurrence 
2 from Table 3-1). The problem is that it chooses an arbitrary node at each step, which means that it has to look 
where the node fits after the recursive call (which gives the linear work). We can turn this around and work more like 
selection sort. Find the right node to remove before the recursive call. This new idea, however, leaves us with two 
questions. First, which node should we remove? And second, how can we find it efficiently?
13
We’re working with a sequence (or at least we’re working toward a sequence), which should perhaps give us an 
idea. We can do something similar to what we do in selection sort and pick out the element that should be placed first 
(or last ... it doesn’t really matter; see Exercise 4-19). Here, we can’t just place it first—we need to really remove it from 
the graph, so the rest is still a DAG (an equivalent but smaller problem). Luckily, we can do this without changing the 
graph representation directly, as you’ll see in a minute.
How would you find a node that can be put first? There could be more than one valid choice, but it doesn’t matter 
which one you take. I hope this reminds you of the maximum permutation problem. Once again, we want to find the 
nodes that have no in-edges. A node without in-edges can safely be placed first because it doesn’t depend on any 
others. If we (conceptually) remove all its out-edges, the remaining graph, with n–1 nodes, will also be a DAG that can 
be sorted in the same way.
Tip
 
■
  If a problem reminds you of a problem or an algorithm you already know, that’s probably a good sign. In fact, 
building a mental archive of problems and algorithms is one of the things that can make you a skilled algorist. If you’re 
faced with a problem and you have no immediate associations, you could systematically consider any relevant  
(or semirelevant) techniques you know and look for reduction potential.
Just like in the maximum permutation problem, we can find the nodes without in-edges by counting. By 
maintaining our counts from one step to the next, we need not start fresh each time, which reduces the linear step 
cost to a constant one (yielding a linear running time in total, as in recurrence 1 in Table 3-1). Listing 4-10 shows an 
iterative implementation of this counting-based topological sorting. (Can you see how the iterative structure still 
embodies the recursive idea?) The only assumption about the graph representation is that we can iterate over the 
nodes and their neighbors.
13
Without effective selection, we’re not gaining anything. For example, the algorithms I’ve compared with, insertion and selection 
sort, are both quadratic, because selecting the largest or smallest element among unsorted elements isn’t any easier than inserting  
it among sorted ones.

---

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