Сериализация графов
-
08-06-2019 - |
Вопрос
Я ищу простой алгоритм для "сериализации" ориентированного графа.В частности, у меня есть набор файлов с взаимозависимостями в порядке их выполнения, и я хочу найти правильный порядок во время компиляции.Я знаю, что это, должно быть, довольно распространенная вещь - компиляторы делают это постоянно, - но мой google-fu сегодня был слабым.Каков алгоритм "перехода" к этому?
Решение
Топологическая сортировка (Из Википедии):
В теории графов топологическая сортировка или топологическое упорядочение направленного ациклического графа (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).Единственный способ обойти это, который я вижу, - это превратить рекурсивный алгоритм в интерактивный с ручным стеком и вручную проверить стек на наличие повторяющихся элементов.
У кого-нибудь есть что-нибудь получше?