如何在networkx python中找到长度等于某个数字的最短路径的节点

Question

我有一个简单的代码来创建一个图，即networkx中的G。

import networkx as nx
import matplotlib.pyplot as plt
%matplotlib notebook
G = nx.DiGraph()
G.add_edge(1,2); G.add_edge(1,4)
G.add_edge(3,1); G.add_edge(3,2)
G.add_edge(3,4); G.add_edge(2,3)
G.add_edge(4,3)

我想找到"；G中的该节点通过长度等于G〃直径的最短路径连接到其它节点；。

这些组合中有两个，[1,3]和[2,4]，它们可以分别由nx.shortest_path(G，1(和nx.shortest _path(G，2(找到。

或者例如，如果我使用nx.shortest_path_length(G，source=2(，那么我得到{2:0，3:1,2,4:2}。因此长度=2是从节点2到节点4，这是可以的

现在，我试图将它推广到所有节点，看看我是否能找到目标节点。

for node in G.nodes():
target = [k for k,v in nx.shortest_path_length(G, node).items() if v == nx.diameter(G)]
print(target)

我得到一个奇怪的结果：

[3]
[1, 4]
[1, 2]
[]

有人能解释一下这个结果意味着什么吗？因为我正试图用这种方法来解决一个更大的问题。

Answer 1

对于您提供的图形：

G = nx.DiGraph()
G.add_edge(1,2); G.add_edge(1,4)
G.add_edge(3,1); G.add_edge(3,2)
G.add_edge(3,4); G.add_edge(2,3)
G.add_edge(4,3)

以下内容：

for node in G.nodes():
target = [k for k,v in nx.shortest_path_length(G, node).items() if v == nx.diameter(G)]
print(target)

将打印node距离等于nx.diameter(G)的目标

我建议不要计算for环路内部的直径，因为这可能会非常昂贵。

相比之下，对于直径计算在for循环之外的200节点图(nx.barabasi_albert_graph(200, 2, seed=1)(，大约需要74ms。另一个选项(在for循环中进行直径计算(需要。。。好吧，它仍然在运行：´(但我认为这将花费waaay太长时间。

此外，为了可读性，不只是目标打印开始和结束节点：

diameter = nx.diameter(G)
for node in G.nodes():
start_end_nodes = [(node, k) for k,v in nx.shortest_path_length(G, node).items() if v == diameter]
print(start_end_nodes)

屈服：

[(1, 3)]          # the path from 1 to 3 has lenght 2 = nx.diameter(G)
[(2, 1), (2, 4)]  # the paths from 2 to 1 and 2 to 4 have lenght 2
[(4, 1), (4, 2)]  # the paths from 4 to 1 and 4 to 2 have lenght 2
[]                # there is no path starting at 3 that has lenght 2

Answer 2

从上面willcrack的回复中对代码进行了轻微修改(注意添加了对排序的调用(：

diameter = nx.diameter(G)
for node in sorted(G.nodes()):
start_end_nodes = sorted([(node, k) for k,v in nx.shortest_path_length(G, node).items()
if v == diameter])
print(node, ":", start_end_nodes)

将产生：

1 : [(1, 3)]
2 : [(2, 1), (2, 4)]
3 : []
4 : [(4, 1), (4, 2)]

重点是G.nodes((基于图的内部表示以任意方式返回节点，该图可能将节点存储在未排序的类集结构中。