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

Question

我有一个创建图形的简单代码，G in networkx。

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, 1: 2, 4: 2}。所以length=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))，它需要大约 74 毫秒。另一个选项（在 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

Answer 2

对上面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() returns 基于图的内部表示的任意方式的节点，它可能将节点存储在未排序的类集合结构中。

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

How to find a node with a shortest path of length equal to some number in networkx python?

python

nodes

networkx