Clasificación topológica, recursiva, mediante generadores.
Pregunta
Datos:una lista de dependencias, ya verificada como acíclica.Entonces aquí, 'a' depende de 'b', 'c' (c depende de 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)
}
Me gustaría tener una solución recursiva de arriba hacia abajo para decir que la cadena comienza en 'A':a, c, d, e, g, f, b
Entonces, ahora mismo (una solución sin generador):
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, esto es bastante débil :) Me he estado dando vueltas en la cabeza sobre cómo obtener rendimientos allí, y agradecería cualquier py-foo que puedan aportar a esto.
Solución
Prueba esto:
#!/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
me da
steve@rei:~/code/tmp $ python recur.py a c d e g f b
Otros consejos
Ambas respuestas dan el mismo resultado, pero si mi lectura de la pregunta es correcta, daré la respuesta incorrecta a una simple alteración del gráfico dado: si agrega una dependencia de 'c' a partir de 'b' (que no introduce un ciclo como está dirigido el gráfico) el resultado es:
a
c
d
e
g
f
b
d
e
g
f
lo cual no es del todo útil.Pruebe esta pequeña variación, que realiza un seguimiento de qué nodos del gráfico ya han sido visitados:
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