Tarjan’s Algorithm Python Implementation

I’m planning to use Tarjan’s algorithm for a program in which I would be processing a file, converting the processed data to a dictionary, doing a topological sort on that dictionary (using this implementation), and then finding the longest path.

Is there any optimization that can be made to the below code, or can be be made more pythonic?

def strongly_connected_components(graph):

    index_counter = [0]
    stack = []; result = []
    lowlinks = {}; index = {}

    def tarjan(node):

        index[node] = index_counter[0]
        lowlinks[node] = index_counter[0]
        index_counter[0] += 1
        stack.append(node)

        try:
            successors = graph[node]
        except:
            successors = []
        for successor in successors:
            if successor not in lowlinks:
                tarjan(successor)
                lowlinks[node] = min(lowlinks[node],lowlinks[successor])
            elif successor in stack:
                lowlinks[node] = min(lowlinks[node],index[successor])

        if lowlinks[node] == index[node]:
            connected_component = []
            while True:
                successor = stack.pop()
                connected_component.append(successor)
                if successor == node: break
            component = tuple(connected_component)
            result.append(component)

    for node in graph:
        if node not in lowlinks:
            tarjan(node)

    return result

Source

The graph is unweighted, and would look something like this:-

test_graph = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}

Multi-statement lines

This:

stack = []; result = []
lowlinks = {}; index = {}
# ...
if successor == node: break

is generally discouraged; just use two lines.

snake_case

This:

lowlinks

is usually spelled out, i.e. low_links.

Bare except

    try:
        successors = graph[node]
    except:
        successors = []

has an except statement that’s too broad. If you expect a KeyError from this, then except KeyError.