¿Cuál es el mejor método (algoritmo) para calcular las relaciones en cascada continua entre los objetos?

Question

Por ejemplo A + B = C C + D = E E + F = G como se realizan cambios en cada nodo de los nodos asociados se vuelven a calcular. La imagen de abajo es un ejemplo simplista de lo que estoy tratando de hacer.

más aclaraciones La estructura de cada objeto es idéntico. las entradas serían los precios, ya que cada variaciones de los precios tendría un efecto en cascada sobre los precios de aguas abajo. por lo que en el ejemplo anterior A + B = C se convertiría en 5 + 6 = 11. etc.

Los cambios tienen lugar constantemente (posiblemente cada segundo), ya que se cambia cada valor que tendría que ser notificado (despedido de eventos).

Answer 1

Mientras que su gráfico no está cambiando, sólo los valores, se puede hacer una topológica sort de su gráfico. Luego caminar el gráfico de la orden de clasificación topológica a partir del valor (s) que cambió. Si los cambios van a ser una parte escasa de la gráfica, asignar a cada nodo de un índice en un orden topológico y utilizar un prioridad de la cola para decidir qué nodo a hacer a continuación.

Answer 2

La forma más sencilla jsut sería un método basado en eventos. Cada nodo tiene un evento "onChanged" y cualquier cosa que utiliza ese nodo pueden suscribirse a ese evento. Después de un nodo ha actualizado en sí plantea entonces ese evento y permite a cualquier otra cosa que necesita saber.

Si sus dependencias son más complejas entonces puede que tenga que tener algo más la gestión de los cambios a las cosas optimizar. por ejemplo, si los efectos A B y C y C también efectos B (por ejemplo B = A + C y C = A + 1), entonces un método simple podría actualizar a, entonces B, después C entonces B de nuevo. Esto funciona, pero es obviamente una actualización mroe lo que se requiere. La forma exacta de la optimización de los cambios dependerá de la complejidad de su árbol de dependencia es.