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

Question

Données: une liste de dépendances, déjà vérifiée comme étant acyclique. Donc, ici, 'a' dépend de 'b', 'c' (c dépend 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)
    }

J'aimerais une solution récursive descendante pour trouver la chaîne à partir de 'a': a, c, d, e, g, f, b

Donc, maintenant (solution non génératrice):

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

Évidemment, c'est assez faible :) Je me suis cogné la tête pour savoir comment obtenir des rendements à l'intérieur, et j'apprécierais que tout le monde puisse y contribuer.

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

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, donner une mauvaise réponse à une simple modification du graphique donné - si vous ajoutez une dépendance à 'c' à partir de 'b' introduisez un cycle comme le graphique est dirigé) la sortie est: une c ré e g F b ré e g F

ce qui n'est pas totalement utile. Essayez cette petite variante, qui garde la trace des nœuds du graphique déjà 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