如何在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找到。最短路径（G，1）和nx。分别为最短路径（G，2）。

或者，例如，如果我使用nx。最短路径长度（G，source=2），然后得到{2:0，3:1，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

对上述willcrack回复中的代码稍作修改（注意添加了对sorted的调用）：

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（）根据图的内部表示以任意方式返回节点，该图可能将节点存储在未排序的类似集合的结构中。

Answer 2

对于您提供的图表：

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)

将打印节点距离等于nx.diameter（G）的目标

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

相比之下，对于200节点图（nx.barabasi\u-albert\u图（200，2，seed=1）），直径计算在循环之外，需要约74ms。另一个选项（在for循环内进行直径计算）采用。。。嗯，它仍在运行：'）但我想说这将需要太长时间。

此外，不只是打印目标，而是打印开始和结束节点以提高可读性：

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