CODEWITHSUNDEEP
pythongraphnetworkxgraph-theory
cagatayodabasi
cagatayodabasi

Reputation: 762

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

Let's say we have a complete graph G with nodes A, B, C which is created by networkx library.

Each node has a coordinate attribute like {x: 2, y: 4}. Currently, the edge weights are 1, but they should be the Euclidean distance between nodes. I can calculate them with for loops but it is extremely inefficient.

So my question is how can I calculate the edge weights in an efficient manner?

Note: I found this but it is an old question.

Edit: I created my network as follows: 

# 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

Upvotes: 2

Views: 2205

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476659

If you have the data in advance, we can use numpy and/or pandas to first calculate the distance in bulk, and then load the data into a graph.

Say for instance we can first construct an n×2-matrix with:

import numpy as np

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

We then can use scipy to calcuate a 2d matrix of distances, for example:

from scipy.spatial.distance import pdist, squareform

B = squareform(pdist(A))

If for instance A is:

>>> 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]])

then B will be:

>>> 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.        ]])

And now we can construct a graph based on that matrix:

G = nx.from_numpy_matrix(B)

now we see that the weights match:

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

Upvotes: 3

Related Questions