График сериализации

голоса
38

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

Задан 07/08/2008 в 01:22
источник пользователем
На других языках...                            


4 ответов

голоса
54

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

В теории графов, топологическая сортировки или топологическое упорядочение ориентированного ациклического графа (DAG) представляет собой линейный порядок его узлов, в которых каждый узел предшествует все узлы, к которым он имеет исходящие ребра. Каждый 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)
Ответил 07/08/2008 d 11:53
источник пользователем

голоса
1

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

Ответил 23/01/2009 d 16:09
источник пользователем

голоса
1

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

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

Ответил 07/08/2008 d 01:27
источник пользователем

голоса
0

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

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). Единственный способ обойти это, что я могу видеть, будет переворачивать рекурсивный алгоритм в итерационные один с ручным стеком, и вручную проверить стек для повторяющихся элементов.

Кто-нибудь есть что-то лучше?

Ответил 07/08/2008 d 01:30
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more