Tarjan's Algorithm Python Implementation

Question

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']
}

• Graipher: Do you know of networkx, which has multiple functions to deal with strongly connected components? It also uses Tarjan's algorithm (with some modifications), so even if you don't want to use it you could have a look at their implementation.
• Saurabh: It uses a modified Tarjan's implementation ("Uses Tarjan’s algorithm[1]_ with Nuutila’s modifications[2]_" - from the link). Also, I'm trying to avoid using any libraries.

Answer 1

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.