algorithm - 算法如何解释有向节点图

Question

问题:解释节点图

最近我对节点编辑器很感兴趣，我指的是那些在 Maya 中看到和使用过的编辑器。 , Blender , Substance Painter , 以及 Unreal Engine 4 .

我的代码分为两部分，一部分处理 UI(创建节点、移动节点、附加节点)，另一部分，我现在正在处理的是基本上读取图表的解释器。

这是显示三个由边连接的节点的屏幕截图(它们的方向总是这样:粉色 -> 绿色)。一个节点可以有多个参数(绿色停靠点)和多个返回值(绿色停靠点)。

需要说明的是，我有一个对象会在屏幕上发生变化时更新(节点连接、节点创建/删除)。我想创建一个算法来解释/读取图形，以便运行节点描述的程序。

我找到了 this reddit thread这有助于我理解这个问题。然而，我仍然没有足够的信心开始为它编写代码。

我假设需要有一个起始节点，用于启动图形读取的东西，但我面临的问题是当它变得更复杂时，例如具有多个输入节点的图形。

(下图有红色注释。)

Answer 1

有向节点路径:

以下算法将解释此图节点:

关于节点图的更多细节:

1. 绿色码头是来自其他节点的变量，因此它们是必然是前一个节点输出的对象。另一方面方形码头是常量。

2. 我将引用“控制对象”，即保存图中停靠点之间所有链接的对象。

---

-- 算法开始 --

• 搜索所有输入节点，即所有左侧没有附加链接(无参数)的节点。

  there are five on this graph: A, B, C, E, and K they have only constant docks on their left: A1, B1, B2, C1, E1, E2, K1, and K2 are all defined variables.

• 节点是函数，输入节点是没有参数的函数。不需要其他值，因此我们可以计算这五个节点的输出。

  these outputs are A2, B3, C2, E3, E4, K3.

• 通过我们的控制对象，我们知道哪些扩展坞连接到这四个输出

  they link like so: A2 -> D1; B3 -> D2; C2 -> D3; C2 -> F1; E3 -> G2; E4 -> J1; K3 -> N3

注意:链接到多个绿色停靠点的粉红色停靠点被处理为好像有多个相同的粉红色停靠点。例如，在这里，节点 C 的输出 C2 可以看作是 C2 和 C2'(因为 C2 链接到 D3 AND 到 F1)。总共有 7 个链接需要分析。

• 再次使用我们的控制对象，我们将查看这 7 个链接的最终位置。

  they end in the D, F, G, J and N nodes

• 它们最终出现在五个不同的节点上。现在，我们可以计算出D输出、F输出、G输出、J输出和N输出吗？或者我们是否需要我们现在没有的其他变量？

  node D has three parameters and it just happens that we have all three parameters: D1, D2, D3 so we can calculate D's output right now: D4 node F has only one parameter and we have F1, we can calculate F's output: F2 node G has two parameters but we only have G2, we can't calculate G's output => store G2 in G's waiting queue in the control object node J same thing we have J1 but not J2 => store J1 in J's waiting queue in the control object node N has three parameters but we only have N3

• 在此步骤结束时，我们计算了 D4 和 F2 并将以下值存储在我们的控制对象中:N3(尚未使用因为我们还没有 N1，N2)，G2(因为我们没有 G1)和J1(因为我们没有 J2)。现在让我们看看 D4 和 F2 在哪里结束向上

  

  D4 ends up on the G node: on the G1 dock (therefore the object in D4 dock equals the object in G1) F2 ends up on J node: on the J2 dock (same here)

• 我们可以计算出 G 和 J 吗？

  for G we have 2 parameters on 2 so we can get G3 for J we have 2 parameters on 2 so we can get J3

  

• 检查 G3 和 J3 在哪里结束

  H, I and L nodes

• 我们可以计算它们吗？

  H has two parameters: H2 equal to G3 and the other one is set => we calculate H3 I has two parameters: I1 equal to G3 and the other one is set => we calculate I3 L has only one parameter: L1 => we calculate L2

• H3、I3、L2 在哪里结束？

  M and N

• 我们可以计算出 M 和 N 吗？

  M has two parameters, we have M1 and M2 => we can calculate M3 N has three parameters, we have N3 from the first step stored in N's parameters array and N2 is equal to L2 => we cannot calculate N

• 我们还有一个顶点需要解决:M3

  it goes to N, M3 = N1

• 我们可以计算 N 吗？

  now we can because we have N1, N2, N3 => we can calculate node N (no output in this case)

• 没有更多的顶点需要排序

-- 算法结束 --