一些背景
我正在分析一个函数的控制流图,该函数基本上将传入数据映射到传出数据。大多数块都是这样的:
if (input_variable == SPECIFIC_CONSTANT) {
output_variable = TRUE;
}
else {
output_variable = FALSE;
}
此类代码的典型控制流图如下图所示
digraph G {
2 -> 3 -> 5;
2 -> 4 -> 5;
}
其中,3
and的执行取决于but4
的值是独立的。input_variable
5
问题
给定一个有向图和一个起始节点,我如何找到最近的节点,以使起始节点的任何路径都通过该节点?
示例:鉴于此图,我如何找到6
从2
或12
开始8
?
我可以反转最低共同祖先算法吗?它会有效吗?喜欢
for each node in graph:
ancestors = node.get_all_ancestors()
lca = find_lowest_common_ancestor(ancestors)
junction_node[lca] = node
get_junction_point(node):
return junction_node[node]
我的编程语言是 Python,我刚刚发现了 NetworkX,但任何算法都会受到赞赏。我不习惯图论,我想我错过了基本词汇表来找到我正在寻找的东西。
谢谢你的帮助!