Топологическая сортировка, рекурсивная, с использованием генераторов
Вопрос
Данные:список зависимостей, уже проверенный на ацикличность.Итак, здесь "a" зависит от "b", "c" (c зависит от d) и т.д...
A = { 'a' : dict(b=1, c=1),
'c' : dict(d=1),
'd' : dict(e=1,f=1,g=1),
'h' : dict(j=1)
}
Я хотел бы иметь рекурсивное решение сверху вниз, чтобы, скажем, найти цепочку, начинающуюся с 'a':a, c, d, e, g, f, b
Итак, прямо сейчас (решение без генератора):
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
Очевидно, что это довольно слабо :) Я ломал голову над тем, как получить доходность внутри, и я был бы признателен за любую помощь, которую вы все можете внести в это.
Решение
Попробуй это:
#!/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
Дает мне
steve@rei:~/code/tmp $ python recur.py a c d e g f b
Другие советы
Оба ответа дают одинаковый результат, но если мое прочтение вопроса правильное, дайте неправильный ответ на простое изменение данного графика - если вы добавите зависимость от 'c' из 'b' (которая не вводит цикл по мере направления графика), результат будет:
a
c
d
e
g
f
b
d
e
g
f
что не совсем полезно.Попробуйте этот небольшой вариант, который отслеживает, какие узлы графика уже были посещены:
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