CODEWITHSUNDEEP
pythonnumpy
nycynik
nycynik

Reputation: 7541

Get list of connected nodes ordered by shortest distance

I have a numpy 2D array that represents distances between nodes on a graph. I want to, for a single node, get a list of connected nodes ordered by shortest distance, how can I do that?

# create some data
distances = np.array([[0., 1., 2., 3.], [1.,0.,5.,7.], [2.,5.,0.,4.], [3.,7.,4.,0.]]) 
# get just the node I care about, 1
closest_to_node = distances[:,1]
print (closest_to_node)
# outputs [ 1.  0.  5.  7.]

I would like to order closest_to_node by distance, but my only way of knowing what node it relates to is the order in the array.

I would like a list that was [1,0,2,3] or even better since item 1 (value 0) is meaningless in this case [1,2,3]

Upvotes: 0

Views: 190

Answers (1)

Divakar
Divakar

Reputation: 221654

IIUC you could do -

((distances - closest_to_node[:,None])**2).sum(0).argsort()

Alernatively, with Scipy's cdist -

from scipy.spatial.distance import cdist

idx = cdist(distances, closest_to_node[None]).argsort(0).ravel()

Output for given sample -

In [147]: ((distances - closest_to_node[:,None])**2).sum(0).argsort()
Out[147]: array([1, 0, 2, 3])

In [148]: cdist(distances, closest_to_node[None]).argsort(0).ravel()
Out[148]: array([1, 0, 2, 3])

Upvotes: 2

Related Questions