Qual è l'approccio migliore (Algorithm) per i rapporti a cascata continuamente Calcolare tra gli oggetti?

Question

Per esempio A + B = C = C + D E E + F = G quale vengono apportate modifiche a ciascun nodo i nodi associati vengono ricalcolati. L'immagine qui sotto è un esempio semplicistico di quello che sto cercando di fare.

Un ulteriore chiarimento La struttura per ogni oggetto è identico. gli ingressi sarebbero prezzi come ogni prezzo cambia avrebbe un effetto a cascata sui prezzi a valle. così nell'esempio sopra A + B = C diventerebbe 5 + 6 = 11. ecc.

cambiamenti avvengono costantemente (possibilmente ogni secondo), in quanto ogni valore viene modificato avrei bisogno di ricevere una notifica (eventi sparato).

Answer 1

Fino a quando il grafico non cambia, solo i valori, si può fare una topologica sort del grafico. Poi a piedi il grafico in ordinamento topologico partire dal valore (s) che ha cambiato. Se i cambiamenti stanno per essere una parte sparso del grafico, assegnare ciascun nodo in un indice ordinamento topologico e utilizzare un priorità della coda per decidere quale nodo sul da farsi.

Answer 2

Il modo più semplice sarebbe finite essere un metodo basato su eventi. Ogni nodo ha un evento "onChanged" e tutto ciò che usi quel nodo possono iscriversi a questo evento. Dopo un nodo si è aggiornato allora solleva quell'evento e permette qualsiasi altra cosa che ha bisogno di sapere.

Se le dipendenze sono più complessi, allora potrebbe essere necessario avere qualcos'altro gestire gli aggiornamenti alle cose ottimizzare. ad esempio se gli effetti A B e C e C anche effetti B (ad esempio B = A + C e C = A + 1) allora un metodo semplice potrebbe aggiornare una, poi B, poi C poi B nuovamente. Questo funziona, ma è ovviamente un'aggiornamento mroe di quanto richiesto. Il modo esatto di ottimizzare gli aggiornamenti dipenderà dalla complessità vostro albero dipendenza è.