Source code online books for professionals by professionals

Listing 5-11.  Kosaraju’s Algorithm for Finding Strongly Connected Components
def tr(G):                                      # Transpose (rev. edges of) G
    GT = {}
    for u in G: GT[u] = set()                   # Get all the nodes in there
    for u in G:
        for v in G[u]:
            GT[v].add(u)                        # Add all reverse edges
    return GT
 
def scc(G):
    GT = tr(G)                                  # Get the transposed graph
    sccs, seen = [], set()
    for u in dfs_topsort(G):                    # DFS starting points
        if u in seen: continue                  # Ignore covered nodes
        C = walk(GT, u, seen)                   # Don't go "backward" (seen)
        seen.update(C)                          # We've now seen C
        sccs.append(C)                          # Another SCC found
    return sccs
 
If you try running scc on the graph in Figure 
5-7
, you should get the three sets {a, b, c, d}; {e, f, g}; and {i, h}.
19
 Note 
that when calling walk, I have now supplied the S parameter to make it avoid the previous SCCs. Because all edges are 
pointing backward, it would be all too easy to start traversing into these unless that was expressly prohibited.
Note
 
■
  it might seem tempting to drop the call to 
tr(G)
, to not reverse all edges and instead reverse the sequence 
returned by 
dfs_topsort
 (that is, to select starting points sorted by ascending rather than descending finish time).  
that would not work, however (as exercise 5-17 asks you to show).