Topologische Sortierung, rekursiv, mit Generatoren

Question

Daten: eine Abhängigkeitsliste, bereits überprüft azyklisch sein. Also hier, 'a' hängt davon ab, 'b', 'c' (c hängt von 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)
    }

Ich möchte eine Top-down haben, um rekursive Lösung lassen Sie uns sagen, Start der Kette finden bei 'A': a, c, d, e, g, f, b

So, jetzt (eine nicht-Generator-Lösung):

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

Das ist natürlich ziemlich schwach :) Ich habe meinen Kopf über worden hämmern wie man, wie die Renditen dort hineinzukommen, und ich würde schätzen jede py-foo y'all dazu bringen kann.

Answer 1

Versuchen Sie folgendes:

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

Gibt mir

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

Answer 2

Beiden Antworten geben das gleiche Ergebnis, aber wenn meine Lektüre der Frage richtig geben die falsche Antwort auf eine einfache Änderung des Graphen - wenn Sie eine Abhängigkeit von ‚c‘ von ‚b‘ hinzuzufügen (was nicht Einführung eines Zyklus wie der graph gerichtet ist), der Ausgang ist: a c d e g f b d e g f

, die nicht ganz hilfreich ist. Versuchen Sie, diese kleine Veränderung, die verfolgt, welche Knoten des Graphen bereits besucht haben, hält:

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