ordenação topológica, recursivo, usando geradores
Pergunta
Dados: a lista de dependência, já verificado para ser acíclico. Então, aqui, 'a' depende 'b', 'c' (c depende d), etc ...
A = { 'a' : dict(b=1, c=1),
'c' : dict(d=1),
'd' : dict(e=1,f=1,g=1),
'h' : dict(j=1)
}
Eu gostaria de ter uma solução recursiva top-down, para digamos, encontrar a cadeia a partir de 'A': a, c, d, e, g, f, b
Então, agora mesmo (a solução não-gerador):
def get_all(D,k):
L = []
def get2(D,k):
L.append(k)
for ii in D.get(k,[]):
get2(D, ii)
get2(D,k)
return L
Obviamente, isso é muito fraco :) Eu estive batendo a cabeça sobre como a forma de obter rendimentos dentro lá, e eu apreciaria qualquer py-foo vocês pode trazer a este.
Solução
Tente isto:
#!/usr/bin/env python
def get_all(D, k):
yield k
for ii in D.get(k, []):
for jj in get_all(D, ii):
yield jj
A = { 'a' : dict(b=1, c=1),
'c' : dict(d=1),
'd' : dict(e=1,f=1,g=1),
'h' : dict(j=1)
}
for ii in get_all(A,'a'):
print ii
Dá-me
steve@rei:~/code/tmp $ python recur.py a c d e g f b
Outras dicas
Ambas as respostas dão o mesmo resultado, mas se a minha leitura da questão é dar correta a resposta errada a uma simples alteração ao gráfico dado - se você adicionar uma dependência em 'c' de 'b' (que não faz introduzir um ciclo como o gráfico é dirigida), o resultado é:
a
c
d
e
g
f
b
d
e
g
f
que não é totalmente útil. Tente esta pequena variação, que mantém o controle dos quais já foram visitadas nós do grafo:
def get_all(D, k, seen=None):
if not seen:
seen = set( )
if k not in seen:
seen.add(k)
yield k
for ii in D.get(k, []):
for jj in get_all(D, ii, seen):
yield jj