Problemi con un semplice algoritmo di dipendenza

Question

Nella mia webapp, abbiamo molti campi che riassumono altri campi, e quei campi riassumono più campi. So che questo è un grafico aciclico diretto.

Quando la pagina viene caricata, calcolo i valori per tutti i campi. Quello che sto cercando di fare è convertire il mio DAG in un elenco unidimensionale che conterrebbe un ordine efficiente per calcolare i campi.

Ad esempio: A = B + D, D = B + C , B = C + E Ordine di calcolo efficiente: E -> C -> B -> D -> A

In questo momento il mio algoritmo esegue semplicemente inserimenti in una lista in modo iterativo, ma mi sono imbattuto in alcune situazioni in cui che inizia a rompersi. Sto pensando che sarebbe invece necessario elaborare tutte le dipendenze in una struttura ad albero, e da lì convertirlo in una forma unidimensionale? Esiste un semplice algoritmo per convertire un albero di questo tipo in un ordine efficiente?

Answer 1

Stai cercando topological sort? Questo impone un ordinamento (una sequenza o un elenco) su un DAG. Viene utilizzato, ad esempio, da fogli di calcolo, per calcolare le dipendenze tra le celle per i calcoli.

Answer 2

Quello che vuoi è una ricerca in profondità.

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

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

    AddToList(F) 
} 

Poi basta chiamare ExamineField() su ogni campo, a sua volta, e la lista sarà popolata in un ordinamento ottimale in base alle proprie specifiche.

Si noti che se i campi sono ciclici (ovvero, si ha qualcosa come A = B + C, B = A + D) allora l'algoritmo deve essere modificato in modo che non entri in un ciclo infinito .

Per esempio, le chiamate sarebbero andati:

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) 

E la lista finirebbe C, E, B, D, A.