首页 文章

使用Networkx或其他Python Framework自动计算Graph中节点之间的距离

提问于
浏览 次
2

假设我们有一个完整的图G，其中包含由networkx库创建的节点A，B，C .

每个节点都有一个坐标属性，如{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
python graph networkx graph-theory

1 回答

  • 1

    如果您预先拥有数据，我们可以使用 numpy 和/或 pandas 来首先计算批量距离，然后将数据加载到图表中 .

    比如我们可以先用以下方法构造一个n×2矩阵：

    import numpy as np

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

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

    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}
    回复于

相关问题