Алгоритм топологической сортировки при наличии циклов

Это NP-трудная (и APX-трудная) проблема, известная как минимальный набор вершин обратной связи. Алгоритм аппроксимации, разработанный Деметреску и Финокчи (pdf, Комбинаторные алгоритмы для задач обратной связи в ориентированных графах (2003) ") хорошо работают на практике, когда нет длинных простых циклов, как я ожидал от вашего приложения.

Вот как это сделать в Python:

from collections import defaultdict

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    for h, t in dependency_pairs:
        num_heads[t] += 1
        tails[h].append(t)

    ordered = [h for h in tails if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.iteritems() if heads]
    return ordered, cyclic

def is_toposorted(ordered, dependency_pairs):
    '''Return True if all dependencies have been honored.
       Raise KeyError for missing tasks.
    '''
    rank = {t: i for i, t in enumerate(ordered)}
    return all(rank[h] < rank[t] for h, t in dependency_pairs)

print topological_sort('aa'.split())
ordered, cyclic = topological_sort('ah bg cf ch di ed fb fg hd he ib'.split())
print ordered, cyclic
print is_toposorted(ordered, 'ah bg cf ch di ed fb fg hd he ib'.split())
print topological_sort('ah bg cf ch di ed fb fg hd he ib ba xx'.split())

Время выполнения линейно пропорционально количеству ребер (пар зависимостей).

Алгоритм организован вокруг таблицы поиска под названием num_heads, в которой ведется подсчет количества предшественников (входящих стрелок). В примере ah bg cf ch di ed fb fg hd he ib подсчеты:

node  number of incoming edges
----  ------------------------
 a       0
 b       2
 c       0
 d       2
 e       1
 f       1  
 g       2
 h       2
 i       1

Алгоритм работает, "просматривая" узлы без предшественников. Например, узлы a и c не имеют входящих ребер, поэтому они посещаются первыми.

Посещение означает, что узлы выводятся и удаляются с графика. Когда узел посещается, мы перебираем его последователей и уменьшаем их входящее число на единицу.

Например, при посещении узла a мы переходим к его преемнику h, чтобы уменьшить его входящий счет на единицу (так что h 2 становится h 1.

Аналогичным образом, при посещении узла c мы перебираем его преемников f и h, уменьшая их счетчики на единицу (так что f 1 становится f 0, а h 1 становится h 0).

Узлы f и h больше не имеют входящих ребер, поэтому мы повторяем процесс их вывода и удаления из графа, пока не будут посещены все узлы. В примере порядок посещения (топологическая сортировка):

a c f h e d i b g

Если num_heads когда-либо достигает состояния, когда нет узлов без входящих ребер, это означает, что существует цикл, который не может быть топологически отсортирован, и алгоритм завершается.