8
\$\begingroup\$

Kosaraju algorithm is mainly phrased as two recursive subroutines running postorder DFS twice to mark SCCs with linear time complexity O(V+E) below,

  1. For each vertex \$u\$ of the graph, mark \$u\$ as unvisited. Let \$L\$ be empty.

  2. For each vertex \$u\$ of the graph do Visit(\$u\$), where Visit(\$u\$) is the recursive subroutine:
        If \$u\$ is unvisited then:
            1. Mark \$u\$ as visited.
            2. For each out-neighbour \$v\$ of \$u\$, do Visit(\$v\$).
            3. Prepend \$u\$ to \$L\$.
        Otherwise do nothing.

  3. For each element \$u\$ of \$L\$ in order, do Assign(\$u\$,\$u\$) where Assign(\$u\$,\$root\$) is the recursive subroutine:
        If \$u\$ has not been assigned to a component then:
            1. Assign \$u\$ as belonging to the component whose root is \$root\$.
            2. For each in-neighbour \$v\$ of \$u\$, do Assign(\$v\$,\$root\$).
        Otherwise do nothing.

Here is the recursive implementation in Python according to the above recipe,

def kosaraju(G):
    
    # postorder DFS on G to transpose the graph and push root vertices to L
    
    N = len(G)
    T, L, U = [[] for _ in range(N)], [], [False] * N
    
    def visit(u):
        if not U[u]:
            U[u] = True
            for v in G[u]:
                visit(v)
                T[v].append(u)
            L.append(u)
    
    for u in range(N):
        visit(u)
    
    # postorder DFS on T to pop root vertices from L and mark SCCs
    
    C = [None] * N
    
    def assign(u, r):
        if U[u]:
            U[u] = False
            C[u] = r
            for v in T[u]:
                assign(v, r)
    
    while L:
        u = L.pop()
        assign(u, u)
    
    return C

The following iterative implementation scales well against the stack overflow due to excessively deep recursion. I revised the inner loop of the first iterative DFS so the linear time complexity O(V+E) is guaranteed now, however it deserves to be shared for further improvement.
I'll be glad about all your opinions or alternative implementations.

def kosaraju(G):
    
    # postorder DFS on G to transpose the graph and push root vertices to L
    N = len(G)
    T, L, U = [[] for _ in range(N)], [], [False] * N
    for u in range(N):
        if not U[u]:
            U[u], S = True, [u]
            while S:
                u, done = S[-1], True
                for v in G[u]:
                    T[v].append(u)
                    if not U[v]:
                        U[v], done = True, False
                        S.append(v)
                        break
                if done:
                    S.pop()
                    L.append(u)
    
    # postorder DFS on T to pop root vertices from L and mark SCCs
    C = [None] * N
    while L:
        r = L.pop()
        S = [r]
        if U[r]:
            U[r], C[r] = False, r
        while S:
            u, done = S[-1], True
            for v in T[u]:
                if U[v]:
                    U[v] = done = False
                    S.append(v)
                    C[v] = r
                    break
            if done:
                S.pop()
    
    return C

Test example:

G = [[1], [0, 2], [0, 3, 4], [4], [5], [6], [4], [6]]

print(kosaraju(G)) # => [0, 0, 0, 3, 4, 4, 4, 7]

enter image description here

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

(Work in progress)
I find the recursive variant pleasant enough to read:
• It picks up the names from the description referred
• The meaning of additional single-letter names isn't hard to guess
• there are comments to what's what

Main gripe: What can I use kosaraju(G) for, does it return something useful?
Have your source code document (non-private) parts:
Use docstrings.

Using loop-else, you don't need a done flag

def kosaraju(G):
    """ For a graph G given as a list of lists of node numbers
        find the strongly connected components.
        Use Kosaraju's algorithm:
        for each unvisited node, traverse and mark visited its out-neighbours,
          then add it to a sequence L
        for each unassigned node taken from L in reverse order,
          assign it to the same new SCC as all nodes reached via in-neighbours
    """
    # postorder DFT on G to transpose the graph and push root vertices to L
    N = len(G)
    T, L, visited = [[] for _ in  range(N)], [], [False] * N
    for u in range(N):
        if visited[u]:
            continue
        visited[u], stack = True, [u]
        while stack:
            u = stack[-1]
            for v in G[u]:
                T[v].append(u)
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)
                    break
            else:
                stack.pop()
                L.append(u)
    # print("L:", L)
    # try and follow en.wikipedia's hint and have
    #  visited indication share storage with the final assignment
    assigned = visited
                         
    # postorder DFT on T to pop root vertices from L and mark SCCs
    assigned = visited   # C = [None] * N
    while L:
        root = L.pop()
        if not visited[root] is True:
            continue
        assigned[root] = root
        stack = [root]
        while stack:
            # print("T[" + stack[-1] + "]: " + T[stack[-1]])
            for v in T[stack[-1]]:
                if visited[v] is True:
                    stack.append(v)
                    assigned[v] = root
                    break
            else:
                stack.pop()
    
    return assigned


if __name__ == '__main__':
    G = [[], [5, 4], [3, 11, 6], [7], [2, 8, 10], [7, 5, 3],
         [8, 11], [9], [2, 8], [3], [1], [9, 6]] 
    print(kosaraju(G))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.