Tri topologique, récursif, utilisant des générateurs

Question

Données: une liste de dépendances, déjà vérifiée pour être acyclique. Voici donc, 'a' dépend 'b', 'c' (c dépend 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) 
    } 

Je voudrais avoir un haut vers le bas, la solution récursive pour disons, trouver la chaîne à partir de 'a': a, c, d, e, g, f, b

Ainsi, en ce moment (une solution non générateur):

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 

de toute évidence, cela est assez faible :) Je me suis cogné la tête sur la façon d'obtenir des rendements à l'intérieur, et j'apprécierais tout py-foo y'all peut apporter à cela.

Answer 1

Essayez ceci:

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

Ça me donne

 
steve@rei:~/code/tmp 
$ python recur.py 
a 
c 
d 
e 
g 
f 
b 

Answer 2

Les deux réponses donnent le même résultat, mais si ma lecture de la question est correcte donne la mauvaise réponse à une simple modification à la donnée graphe - si vous ajoutez une dépendance à 'c' de 'b' (qui n'introduit pas un cycle comme le graphique est dirigé) la sortie est: a c d e g f b d e g f

ce qui n'est pas totalement utile . Essayez cette petite variation, qui garde la trace des noeuds du graphique qui ont déjà été visités:

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