algorithm - Serialización de gráficos

sorting graph-algorithm

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 tiempo de compilación. Sé que debe ser algo bastante común de hacer, los compiladores lo hacen todo el tiempo, pero mi Google-Fu ha sido débil hoy. ¿Cuál es el algoritmo ''go-to'' para esto?

Answer 1

Esperaría que las herramientas que necesitan esto simplemente caminen sobre el árbol en profundidad y cuando toquen una hoja, simplemente procesen (por ejemplo, compilen) y quítenlo del gráfico (o márquelo como procesado, y traten los nodos con todas las hojas procesado como hojas).

Siempre que sea un DAG, esta simple caminata basada en la pila debería ser trivial.

Answer 2

He encontrado 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 la capacidad de detectar dependencias cíclicas; puede entrar en una recursión infinita (es decir, desbordamiento de la pila ;-p). La única forma de evitarlo que veo es voltear el algoritmo recursivo en uno interactivo con una pila manual y verificar manualmente la pila para ver si hay elementos repetidos.

Alguien tiene algo mejor?

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 se informa correctamente mediante el algoritmo anterior.

Answer 4

Clasificación topológica (de Wikipedia):

En la teoría de grafos, un ordenamiento topológico u ordenamiento topológico de un gráfico acíclico dirigido (DAG) es un ordenamiento lineal de sus nodos en el cual cada nodo viene antes de todos los nodos a los que tiene bordes de salida. Cada DAG tiene uno o más géneros 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)