Kosaraju-Sharir algorithm in Python
Two DFS passes, one on the graph and one on its transpose in reverse finishing order, find all SCCs.
- File
kosaraju_sharir.py, 54 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kosaraju-sharir/. The authors are listed in prov/TA3TXZ.jsonl.
def kosaraju_sharir(adj: list[list[int]]) -> list[int]:
"""Return comp, where comp[v] is the number of the strongly connected component of v.
The graph is directed, with vertices 0 .. n-1 and adjacency lists adj. Parallel
arcs (repeated entries) and self-loops (v in adj[v]) are allowed. The components
are numbered 0, 1, ... in the order the second pass finds them, which is a
topological order of the condensation: for each arc (u, v), comp[u] <= comp[v].
Both passes use explicit stacks, so long paths do not overflow the Python stack.
Time O(n + m), extra space O(n + m) for the transpose.
"""
n = len(adj)
# L1: a DFS of G that lists the vertices in order of finish time.
order: list[int] = []
seen = [False] * n
for root in range(n): # @line L1
if seen[root]:
continue
seen[root] = True
stack = [(root, 0)]
while stack:
u, i = stack[-1]
if i < len(adj[u]):
stack[-1] = (u, i + 1)
v = adj[u][i]
if not seen[v]:
seen[v] = True
stack.append((v, 0))
else:
stack.pop()
order.append(u) # u finishes
adj_t: list[list[int]] = [[] for _ in range(n)] # @line L2
for u in range(n):
for v in adj[u]:
adj_t[v].append(u)
comp: list[int] = [-1] * n # @line L3
k = -1
for u in reversed(order): # @line L4
if comp[u] != -1: # @line L5
continue
k += 1 # @line L6
# L7: ASSIGN(G^T, u, k), with an explicit stack.
todo = [u] # @line L7
comp[u] = k # @line L9
while todo:
x = todo.pop()
for y in adj_t[x]: # @line L10
if comp[y] == -1: # @line L11
comp[y] = k
todo.append(y)
return comp # @line L8
test_kosaraju_sharir.py 66 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kosaraju-sharir/. The authors are listed in prov/TA3TXZ.jsonl.
import random
from kosaraju_sharir import kosaraju_sharir
def reach(adj: list[list[int]], s: int) -> set[int]:
seen, todo = {s}, [s]
while todo:
u = todo.pop()
for v in adj[u]:
if v not in seen:
seen.add(v)
todo.append(v)
return seen
def check(adj: list[list[int]]) -> None:
n = len(adj)
comp = kosaraju_sharir(adj)
r = [reach(adj, u) for u in range(n)]
for u in range(n):
for v in range(n):
assert (comp[u] == comp[v]) == (v in r[u] and u in r[v])
for u in range(n):
for v in adj[u]:
assert comp[u] <= comp[v]
if n:
assert sorted(set(comp)) == list(range(max(comp) + 1))
def test_example() -> None:
adj = [[1, 3, 2], [2], [0], [2, 4], [], [4, 6], [5]]
assert kosaraju_sharir(adj) == [1, 1, 1, 1, 2, 0, 0]
def test_edges() -> None:
assert kosaraju_sharir([]) == []
assert kosaraju_sharir([[]]) == [0]
assert kosaraju_sharir([[0]]) == [0]
assert kosaraju_sharir([[1, 1], [0]]) == [0, 0]
assert kosaraju_sharir([[1], [2], []]) == [0, 1, 2]
assert kosaraju_sharir([[], [0], [1]]) == [2, 1, 0]
cycle = [[(i + 1) % 6] for i in range(6)]
assert kosaraju_sharir(cycle) == [0] * 6
def test_long_path() -> None:
n = 20000
path = [[i + 1] for i in range(n - 1)] + [[]]
assert kosaraju_sharir(path) == list(range(n))
path[-1] = [0]
assert kosaraju_sharir(path) == [0] * n
def test_random() -> None:
rng = random.Random(20)
for _ in range(600):
n = rng.randrange(1, 9)
m = rng.randrange(0, 3 * n)
adj: list[list[int]] = [[] for _ in range(n)]
for _ in range(m):
adj[rng.randrange(n)].append(rng.randrange(n))
check(adj)
What the next level needs
- the tests did not run in this build