Quelle est la meilleure approche (algorithme) aux relations en cascade sans cesse entre les objets calculate?

Question

Par exemple A + B = C C + D = E E + F = G en tant que des changements sont apportés à chaque noeud des noeuds associés sont recalculées. L'image ci-dessous est un exemple simpliste de ce que je suis en train de faire.

D'autres précisions La structure de chaque objet est identique. les entrées seraient les prix que chaque prix change, il aurait un effet en cascade sur les prix en aval. Ainsi, dans l'exemple ci-dessus A + B = C deviendrait 5 + 6 = 11. etc.

Les changements ont lieu en permanence (peut-être à chaque seconde), chaque valeur est modifiée je besoin d'être informé (tiré de l'événement).

Answer 1

Tant que votre graphique ne change pas, seules les valeurs, vous pouvez faire une tri topologique de votre graphique. Puis marcher le graphique dans l'ordre de tri topologique à partir de la valeur (s) qui a changé. Si les changements vont être une partie clairsemée du graphe, attribuer à chaque noeud un index dans l'ordre de tri topologique et utilisez un priorité file d'attente pour décider quel nœud à faire.

Answer 2

La façon la plus simple serait jsut être une méthode basée sur des événements. Chaque nœud a un événement « onChanged » et tout ce qui utilise ce nœud peuvent souscrire à cet événement. Après un nœud lui-même a mis à jour il soulève cet événement et laisse toute autre chose qui a besoin de connaître.

Si vos dépendances sont alors plus complexes, vous devrez peut-être avoir quelque chose d'autre gérer les mises à jour pour optimiser les choses. par exemple, si un des effets B et C et C B également des effets (par exemple B = A + C et C = A + 1), puis un procédé simple pourrait mettre à jour un, puis B, puis C puis B à nouveau. Cela fonctionne, mais est évidemment une mise à jour mroe que nécessaire. La manière exacte d'optimiser les mises à jour dépendra de la complexité de votre arbre est dépendance.