# Recursive and iterative implementation on Kosaraju algorithm

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.

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]


(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))