5
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Graipher Mar 16 at 7:27
  • \$\begingroup\$ 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. \$\endgroup\$ – Saurabh Mar 16 at 7:59
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.