时间戳

首页 > 解决方案 > 可以确定是否总是在有向图中访问给定节点？

python - 可以确定是否总是在有向图中访问给定节点？

问题描述

我正在解决一个问题，我有一堆有向图，每个有一个源/汇，边是概率连接（尽管 90% 的节点只有 1 个输入和 1 个输出）。每个图中还有一个关键节点，我想确定是否有任何方法可以遍历绕过该节点的图。理想情况下，我还想列举绕过该节点的特定路径。我已经能够将示例图导入NetworkX，并且可以毫无困难地在图上运行一些函数，但我不确定我正在寻找的是否是一个常见的请求，我只是不知道在帮助文件中找到正确的术语，或者如果这是我需要手动编码的东西。我也对替代工具或方法持开放态度。

标签： pythonnetworkxgraph-theory

解决方案

首先，您可能需要某种方法来量化关键节点。为此，您可以使用某种中心性度量，在您的情况下可能是中介中心性。在这里阅读更多。

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

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 的更多信息。

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

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

推荐阅读