• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Sign in to follow this  
Followers 0

[Python] Robust topological sorting and Tarjan's algorithm in Python

1 post in this topic

The Strongly Connected Components of a directed graph are subsets of nodes such that each node within a subset can be reached from each other node. Tarjan's algorithm can identify these components efficiently (thanks njh for finding this algorithm).

By identifying strongly connected components ahead of time we can create a topological sorting algorithm that does the best it can in the presence of cycles.

Here is an implementation in Python:

* sort.py

Here are some things you might use this for:

* Install packages with circular dependencies in the best order you can.

* Work out in which order a set of equations must be solved, and which must be solved simultaneously.

* In a revision control system align as well as possible many versions of a file. (This is basically what I am using this for, but with DNA.)

in: http://www.logarithmic.net/pfh/blog/01208083168

Aqui fica o código para quem precisar


  Tarjan's algorithm and topological sorting implementation in Python

  by Paul Harrison

  Public domain, do with it as you will


def strongly_connected_components(graph):
   """ Find the strongly connected components in a graph using
       Tarjan's algorithm.

       graph should be a dictionary mapping node names to
       lists of successor nodes.

   result = [ ]
   stack = [ ]
   low = { }

   def visit(node):
       if node in low: return

num = len(low)
       low[node] = num
       stack_pos = len(stack)

       for successor in graph[node]:
           low[node] = min(low[node], low[successor])

       if num == low[node]:
    component = tuple(stack[stack_pos:])
           del stack[stack_pos:]
    for item in component:
        low[item] = len(graph)

   for node in graph:

   return result

def topological_sort(graph):
   count = { }
   for node in graph:
       count[node] = 0
   for node in graph:
       for successor in graph[node]:
           count[successor] += 1

   ready = [ node for node in graph if count[node] == 0 ]

   result = [ ]
   while ready:
       node = ready.pop(-1)

       for successor in graph[node]:
           count[successor] -= 1
           if count[successor] == 0:

   return result

def robust_topological_sort(graph):
   """ First identify strongly connected components,
       then perform a topological sort on these components. """

   components = strongly_connected_components(graph)

   node_component = { }
   for component in components:
       for node in component:
           node_component[node] = component

   component_graph = { }
   for component in components:
       component_graph[component] = [ ]

   for node in graph:
       node_c = node_component[node]
       for successor in graph[node]:
           successor_c = node_component[successor]
           if node_c != successor_c:

   return topological_sort(component_graph)

if __name__ == '__main__':
   print robust_topological_sort({
       0 : [1],
       1 : [2],
       2 : [1,3],
       3 : [3],


Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  
Followers 0