Running Kosaraju's Second Pass on the Original Graph

Kosaraju's second pass must search the reversed graph, and running it on the original graph merges strongly connected components that are not mutually reachable. The card shows the merged answer the mistake gives on the topic's graph, explains why the reversal stops it, and gives the fix.

The symptom is too few components, each too large. On the graph of Strongly Connected Components With Kosaraju's Two Passes, with edges A->B, B->A, B->C, C->D, D->E, E->C, E->F and G->F, the correct answer is four components: {A, B}, {C, D, E}, {F} and {G}. With the reversal left out, the same code reports two: {F, G} and {A, B, C, D, E}. Nothing crashes, and every vertex is still assigned exactly once, so the output looks plausible. The trigger is writing the second pass by reusing the first pass's search, which takes the original graph, and forgetting to hand it the reversed one.

The listing below runs the second pass both ways, from the same starts in the same order.

GRAPH = {
    "A": ["B"], "B": ["A", "C"], "C": ["D"], "D": ["E"],
    "E": ["C", "F"], "F": [], "G": ["F"],
}


def reversed_graph(graph):
    flipped = {vertex: [] for vertex in graph}
    for vertex, neighbours in graph.items():
        for neighbour in neighbours:
            flipped[neighbour].append(vertex)
    return flipped


def finishing_order(graph):
    visited, order = set(), []

    def visit(vertex):
        visited.add(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visit(neighbour)
        order.append(vertex)

    for vertex in graph:
        if vertex not in visited:
            visit(vertex)
    return order


def collect(graph, starts):
    visited, components = set(), []

    def visit(vertex, component):
        visited.add(vertex)
        component.append(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visit(neighbour, component)

    for start in starts:
        if start not in visited:
            component = []
            visit(start, component)
            components.append((start, component))
    return components


order = finishing_order(GRAPH)
print("first pass, finishing order:", " ".join(order))
starts = order[::-1]
print("second pass starts in order:", " ".join(starts))
for label, graph in (("reversed graph", reversed_graph(GRAPH)), ("original graph", GRAPH)):
    print(f"second pass on the {label}:")
    for start, component in collect(graph, starts):
        print(f"  from {start}: {' '.join(sorted(component))}")

first pass, finishing order: F E D C B A G
second pass starts in order: G A B C D E F
second pass on the reversed graph:
  from G: G
  from A: A B
  from C: C D E
  from F: F
second pass on the original graph:
  from G: F G
  from A: A B C D E

The mechanism is in which way edges point. The second pass starts from G, the vertex that finished last, because G's component has no edges coming in from other components. It may well have edges going out, and G does: G->F. On the reversed graph that edge points into G, so a search from G stays at G. On the original graph the search follows it out to F, and F joins G's component although F cannot reach G. The search from A does the same on a larger scale, crossing B->C into C, D and E, and those three are merged with A and B although none of them can get back.

The cost depends on what the components are for. A build tool that groups modules depending on each other in a cycle would report one large cycle of five modules where there are two small ones and a clean dependency between them. A road planner would mark one-way routes as two-way. The remedy is to build the reversed graph once, before the second pass, and search that. The order from the first pass is only half the algorithm: it says where to start, and the reversal is what keeps each search inside one component.