在python Networkx中，如何通过避免某些已定义的节点来获得从源到目标的路径?

Question

我在python中使用Networkx库创建了一个示例无向图，其中包含以下节点。nodes_connected =[(4 1),(2、5)(5、1),(4,2)(5、6)]

我可以使用nx.all_simple_paths(...),ie找到从节点6到4的所有路径All_paths = [[6,5,2,4]， [6,5,1,4]]

，但现在我有一个要求，得到所有的路径，这样我有避免路径包含节点1。所以基本上，当它到达节点1时，我必须阻塞路径，这样我的路径就不应该包含节点1，即使有可能存在一条路径通过它。也就是说，所有的路径现在都应该是[[6,5,2,4]].

我能得到所有不包含特定节点的路径吗?如果是，如何使用Networkx实现它?

感谢

Answer 1

在不包含1的节点上创建子图，然后在子图中查找路径。最近版本的networkx相对有效地创建子图。它们实际上并没有创建一个新的图，而是仅基于包含的节点创建原始图的"视图"。所以你的代码看起来像:

G = nx.Graph()
G.add_edges_from([(4,1),(2,5),(5,1), (4,2), (5,6)])
nodelist = list(G.nodes())
nodelist.remove(1)
H = nx.subgraph(G)
print(nx.all_simple_paths(H,6,4))
> [[6, 5, 2, 4]]

对视图要小心:

G.remove_node(5)
print(H.nodes())
> [4, 2, 6]

修改G，会影响H。