Ir para o conteúdo
• Revista PROGRAMAR: Já está disponível a edição #57 da revista programar. Faz já o download aqui!

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

djthyrax    11

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.)

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

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

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

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

×