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

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

更新:我提出了另一种解决方案,这次是使用最常见祖先问题的标准解决方案.看到我的其他答案.

正如评论奥伦的回答指出,奥伦实际上已经回答了这个问题:"什么是最接近的节点可以从两个分支到达？" 但实际上要回答的问题是" 两个分支必须达到的最接近的节点是什么？"

这是一个难以解决的问题,我不知道一个有效的解决方案.但是,这是一个可行的算法草图.

假设给定的决策节点被称为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中删除绝对不是G的所有节点.对于集合Alpha中的每个节点N:

• 构造一个与原始图形相同的新图形,但缺少N.
• 在新图表中,是否可以从B或C到达END？如果是,则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 子树进行广度优先遍历，将每个元素添加到列表中。然后进行广度优先遍历或 no 子树，当该子树中的元素出现在“yes”列表中时停止。