# 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 = 
stack = []; result = []
lowlinks = {}; index = {}

def tarjan(node):

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

try:
successors = graph[node]
except:
successors = []
for successor in successors:
tarjan(successor)
elif successor in stack:

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


• 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. Mar 16, 2020 at 7:27
• It uses a modified Tarjan's implementation ("Uses Tarjan’s algorithm_ with Nuutila’s modifications_" - from the link). Also, I'm trying to avoid using any libraries. Mar 16, 2020 at 7:59

## 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.