Skip to main content
 首页 » 编程设计

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

2025年01月19日10jillzhang

假设我们有一个由 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 

请您参考如下方法:

如果您事先有数据,我们可以使用numpy 和/或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}