我正在分析一个函数的控制流图,它基本上是将传入数据映射到传出数据。大多数街区都是这样的:
if (input_variable == SPECIFIC_CONSTANT) {
output_variable = TRUE;
}
else {
output_variable = FALSE;
}
这类代码的典型控制流图如下所示
^{pr2}$其中,3
和4
的执行受input_variable
的值限制,但是5
是独立的。在
给定一个有向图和一个起始节点,如何找到最近的节点,使起始节点的任何路径都通过这个节点?在
示例:给定this graph如何找到从2
开始的6
或从{
我可以反转一个最低的公共祖先算法吗?它是否有效?像
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,但是任何算法都会很受欢迎。我不习惯图论,我想我错过了基本的词汇表来找到我要找的东西。在
谢谢你的帮助!在
虽然不是最有效的解决方案,但以下是一些应该让您开始的方法:
执行DFS,然后计算所有路径(每个路径中存在的节点)的交集。然后,在这些节点中,找到每个路径中最靠近开始的节点:
现在,请注意
6
在某些路径中是如何在索引2处显示的,在其他一些路径中是如何在索引1处显示的。如果有一个节点(比如x)出现在索引1,路径6出现在索引2,索引2出现在索引1,那么,这将是一个平局,这个算法会任意破坏它。根据您的需要,您可能需要定义如何更好地处理这种情况你可以这样做:
对于每个节点,查找其所有祖先和后代的列表。如果大小(祖先)+大小(后代)+1等于网络大小,则它是候选。现在,找到一个至少有一个祖先和最大数量后代的节点。在
祖先和后代的名单很容易计算出来。如果你不确定,请告诉我,我会扩展我的答案。在
读了你提出的所有解决方案,我想出了一个主意。我给我的第一个节点赋值为1。递归地,所有的子代都会得到相等的分数。反过来,他们把这笔钱向下分配。如果一个孩子总共得到1(起始量),那么它就是“连接点”。这是我的实现(公开征求意见!!)。在
我希望BFS结构可以限制访问的节点数量。在
相关问题 更多 >
编程相关推荐