Сериализация графов

Question

Я ищу простой алгоритм для "сериализации" ориентированного графа.В частности, у меня есть набор файлов с взаимозависимостями в порядке их выполнения, и я хочу найти правильный порядок во время компиляции.Я знаю, что это, должно быть, довольно распространенная вещь - компиляторы делают это постоянно, - но мой google-fu сегодня был слабым.Каков алгоритм "перехода" к этому?

Answer 1

Топологическая сортировка (Из Википедии):

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

Псевдокод:

L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)

Answer 2

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

Пока это DAG, этот простой обход на основе стека должен быть тривиальным.

Answer 3

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

Answer 4

Я придумал довольно наивный рекурсивный алгоритм (псевдокод).:

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list

function resolve(a):
    if (dest.contains(a)) return;
    foreach (b in source[a]):
        resolve(b);
    dest.add(a);

foreach (a in source):
    resolve(a);

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

У кого-нибудь есть что-нибудь получше?