Serialización de gráficos

Question

Estoy buscando un algoritmo simple para "serializar" un gráfico dirigido.En particular, tengo un conjunto de archivos con interdependencias en su orden de ejecución y quiero encontrar el orden correcto en el momento de la compilación.Sé que debe ser algo bastante común (los compiladores lo hacen todo el tiempo), pero mi google-fu ha estado débil hoy.¿Cuál es el algoritmo de referencia para esto?

Answer 1

Orden topológico (De Wikipedia):

En la teoría de grafos, un orden topológico o un orden topológico de un gráfico acíclico dirigido (DAG) es un orden lineal de sus nodos en los que cada nodo viene antes de todos los nodos a los que tiene bordes de salida.Cada DAG tiene uno o más tipos topológicos.

Pseudocó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

Esperaría que las herramientas que necesitan esto simplemente recorran el árbol en profundidad y, cuando lleguen a una hoja, simplemente la procesen (p. ej.compilar) y eliminarlo del gráfico (o marcarlo como procesado y tratar los nodos con todas las hojas procesadas como hojas).

Mientras sea un DAG, este sencillo recorrido basado en pilas debería ser trivial.

Answer 3

Si el gráfico contiene ciclos, ¿cómo pueden existir órdenes de ejecución permitidas para sus archivos?Me parece que si el gráfico contiene ciclos, entonces no tiene solución, y esto es informado correctamente por el algoritmo anterior.

Answer 4

Se me ocurrió un algoritmo recursivo bastante ingenuo (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);

El mayor problema con esto es que no tiene capacidad para detectar dependencias cíclicas; puede entrar en recursividad infinita (es decir, desbordamiento de pila ;-p).La única forma de evitarlo que puedo ver sería convertir el algoritmo recursivo en uno interactivo con una pila manual y verificar manualmente la pila en busca de elementos repetidos.

¿Alguien tiene algo mejor?