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

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

3 голосов
/ 20 сентября 2008

Данные: список зависимостей, уже проверенный на ацикличность. Итак, здесь «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

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

Ответы [ 2 ]

6 голосов
/ 20 сентября 2008

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

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

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