节点编辑器评估的高效图遍历

Question

我有一个由用户创建的有向无环图，其中图的每个节点（顶点）代表对某些数据执行的操作。一个节点的输出取决于它的输入（显然），而该输入由它的 parents 提供。然后将输出传递给它的 children。循环保证不存在，所以可以忽略。

此图表的工作原理与 Shader Editor in Blender 相同。每个节点对其输入执行一些操作，并且这个操作可以任意昂贵。因此，我只想在严格要求时评估这些操作。

当通过用户输入或其他方式更新节点时，我需要重新评估每个节点，这取决于更新节点的输出。但是，鉴于我无法证明多次评估同一个节点是合理的，我需要一种方法来确定更新节点的正确顺序。基本的 breadth-first 遍历并不能解决问题。要了解原因，请考虑此图：

传统的 breadth-first 遍历会导致 D 在 B 之前被求值，尽管 D 取决于 B.

我试过进行 breadth-first 反向遍历（即从 O1 和 O2 节点开始，然后遍历 up 图），但我似乎运行遇到了同样的问题。反向 breadth-first 遍历将在 B 之前访问 D，因此 I2 在 A 之前，导致 I2 在 之后被排序 A，尽管 A 取决于 I2。

我确定我在这里遗漏了一些相对简单的东西，我觉得反向遍历是关键，但我似乎无法全神贯注并让所有部分都适合。我想一个潜在的解决方案是按预期使用反向遍历，而不是避免多次访问每个节点，而是每次出现时都访问每个节点，确保它具有绝对正确的顺序。但是多次访问每个节点以及随之而来的指数缩放是一个非常没有吸引力的解决方案。

是否有针对此类问题的 well-known 高效算法？

Answer 1

是的，有一个众所周知的高效算法。这是 topological sorting.

创建一个包含所有节点及其对应的字典in-degree，我们称之为indegree_dic。 in-degree 是该节点的 parents/or 传入边的数量。有一组 S 个 in-degree 等于零的节点。

取自维基百科页面并进行了一些修改：

L ← Empty list that will contain the nodes sorted topologically
S ← Set of all nodes with no incoming edge that haven't been added to L yet

while S is not empty do
    remove a node n from S
    add n to L
    for each child node m of n do
        decrement m's indegree
        if indegree_dic[m] equals zero then
            delete m from indegree_dic
            insert m into S

if indegree_dic has length > 0 then
    return error   (graph is not a DAG)
else 
    return L   (a topologically sorted order)

这种排序不是唯一的。我提到它是因为它对你的算法有一些影响。

现在，每当任何节点发生更改时，您都可以安全地避免重新计算拓扑排序列表中更改节点之前的任何节点，但需要重新计算它之后的节点。如果您在计算中遵循排序列表，则可以确保所有 parents 在它们的 children 之前被处理。

这个算法不是最优的，因为在更改的节点之后可能有节点不是该节点的 children。就像在下面的场景中：

    A
   /  \
  B    C

一种正确的拓扑排序是[A, B, C]。现在，假设 B 发生变化。您跳过 A 因为它没有任何变化，但是重新计算 C 因为它在 B 之后。但实际上你不需要，因为 B 对 C 没有任何影响。

如果这个影响不大，你可以使用这个算法，让实现更容易，更不容易出错。但如果效率是关键，这里有一些想法可能会有所帮助：

你可以每次做一个拓扑排序，把哪个节点发生变化作为一个因素。在上述算法中从 S 中选择节点时，在选择更改的节点之前，请尽可能选择其他节点。换句话说，仅当 S 的长度为 1 时，您才从 S 中选择更改的节点。这保证您处理不低于更改节点之前的层次结构的每个节点。当排序比处理节点便宜得多时，这种方法会有所帮助。
另一种我不完全确定是否正确的方法是在拓扑排序列表中查看更改的节点，并且仅在到达第一个 child 时才开始处理更改的节点。
另一种方法依赖于想法 1，但如果您可以做一些事情会很有帮助 pre-processing。您可以为更改一个节点的每种情况创建拓扑排序。更改节点时，您会尝试将其尽可能晚地放入排序中。您将所有这些排序保存在一个节点中以排序字典，并根据更改的节点选择该排序。

节点编辑器评估的高效图遍历

Efficient Graph Traversal for Node Editor Evaluation

algorithm

graph-theory

graph-traversal

directed-acyclic-graphs

graph-algorithm