Skip to main content
 首页 » 编程设计

python之可以确定给定的节点是否将始终在有向图中被访问

2024年11月24日10bonelee

我正在处理一个问题,我有一堆有向图,每个有向图都有一个源/汇,边是概率连接(尽管 90% 的节点只有 1 个输入和 1 个输出)。每个图中还有一个关键节点,我想确定是否有任何方法可以绕过该节​​点来遍历该图。理想情况下,我还想枚举绕过该节点的具体路径。我已经能够将示例图导入 NetworkX并且可以毫无困难地运行图表上的一些功能,但我不确定我正在寻找的是否是一个常见的请求,我只是不知道在帮助文件中找到它的正确术语,或者如果这是我需要手动编码的东西。我也愿意接受替代工具或方法。

请您参考如下方法:

首先,您可能需要某种方法来量化关键节点。为此,您可以使用某种程度的中心性,可能是您情况下的中介中心性。 Read more here.

接下来,如果您知道要在两个节点之间穿行,则可以将其用作一种伪代码来帮助您到达那里。您还可以遍历所有可能经过的节点对,但这可能需要一段时间。

import NetworkX as nx 
important_nodes=[]#list of important nodes     
paths = nx.all_simple_paths(G, source, target) 
paths=list(paths) 
#This is pseudocode, next four lines could be done with list comprehension 
exclusive_paths=[] 
for path in paths: 
    if important_nodes not in path: 
        exclusive_paths.append(path) 

阅读有关 all_simple_paths 的更多信息 here .

列表理解可能看起来像这样

exclusive_paths=[x for x in paths if important_nodes not in x]