Topological sort, recursive, using generators

generator, python, recursion, topology

Solution

Try this:

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

Gives me

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

Problem

Data: a dependency list, already verified to be acyclic. So here, 'a' depends on 'b','c' (c depends on 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) } ``` I'd like to have a top-down, recursive solution to let's say, find the chain starting at 'a': a, c, d, e, g, f, b So, right now (a non-generator solution): ``` 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 ``` Obviously, this is pretty weak :) I've been banging my head about how to how to get yields inside there, and I'd appreciate any py-foo y'all can bring to this.

Original source