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

← Competitive Coding Multiplying Polynomials with Fast Fourier Transform →

This site uses Akismet to reduce spam. Learn how your comment data is processed.