c# - 检测图何时重新收敛的算法(类似于公共(public)子树？)

Question

我一整天都在研究这个问题，我正在重写我们的一个遗留产品，我很难确定如何在我的流程图中找到特定的节点。这个问题让我想起了大学，但我一辈子都想不出解决这个问题的算法。

我附上了 3 个屏幕截图来帮助解释这一点，但基本问题是，给出是/否？决策节点，找到最近的终止分支的子节点。

我正在使用 C# .NET 和 JSON。在 JSON 中，我有一个对象，它为每个节点提供了一个唯一标识符，并且还标识了从一个节点到下一个节点的每个“链接”。我希望编写一个(或多个)函数来确定 C# 中给定分支节点的第一个“结束节点”。目前，我已经在 C# 中将 jSON 构建到 XML 中。

鼓励任何和所有想法，不是真正寻找代码，而是寻找方法/算法。

附件是图中jSON的输出:

{ "class": "go.GraphLinksModel",
  "linkFromPortIdProperty": "fromPort",
  "linkToPortIdProperty": "toPort",
  "nodeDataArray": [ 
{"key":-1, "category":"Start", "loc":"169 288", "text":"Start"},
{"key":-2, "category":"End", "loc":"855 394", "text":"End"},
{"category":"Branch", "text":"Yes or No", "key":-4, "loc":"284.8837209302326 285.7848837209302"},
{"category":"DelayNode", "text":"Delay", "key":-3, "loc":"365.8837209302326 215.52345997177622"},
{"category":"Branch", "text":"Yes or No", "key":-5, "loc":"478.8837209302326 214.52345997177622"},
{"category":"DelayNode", "text":"Delay", "key":-6, "loc":"568.8837209302326 151.52345997177622"},
{"category":"DelayNode", "text":"Delay", "key":-7, "loc":"573.8837209302326 268.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-8, "loc":"653.8837209302326 215.52345997177622"},
{"category":"Branch", "text":"Yes or No", "key":-9, "loc":"392.8837209302326 392.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-10, "loc":"454.8837209302326 317.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-11, "loc":"550.8837209302326 473.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-12, "loc":"549.8837209302326 317.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-13, "loc":"711.8837209302326 343.5234599717762"},
{"category":"Branch", "text":"Yes or No", "key":-14, "loc":"434.8837209302326 487.5234599717762"}
 ],
  "linkDataArray": [ 
{"from":-4, "to":-3, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-1, "to":-4, "fromPort":"R", "toPort":"L"},
{"from":-3, "to":-5, "fromPort":"R", "toPort":"L"},
{"from":-5, "to":-6, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-5, "to":-7, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-6, "to":-8, "fromPort":"R", "toPort":"L"},
{"from":-7, "to":-8, "fromPort":"R", "toPort":"L"},
{"from":-4, "to":-9, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-9, "to":-10, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-10, "to":-12, "fromPort":"R", "toPort":"L"},
{"from":-11, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-12, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-8, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-13, "to":-2, "fromPort":"R", "toPort":"L"},
{"from":-9, "to":-14, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-14, "to":-11, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-14, "to":-11, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"}
 ]}

Answer 1

更新:我提出了另一种解决方案，这次使用的是最低公共(public)祖先问题的标准解决方案。请参阅我的其他答案。

---

正如 Oren 回答的评论中所指出的，Oren 实际上已经回答了“从两个分支可以到达的最近节点是什么？”这个问题。但实际上要回答的问题是“两个分支必须到达的最近节点是什么？”

这是一个相当难解决的问题，我不知道有什么有效的解决方案。不过，这里有一个可行的算法草图。

假设给定的决策节点称为 A，WOLOG 它有两个子节点 B 和 C。那么问题是节点是什么，称为 G，具有这两个属性:

• 从 B 到 END 的每条可能路径，以及从 C 到 END 的每条可能路径，都经过 G。
• G 是距离 B 和 C 具有第一个属性的最近节点。

(注意 G 可能是 END。我们可能有 A-->B，A-->C，B-->END，C-->END。)

我们可以很容易地为可能的 G 制作一组候选者。选择从 B 到 END 的任何路径——如果你愿意，可以随机选择——并将其节点放入哈希集中。然后选择从 C 到 END 的任何路径，并将其节点放入哈希集中。这两个集合的交集包含 G。称交集为 Alpha。

现在让我们从 Alpha 中删除所有绝对不是 G 的节点。对于集合 Alpha 中的每个节点 N:

• 构造一个与原始图相同的新图，但缺少 N。
• END 是否仍然可以从新图中的 B 或 C 到达？如果是，那么N肯定不是G。如果不是，则加N设置Beta。

如果我们完成后 Beta 为空，则 G 为 END。

否则Beta中有节点。这些节点中的每一个都具有这样的属性，即如果它被删除，则没有其他方式可以从 B 或 C 到达 END。这些节点中的一个必须最接近 B —— 如果两个节点同样接近，那么其中一个就没有必要了! -- 所以从 B 做广度优先遍历，第一次遇到 Beta 节点，就是你的 G。

如果图形很大，这个草图似乎不会很快，但我很确定它会起作用。我很想知道是否有更好的解决方案。