I'm planning to useTarjan'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']}

• 1
  \$\begingroup\$Do you know ofnetworkx, which hasmultiple 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

  – Graipher

  2020-03-16 07:27:14 +00:00

  CommentedMar 16, 2020 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

  – Saurabh

  2020-03-16 07:59:34 +00:00

  CommentedMar 16, 2020 at 7:59

1 Answer1

Start asking to get answers

Find the answer to your question by asking.

Explore related questions

See similar questions with these tags.