用于节点编辑器评估的高效图形遍历
Ste*_*ven 2 algorithm graph-theory graph-traversal directed-acyclic-graphs graph-algorithm
我有一个由用户创建的有向无环图，其中图的每个节点（顶点）代表对某些数据执行的操作。节点的输出取决于其输入（显然），并且该输入由其父节点提供。然后输出将传递给其子级。保证不存在循环，因此可以忽略。
该图的工作原理与Blender 中的着色器编辑器相同。每个节点对其输入执行一些操作，并且该操作的成本可能任意高。因此，我只想在严格要求时评估这些操作。
当通过用户输入或其他方式更新节点时，我需要重新评估每个节点，这取决于更新节点的输出。但是，鉴于我无法证明多次评估同一节点的合理性，我需要一种方法来确定更新节点的正确顺序。基本的广度优先遍历并不能解决问题。要了解原因，请考虑此图：
传统的广度优先遍历将导致D在 之前进行评估B，尽管D依赖于B。
我尝试过反向进行广度优先遍历（即从O1和O2节点开始，向上遍历图形），但我似乎遇到了同样的问题。反向广度优先遍历将访问Dbefore B，因此I2before A，导致I2被排序在 after A，尽管A取决于I2。
我确信我在这里遗漏了一些相对简单的东西，而且我觉得反向遍历似乎是关键，但我似乎无法全神贯注并让所有部分都适合。我认为一个潜在的解决方案是按预期使用反向遍历，但不是避免多次访问每个节点，而是在每次出现时访问每个节点，确保它具有绝对正确的顺序。但是多次访问每个节点以及随之而来的指数扩展是一个非常没有吸引力的解决方案。
对于此类问题是否有众所周知的有效算法？
是的，有一个众所周知的高效算法。这就是拓扑排序。
\n创建一个包含所有节点及其相应入度的字典，我们称之为indegree_dic。入度是该节点的父节点/或传入边的数量。拥有一组S入度为零的节点。
摘自维基百科页面并进行了一些修改：
\nL \xe2\x86\x90 Empty list that will contain the nodes sorted topologically\nS \xe2\x86\x90 Set of all nodes with no incoming edge that haven\'t been added to L yet\n\nwhile S is not empty do\n remove a node n from S\n add n to L\n for each child node m of n do\n decrement m\'s indegree\n if indegree_dic[m] equals zero then\n delete m from indegree_dic\n insert m into S\n\nif indegree_dic has length > 0 then\n return error (graph is not a DAG)\nelse \n return L (a topologically sorted order)\n这种类型并不是唯一的。我提到这一点是因为它对你的算法有一些影响。
\n现在，每当任何节点发生更改时，您都可以安全地避免重新计算拓扑排序列表中已更改节点之前的任何节点，但需要重新计算其之后的节点。如果您在计算中遵循排序列表，则可以确保所有父级都会在其子级之前得到处理。
\n该算法不是最佳的，因为更改的节点之后可能存在不是该节点的子节点的节点。就像下面的场景：
\n A\n / \\\n B C\n一种正确的拓扑排序是[A, B, C]。现在，假设B发生变化。您可以跳过，A因为它没有任何变化，但重新计算，C因为它出现在B. 但实际上你不需要这样做，因为B对任何事情都没有影响C。
如果影响不大，您可以使用此算法并使实现更容易并且不易出现错误。但如果效率是关键，那么以下一些想法可能会有所帮助：
\n- \n
您可以每次进行拓扑排序，并将哪个节点发生变化作为一个因素。从上述算法中选择节点时
\nS，请在选择更改的节点之前选择尽可能多的其他节点。换句话说，您S仅在S长度为 1 时选择更改的节点。这保证您处理不低于其之前的更改节点层次结构的每个节点。当排序比处理节点便宜得多时，这种方法很有用。 \n另一种方法（我不完全确定是否正确）是在拓扑排序列表中查看已更改的节点，并仅在到达已更改节点的第一个子节点时才开始处理。
\n \n另一种方法依赖于想法 1，但如果您可以进行一些预处理，则会很有帮助。您可以为每个更改节点的情况创建拓扑排序。当节点发生更改时，您会尝试尽可能晚地将其放入排序中。您将节点中的所有这些排序保存到排序字典中，并根据更改的节点选择该排序。
\n \n