ordenação topológica, recursivo, usando geradores

Question

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.

Answer 1

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

Answer 2

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