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

djthyrax

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

1 mensagem neste tópico

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)
       stack.append(node)

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

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

   for node in graph:
       visit(node)

   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)
       result.append(node)

       for successor in graph[node]:
           count[successor] -= 1
           if count[successor] == 0:
               ready.append(successor)

   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:
               component_graph[node_c].append(successor_c)

   return topological_sort(component_graph)


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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora