CODEWITHSUNDEEP
pythonmatrixscipynetworkx
user136819
user136819

Reputation: 239

Python Scipy and Networkx: How to compute a Euclidean distance matrix?

I am using Python Networkx to build a graph and I have the following node positions as an example (positions.txt): 

1 21.5 23
2 24.5 20
3 19.5 19
4 22.5 15
5 24.5 12

Node ID, X, Y. I read the file using Pandas and set the positions as node attributes in Networkx. Nodes are added using add_edge(id1, id2, weight) method in a for loop (with no self edges). So far, I have assumed that all the nodes are connected to each other by default and have not taken parameters such as Radius or Distance of nodes into consideration.
Now, I want to compute a Euclidean radius or distance matrix between the nodes using these node positions, and with this matrix I want to be able to print the neighbours of a node that fall within a given radius n and save the file as a csv matrix file. A friend suggested that I use scipy's euclidean method but I have no clue how to use this to build the matrix, hence I have no starting point. I tried using ego_graph() but it did not give me the desired results.
Any help is appreciated in solving my problem.
Thanks in advance. (Using Ubuntu 14.04 32-bit VM and Python 2.7)

Upvotes: 1

Views: 1606

Answers (1)

Reti43
Reti43

Reputation: 9797

You can use scipy.spatial.distance.cdist() to generate your distance matrix given a list of coordinates.

Obviously a numpy array is always 0-indexed and if your nodes have random numbers, you want to keep a list of them to know which row/column of your matrix corresponds to which pair.

What you do after that should be trivial, but I'll give an example based on your description. For each node, print the id of said node and the ids of any neighbouring nodes within your threshold distance.

import numpy as np
from scipy.spatial import distance

def neighbour_nodes_of(node, dist_matrix, distance):
    row = dist_matrix[node]
    return np.where((row <= distance) * (row > 0))[0]

ids = [1, 2, 3, 4, 5]
coords = [(21.5, 23),
          (24.5, 20),
          (19.5, 19),
          (22.5, 15),
          (24.5, 12),
          ]
threshold = 8.

dist_matrix = distance.cdist(coords, coords)

# this is something you can write to a file instead
for i, node_id in enumerate(ids):
    neighbours = neighbour_nodes_of(i, dist_matrix, threshold)
    neighbour_ids = [ids[n] for n in neighbours]
    print([node_id] + neighbour_ids)

Upvotes: 3

Related Questions