Я ищу простой алгоритм «сериализации» ориентированного графа. В частности, у меня есть набор файлов с взаимозависимостями в порядке их выполнения, и я хочу найти правильный порядок во время компиляции. Я знаю, что это должно быть довольно распространенным делом - компиляторы делают это постоянно - но мой гугл-фу сегодня был слабым. Каков алгоритм перехода к этому?
Топологическая сортировка (из Википедии):
В теории графов топологическая сортировка или топологическое упорядочение ориентированного ациклического графа (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)
Я ожидал бы, что инструментам, которым это нужно, достаточно просто пройтись по дереву в глубину, а когда они попадают на лист, просто обработать его (например, скомпилировать) и удалить его из графа (или пометить его как обработанный, и обработать узлы всеми листьями обрабатывается как листья).
Пока это DAG, этот простой обход на основе стека должен быть тривиальным.
Я придумал довольно наивный рекурсивный алгоритм (псевдокод):
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). Единственный способ обойти это - перевернуть рекурсивный алгоритм в интерактивный с ручным стеком и вручную проверить стек на наличие повторяющихся элементов.
У кого-нибудь есть что-то лучше?
Если график содержит циклы, как могут существовать разрешенные порядки выполнения для ваших файлов? Мне кажется, что если график содержит циклы, то у вас нет решения, и об этом правильно сообщается с помощью вышеуказанного алгоритма.