python - 有向图 : Nearest node that joins all paths

Question

一些背景

我正在分析一个函数的控制流图，该函数基本上将传入数据映射到传出数据。大多数 block 都是这样的:

if (input_variable == SPECIFIC_CONSTANT) {
    output_variable = TRUE;
}
else {
    output_variable = FALSE;
}

此类代码的典型控制流图如下图所示

digraph G {
  2 -> 3 -> 5;
  2 -> 4 -> 5;
}

Picture of the graphe

3 和 4 的执行取决于 input_variable 的值，但 5 是独立的。

问题

给定一个有向图和一个起始节点，我如何找到最近的节点，使得起始节点的任何路径都经过该节点？

示例:给定 this graph如何找到从 2 开始的 6 或从 8 开始的 12？

我可以反转最低公共(public)祖先算法吗？它是否有效？喜欢

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，但任何算法都将不胜感激。我不习惯图论，我想我错过了基本词汇表来找到我要找的东西。

感谢您的帮助!

Answer 1

这不是最有效的解决方案，但这里有一些可以帮助您入门的方法:

做一个DFS，然后计算所有路径的交集(每条路径中都存在的节点)。然后，在这些节点中，找到在每条路径中最接近开头的节点:

>>> paths
[]
>>> def dfs(G, s, path):
...     if s not in G or not G[s]:
...             paths.append(path)
...     else:
...             for t in G[s]:
...                     dfs({k:[_t for _t in v if _t!=t] for k,v in G.items()}, t, path+[t])
... 
>>> dfs(G, 2, [])
>>> paths
[[3, 4, 6, 7, 12], [3, 4, 6, 8, 9, 10, 12], [3, 4, 6, 8, 9, 12], [3, 4, 6, 8, 11, 12], [3, 5, 6, 7, 12], [3, 5, 6, 8, 9, 10, 12], [3, 5, 6, 8, 9, 12], [3, 5, 6, 8, 11, 12], [4, 6, 7, 12], [4, 6, 8, 9, 10, 12], [4, 6, 8, 9, 12], [4, 6, 8, 11, 12]]
>>> for path in paths: print(path)
... 
[3, 4, 6, 7, 12]
[3, 4, 6, 8, 9, 10, 12]
[3, 4, 6, 8, 9, 12]
[3, 4, 6, 8, 11, 12]
[3, 5, 6, 7, 12]
[3, 5, 6, 8, 9, 10, 12]
[3, 5, 6, 8, 9, 12]
[3, 5, 6, 8, 11, 12]
[4, 6, 7, 12]
[4, 6, 8, 9, 10, 12]
[4, 6, 8, 9, 12]
[4, 6, 8, 11, 12]
>>> nodes = [set(L) for L in paths]
>>> commons = functools.reduce(set.intersection, nodes)
>>> commons
{12, 6}
>>> min(commons, key=lambda v: max(L.index(v) for L in paths))
6

现在，请注意 6 如何在某些路径中显示在索引 2 处，而在其他一些路径中显示在索引 1 处。如果有一个节点(比如 x)出现在路径中的索引 1 处，其中 6 出现在索引 2 处，而在索引 2 处，其中 6 出现在索引 1 处，那么，这将是平局，该算法会随意打破。根据您的需要，您可能想要定义如何更好地处理这种情况