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

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

7.08.2008 00:22:54
4 ОТВЕТА
РЕШЕНИЕ

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

В теории графов топологическая сортировка или топологическое упорядочение ориентированного ациклического графа (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)
57
17.03.2011 12:34:52
Эх ... скопировано прямо из википедии?
Benjol 6.10.2008 07:00:24
Спасибо. Помог мне сопоставить тот факт, что дерево зависимостей может быть отсортировано с помощью этого метода. :-)
Shamasis Bhattacharya 9.12.2013 11:40:27

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

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

1
7.08.2008 00:27:19
Да, вот как ты это делаешь. Это называется поиск в глубину (DFS). И если вы не уверены, что у вас есть DAG, вы должны проверить наличие задних граней, иначе цикл отправит вас в бесконечный цикл.
sleske 30.09.2009 15:42:31

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

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

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

0
7.08.2008 00:30:52
вместо использования foreach какое-то время поддерживайте два указателя, проходящих через данные a, ведущий, который удваивает шаги, и трейлинг, который совершает шаги. Ведущий указатель обрабатывает точные значения разрешения, и, если он когда-либо перекрывает конечный указатель, возникает цикл.
Tenderdude 19.01.2017 17:11:08

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

1
23.01.2009 15:09:27
Да, топологическая сортировка невозможна, если граф содержит циклы. Это соответствует реальному миру: если я попрошу вас сделать A до B, а B до A, вы никак не сможете меня удовлетворить ;-).
sleske 30.09.2009 14:41:51