Serialização de gráfico

Question

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?

Answer 1

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)

Answer 2

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.

Answer 3

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.

Answer 4

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?