I recently needed to compute strongly connected components in graphs with Python, so I implemented Tarjan’s algorithm. The algorithm worked fine for small graph instances, but I needed to use it on graphs with up to 50000 vertices. Tarjan’s algorithm is recursive, and large graphs quickly caused “recursion depth exceeded” errors with Python. In the worst case, the algorithm needs 50000 stack activations, but Python has a fairly low maximum stack depth. When I tried to increase the recursion limit, as suggested in this SO post, this happened:
$ python b.py <chain.in
Segmentation fault: 11
The segmentation fault occurs because the Python process smashes its stack space. The process stack space is controlled by Linux and I did not want to mess with it.
The solution to these problems is to instead use an iterative algorithm. Fortunately, it was not too difficult to translate Tarjan’s algorithm into an iterative form. I just needed to add an extra stack and keep track of the next successor edge to visit for each vertex on the stack.
My implementations use adjacency lists to represent the graph (in the adj global). Here are my implementations. First, the standard recursive version:
next = 0 # Next index.
index = [None] * N
lowlink = [None] * N
onstack = [False] * N
stack = []
nextgroup = 0 # Next SCC ID.
groups = [] # SCCs: list of vertices.
groupid = {} # Map from vertex to SCC ID.
# Tarjan's algorithm.
def sconnect(v):
global next, nextgroup
index[v] = next
lowlink[v] = next
next += 1
stack.append(v)
onstack[v] = True
for w in adj[v]:
if index[w] == None:
sconnect(w)
lowlink[v] = min(lowlink[v], lowlink[w])
elif onstack[w]:
lowlink[v] = min(lowlink[v], index[w])
if index[v] == lowlink[v]:
com = []
while True:
w = stack[-1]
del stack[-1]
onstack[w] = False
com.append(w)
groupid[w] = nextgroup
if w == v: break
groups.append(com)
nextgroup += 1
for v in xrange(N):
if index[v] == None:
sconnect(v)
The iterative version differs only in the sconnect subroutine.
# Tarjan's algorithm, iterative version.
def sconnect(v):
global next, nextgroup
work = [(v, 0)] # NEW: Recursion stack.
while work:
v, i = work[-1] # i is next successor to process.
del work[-1]
if i == 0: # When first visiting a vertex:
index[v] = next
lowlink[v] = next
next += 1
stack.append(v)
onstack[v] = True
recurse = False
for j in range(i, len(adj[v])):
w = adj[v][j]
if index[w] == None:
# CHANGED: Add w to recursion stack.
work.append((v, j+1))
work.append((w, 0))
recurse = True
break
elif onstack[w]:
lowlink[v] = min(lowlink[v], index[w])
if recurse: continue # NEW
if index[v] == lowlink[v]:
com = []
while True:
w = stack[-1]
del stack[-1]
onstack[w] = False
com.append(w)
groupid[w] = nextgroup
if w == v: break
groups.append(com)
nextgroup += 1
if work: # NEW: v was recursively visited.
w = v
v, _ = work[-1]
lowlink[v] = min(lowlink[v], lowlink[w])
Leave a Reply