serialização gráfica

votos
38

Eu estou procurando um algoritmo simples de 'serialize' um grafo direcionado. Em particular, eu tenho um conjunto de arquivos com interdependências na sua ordem de execução, e eu quero encontrar a ordem correta em tempo de compilação. Eu sei que deve ser uma coisa bastante comum para fazer - compiladores fazê-lo o tempo todo - mas meu google-fu tem sido fraco hoje. Qual é o algoritmo de 'go-to' para isso?

Publicado 07/08/2008 em 01:22
fonte usuário
Em outras línguas...                            


4 respostas

votos
54

Topológica Sort (Origem: Wikipédia):

Em teoria gráfico, uma espécie topológica ou ordenação topológica de um gráfico acíclico dirigido (DAG) é uma ordem linear dos seus nós, em que cada nó vem antes todos os nós a que 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)
Respondeu 07/08/2008 em 11:53
fonte usuário

votos
1

Se o gráfico contém ciclos, como pode Existem permitiu ordens de execução para seus arquivos? Parece-me que, se o gráfico contém ciclos, então você não tem solução, e este é relatado corretamente pelo algoritmo acima.

Respondeu 23/01/2009 em 16:09
fonte usuário

votos
1

Eu esperaria ferramentas que necessitam deste simplesmente andar a árvore de uma forma em profundidade e quando atingem uma folha, apenas processá-lo (por exemplo, compilar) e removê-lo a partir do gráfico (ou marcá-lo como processado, e tratar nós com todas as folhas processados ​​como folhas).

Enquanto é um DAG, este simples caminhada à base de pilha deve ser trivial.

Respondeu 07/08/2008 em 01:27
fonte usuário

votos
0

Eu vim com 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 para detectar dependências cíclicas - pode entrar em recursão infinita (ou seja, de estouro de pilha ;-p). A única maneira de contornar isso que eu posso ver seria para virar o algoritmo recursivo em um um interative com uma pilha manual e verificar manualmente a pilha de elementos repetidos.

Alguém tem algo melhor?

Respondeu 07/08/2008 em 01:30
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more