Topological sort, recursive, using generators
Question
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.
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
OTHER TIPS
Both answers give the same result, but if my reading of the question is correct give the wrong answer to a simple alteration to the given graph - if you add a dependency on 'c' from 'b' (which doesn't introduce a cycle as the graph is directed) the output is:
a
c
d
e
g
f
b
d
e
g
f
which isn't totally helpful. Try this small variation, which keeps track of which nodes of the graph have already been visited:
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