使用 Networkx 或其他 Python 框架自动计算图中节点之间的距离

Question

假设我们有一个由 networkx 库创建的具有节点 A、B、C 的完整图 G。

每个节点都有一个坐标属性，如{x: 2, y: 4}。目前，边权重为1，但它们应该是节点之间的欧氏距离。我可以用 for 循环计算它们，但效率极低。

所以我的问题是如何有效地计算边缘权重？

注意：我找到了 this 但这是一个老问题。

编辑：我按如下方式创建了我的网络：

# Get a complete graph
rag = nx.complete_graph(L)

if L > 0:
    for i, node in enumerate(nodes):

        x, y = get_coord() # This function cant be changed

        rag.nodes[i]["x"] = x
        rag.nodes[i]["y"] = y

Answer 1

如果你事先有数据，我们可以使用numpy and/or pandas先批量计算距离，然后将数据加载到图表中。

比如说我们可以首先构造一个n×2-矩阵：

import numpy as np

A = np.array([list(get_coord()) for _ in range(L)])

然后我们可以使用scipy来计算距离的二维矩阵，例如：

from scipy.spatial.distance import pdist, squareform

B = squareform(pdist(A))

如果 A 是：

>>> A
array([[ 0.16401235, -0.60536247],
       [ 0.19705099,  1.74907373],
       [ 1.13078545,  2.03750256],
       [ 0.52009543,  0.25292921],
       [-0.8018697 , -1.45384157],
       [-1.37731085,  0.20679761],
       [-1.52384856,  0.14468123],
       [-0.12788698,  0.22348265],
       [-0.27158565,  0.21804304],
       [-0.03256846, -2.85381269]])

那么 B 将是：

>>> B
array([[ 0.        ,  2.354668  ,  2.81414033,  0.92922536,  1.28563016,
         1.74220584,  1.84700839,  0.8787431 ,  0.93152683,  2.25702734],
       [ 2.354668  ,  0.        ,  0.97726722,  1.53062279,  3.35507213,
         2.20391262,  2.35277933,  1.5598118 ,  1.60114811,  4.60861026],
       [ 2.81414033,  0.97726722,  0.        ,  1.88617187,  3.99056885,
         3.10516145,  3.26034573,  2.20792312,  2.29718907,  5.02775867],
       [ 0.92922536,  1.53062279,  1.88617187,  0.        ,  2.15885579,
         1.897967  ,  2.04680841,  0.64865114,  0.79244935,  3.15551623],
       [ 1.28563016,  3.35507213,  3.99056885,  2.15885579,  0.        ,
         1.75751388,  1.7540036 ,  1.80766956,  1.75396674,  1.59741777],
       [ 1.74220584,  2.20391262,  3.10516145,  1.897967  ,  1.75751388,
         0.        ,  0.1591595 ,  1.24953527,  1.10578239,  3.34300278],
       [ 1.84700839,  2.35277933,  3.26034573,  2.04680841,  1.7540036 ,
         0.1591595 ,  0.        ,  1.39818396,  1.25440996,  3.34886281],
       [ 0.8787431 ,  1.5598118 ,  2.20792312,  0.64865114,  1.80766956,
         1.24953527,  1.39818396,  0.        ,  0.14380159,  3.07877122],
       [ 0.93152683,  1.60114811,  2.29718907,  0.79244935,  1.75396674,
         1.10578239,  1.25440996,  0.14380159,  0.        ,  3.08114051],
       [ 2.25702734,  4.60861026,  5.02775867,  3.15551623,  1.59741777,
         3.34300278,  3.34886281,  3.07877122,  3.08114051,  0.        ]])

现在我们可以根据该矩阵构建一个图：

G = nx.from_numpy_matrix(B)

现在我们看到权重匹配：

>>> G.get_edge_data(2,5)
{'weight': 3.105161451820312}

使用 Networkx 或其他 Python 框架自动计算图中节点之间的距离

Automatically calculate distance between nodes in a Graph by using Networkx or other Python Framework

python

graph-theory

graph

networkx