# Tarjan’s Algorithm Python Implementation

Posted on

Problem

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]
index_counter[0] += 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']
}

``````

Solution

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