Ordinamento topologico, ricorsivo, utilizzando generatori
Domanda
Dati: un elenco di dipendenze, già verificato come aciclico. Quindi qui 'a' dipende da 'b', 'c' (c dipende da d), ecc ...
A = { 'a' : dict(b=1, c=1),
'c' : dict(d=1),
'd' : dict(e=1,f=1,g=1),
'h' : dict(j=1)
}
Mi piacerebbe avere una soluzione ricorsiva dall'alto verso il basso per dire, trovare la catena che inizia da 'a': a, c, d, e, g, f, b
Quindi, proprio ora (una soluzione non generatrice):
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
Ovviamente, questo è piuttosto debole :) Ho sbattuto la testa su come ottenere rendimenti lì dentro, e apprezzerei qualsiasi py-foo che tutti voi possiate portare a questo.
Soluzione
Prova questo:
#!/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
Mi dà
steve@rei:~/code/tmp $ python recur.py a c d e g f b
Altri suggerimenti
Entrambe le risposte danno lo stesso risultato, ma se la mia lettura della domanda è corretta, dai la risposta sbagliata a una semplice alterazione del grafico dato - se aggiungi una dipendenza da 'c' da 'b' (che non introdurre un ciclo come indicato dal grafico) l'output è:
un
c
d
e
g
f
B
d
e
g
f
che non è del tutto utile. Prova questa piccola variazione, che tiene traccia di quali nodi del grafico sono già stati visitati:
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