如何有效地更新这样的有向图

本文关键字：有向图 更新 有效地 | 更新日期: 2023-09-27 18:34:57

>我有很多节点。Node的定义是这样的：

public class Node
{
   public string Name { get; private set; }
   string Expression { get; set; }
   double Value { get; private set; }
}

Value在运行时由表达式计算引擎计算。Expression可以引用其他Node，因此它可以形成有向图(或有向图列表(。假设图中没有循环。

下面是一个示例：

NodeA:
{
    Name: "NodeA",
    Expression: "[NodeB] + [NodeC] + 1.0"
    Value: 4.0
} 
NodeB:
{
    Name: "NodeB",
    Expression: "1.5"
    Value: 1.5
} 
NodeC:
{
    Name: "NodeC",
    Expression: "2.0"
    Value: 2.0
}

问题是，如果节点B被更改，如何有效地将更改传播到其他节点？我可以使用一些并行方法来更新图形吗？

谢谢！

如何有效地更新这样的有向图

您可以让每个节点维护依赖节点的列表以及一个"脏"标志。然后，每当节点更改时，递归地在每个依赖节点上设置脏标志。(如果节点已标记为脏，请不要递归。然后，您可以进行第二次传递以重新评估每个脏节点，在计算其新值时清除脏标志。

相关文章：