Топологическая сортировка, рекурсивная, с использованием генераторов

Question

Данные: список зависимостей, уже проверенный как ациклический. Так вот, «а» зависит от «Ъ», «с» (с зависит от г), и т.д ...

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, б

Итак, прямо сейчас (раствор не-генератор):

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 

Очевидно, что это довольно слабый :) Я уже стучал головой о том, как получить урожай внутри, и я был бы признателен за любой py-foo y'all, который может это принести.

Answer 1

Попробуйте это:

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

Answer 2

Оба ответы дают тот же результат, но если моему чтение вопроса является правильным дать неправильный ответ на простые изменения в данном graph - если вы добавляете зависимость от '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