Problemas con un algoritmo de dependencia simple

Question

En mi aplicación web, tenemos muchos campos que resumen otros campos, y esos campos suman más campos. Sé que este es un gráfico acíclico dirigido.

Cuando la página se carga, calculo valores para todos los campos. Lo que realmente estoy tratando de hacer es convertir mi DAG en una lista unidimensional que contendría un orden eficiente para calcular los campos en.

Por ejemplo: A = B + D, D = B + C , B = C + E Orden de cálculo eficiente: E -> C -> B -> D -> A

Ahora mi algoritmo simplemente hace inserciones simples en una lista de forma iterativa, pero he encontrado algunas situaciones donde eso comienza a romperse Estoy pensando que lo que se necesitaría en su lugar sería calcular todas las dependencias en una estructura de árbol y, a partir de allí, convertir eso en una forma unidimensional. ¿Existe un algoritmo simple para convertir dicho árbol en un ordenamiento eficiente?

Answer 1

¿Está buscando topological sort? Esto impone un orden (una secuencia o lista) en un DAG. Se usa, por ejemplo, en hojas de cálculo para averiguar las dependencias entre las celdas para los cálculos.

Answer 2

Lo que desea es una búsqueda en profundidad.

function ExamineField(Field F) 
{ 
    if (F.already_in_list) 
     return 

    foreach C child of F 
    { 
     call ExamineField(C) 
    } 

    AddToList(F) 
} 

A continuación, sólo llaman ExamineField() en cada campo, a su vez, y la lista se llenará en una ordenación óptima de acuerdo a sus especificaciones.

Tenga en cuenta que si los campos son cíclico (es decir, usted tiene algo así como A = B + C, B = A + D), entonces el algoritmo debe ser modificado para que no entre en un bucle sin fin .

Para su ejemplo, las llamadas irían:

ExamineField(A) 
    ExamineField(B) 
    ExamineField(C) 
     AddToList(C) 
    ExamineField(E) 
     AddToList(E) 
    AddToList(B) 
    ExamineField(D) 
    ExamineField(B) 
     (already in list, nothing happens) 
    ExamineField(C) 
     (already in list, nothing happens) 
    AddToList(D) 
    AddToList(A) 
ExamineField(B) 
    (already in list, nothing happens) 
ExamineField(C) 
    (already in list, nothing happens) 
ExamineField(D) 
    (already in list, nothing happens) 
ExamineField(E) 
    (already in list, nothing happens) 

Y la lista terminarían C, E, D, C, A.