Serialização de gráfico
-
08-06-2019 - |
Pergunta
Estou procurando um algoritmo simples para 'serializar' um gráfico direcionado.Em particular, tenho um conjunto de arquivos com interdependências na ordem de execução e quero encontrar a ordem correta em tempo de compilação.Eu sei que deve ser uma coisa bastante comum de se fazer - os compiladores fazem isso o tempo todo - mas meu google-fu está fraco hoje.Qual é o algoritmo 'go-to' para isso?
Solução
Classificação topológica (Da Wikipédia):
Na teoria dos gráficos, uma espécie topológica ou ordem topológica de um gráfico acíclico direcionado (DAG) é uma ordem linear de seus nós nos quais cada nó vem antes de todos os nós aos quais tem bordas de saída.Cada DAG tem um ou mais tipos topológicos.
Pseudo-código:
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)
Outras dicas
Eu esperaria que as ferramentas que precisam disso simplesmente percorressem a árvore em profundidade e, quando atingissem uma folha, apenas a processassem (por exemplo,compilar) e removê-lo do gráfico (ou marcá-lo como processado e tratar os nós com todas as folhas processadas como folhas).
Contanto que seja um DAG, essa caminhada simples baseada em pilha deve ser trivial.
Se o gráfico contém ciclos, como podem existir ordens de execução permitidas para seus arquivos?Parece -me que, se o gráfico contiver ciclos, você não terá solução, e isso é relatado corretamente pelo algoritmo acima.
Eu criei um algoritmo recursivo bastante ingênuo (pseudocódigo):
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);
O maior problema com isso é que ele não tem capacidade de detectar dependências cíclicas - pode entrar em recursão infinita (ou seja, estouro de pilha ;-p).A única maneira de contornar isso seria transformar o algoritmo recursivo em um algoritmo interativo com uma pilha manual e verificar manualmente a pilha em busca de elementos repetidos.
Alguém tem algo melhor?