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

Question

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

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

我正在使用 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

更新：我想出了另一个解决方案，这次使用的是最低共同祖先问题的标准解决方案。请参阅我的另一个答案。

---

正如对 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。

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

Answer 2

我喜欢亚历克斯的回答，它似乎很有效率。这是解决您的问题的另一种方法，事实证明这实际上是最低共同祖先问题。这是图论中研究得非常透彻的问题。一开始我只是没有看到它，因为您必须反转所有箭头。

使用此解决方案，您只需进行一次昂贵的预处理，然后您就可以拥有一个数据结构，您可以从中读取答案。

我已经在您的图表中标记了节点。您所做的是首先反转所有箭头，然后构建生成的 DAG 的欧拉遍历，在每个步骤中记住您离“根”（末端）有多远。

欧拉遍历是“访问自己，递归邻居，访问自己，递归邻居，......访问自己”。也就是说，如果我们用 C# 编写它，我们会这样说：

void Eulerian(Node n, int i, List<Tuple<Node, int>> traversal)
{
    traversal.Add(Tuple.Create(node, i));
    foreach(Node neighbour in node.Neighbours)
    {
        Eulerian(neighbour, i + 1, traversal);
        traversal.Add(Tuple.Create(node, i));
    }
}

欧拉遍历是您在走图时实际执行的遍历。

当您反转所有箭头并从 END 开始时，您作为示例给出的图具有以下欧拉遍历。

A0 B1 C2 D3 E4 F5 G6 H7 G6 F5 E4 D3 C2 I3 E4 F5 G6 H7 G6 F5 E4 I3 C2 
B1 J2 K3 L4 G5 H6 G5 L4 K3 J2 B1 M2 N3 L4 G5 H6 G5 L4 N3 M2 N3 L4 G5 
H6 G5 L4 N3 M2 B1 A0

现在可以从遍历中读取您的问题的答案。在您的示例中，您有决策节点 E、L 和 G。

对于 E：在遍历中找到 E 的第一次和最后一次出现。现在在遍历中搜索这两个节点之间的节点，以找到编号最小的节点。是C，2分。

对于 L：在遍历中找到 L 的第一次和最后一次出现。它们之间数字最小的节点是B，得分为1。

对于 G：再次出现 G 的第一次和最后一次出现之间得分最低的节点是 B。

如果图很大，计算遍历可能会很昂贵，但好处是您只需执行一次。之后，这只是一个线性搜索问题。（如果你真的想的话，你可以把它变成一个亚线性搜索问题，但这似乎需要做很多额外的工作。）

Answer 3

如果我理解这个问题，那么您正试图找到“是”和“否”子树之间的第一个公共节点。在这种情况下，一种简单的方法是对 yes 子树进行广度优先遍历，将每个元素添加到列表中。然后进行广度优先遍历或无子树，当该子树中的元素出现在“是”列表中时停止。

Answer 4

这可以使用两个广度/深度优先搜索在 O(V + E) 时间内完成。

首先，让我们描述问题。我们得到一个图，一个起始节点 A 和一个结束节点 END。正如@EricLippert 所定义的（我稍作修改，因为我们可以等效地使用 A 而不是 B 和 C），我们正在寻找具有以下两个属性的节点 G：

• 从 A 到 END 的所有可能路径都经过 G。
• G 是距离 A 最近且具有第一个属性的节点。

首先，我们使用 X 优先搜索找到从 A 到 END 的路径。设 P = (p1, p2, p3, ..., pk) 其中 p1 = A 和 pk = END 是这条路径，并将它们编号为 1、2、...、k（因此 pi 的编号为 i）。将这些数字与图中的节点一起存储。从图中删除 P 使用的边。从 A 开始另一个 X-first 搜索，找到从 A 可达的最高编号节点 pi。我们稍微调整一下这个搜索：每次我们找到一个比前一个最高可达节点 pk 更高的可达节点 pj，我们添加所有子路径 (pk, pk+1, ..., pj) 中的边返回图中，并将其间的所有这些节点标记为可访问，并将之前无法访问的所有节点添加到使用的队列/堆栈中在我们的 X 优先搜索处理中。返回以这种方式找到的 pi。

我们现在将证明 pi 满足 G 的条件。假设（为了达到矛盾的目的）我们有一条路径 S=(s1, s2, s3, ..., sj)，其中 s1 = A 和 sj = END不通过 pi。该路径的某些前缀 (s1, s2, s3, ... sm) 与我们的路径 P 一致，因此 s1=p1, s2=p2, ..., sm=pm，但 sm+1 != pm+1。由于 S 没有经过 pi 并且我们的第二次 X-first 搜索到达了 pi，所以当我们添加 (s1, s2, s3, ..., sm) 使用的边时，在我们的第二次 X-first 搜索中可以到达 sm . 因此，我们的第二次 X 优先搜索也将遍历路径 S 的其余部分，直到它到达 END 或 S 中使用的某个边 (pr, pr+1) 位于路径 P 但 r > i 并且因此这条边是删除。然而，我们会发现 pr（或 END）是可达的并且 r > i 所以我们不会返回 pi，这是一个矛盾。因此，

现在假设有一些节点 G' 具有上述属性，但比 pi 更接近 A。由于所有路径都经过 G'，P 也经过 G'，因此存在一些 v，pv=G' 且 v < i。由于所有路径都经过 G' 并且 (pv, pv+1) 已被删除，因此最初无法到达 pv 之外的任何节点，因此永远不会添加 (pv, pv+1) ，因此 pi 也永远无法到达，因此它不能拥有被我们的算法返回，这是一个矛盾。因此 pi 是最接近的此类节点，满足 G 的条件并且算法是正确的。

第一次 X 优先搜索需要 O(V+E) 时间。第二个也需要 O(V+E) 时间：所有节点最多被添加到队列/堆栈一次，因此即使我们将边添加回图，运行时间也会被保留；最终的边数也不超过原始图的边数。维护路径的索引和到目前为止找到的最高索引也需要 O(V+E) 时间，因此我们得出结论，我们的算法在 O(V+E) 时间内工作。

Answer 5

因此，考虑到此处提供的一些答案，我对此进行了更多思考，我还没有完全开始为其编写代码，但是给出了其中一个答案，我已将其稍微修改为伪代码。

我认为更有效的方法是跟踪公共字典变量（键，值）对中任何分支节点的所有结果。对这种方法有什么想法吗？我应该提到的一件事是，该图不应增长到超过 25 个节点。

//call this function for all nodes with 2 children
int getFirstCommonAllpathEndNode(currentNodeId, xml, endNodeId){

    Array[] possibleNodeIds;
    //traverse child nodes
    foreach(childnode of CurrentNode.TopPortChildNode){
        if(childNode has 2 ports)
        {
            possibleNodeIds.add( getFirstCommonAllPathEndNode(childNode.id, xml, endnodeId));
        }
        else{
            possibleNodeIds.add(childNode.Id);
        }
    }

    foreach(childnode of CurrentNode.BottomPortChildNode){
        if(childNode has 2 ports)
        {
            //recursive call for this branch to get it's first common all path end node
            var someNodeId = getFirstCommonAllPathEndNode(childNode.id, xml, endnodeId) 
            if(possibleNodeIds contains someNodeId) 
                return someNodeId;
            //otherwise skip forward to someNodeId as next node to process in for loop
        }
        else{
            if (possibleNodeIds contains childNode.Id)
                return childNode.id
        }
    }
    //return the endNode if nothing else is satisfied. although this code should never be hit
    return endNodeId;
}