Python: how to compute the Euclidean distance distribution of a regular network?

Question

I have an NxN regular network, each node of which has an (X,Y) set of coordinates. The nodes are separated by the unit. The network looks like this:

(0,0) (1,0) (2,0)
(0,1) (1,1) (2,1)
(0,2) (1,2) (2,2)

I want to be able to compute the Euclidean distance from each node to all the others. Example:

#Euclidean distances from node (0,0):
0          sqrt(1)     sqrt(4)
sqrt(1)    sqrt(2)     sqrt(5)
sqrt(4)    sqrt(5)     sqrt(8) 

Then, I want to draw the distance distribution, which tells me with which frequency a given distance has a certain value. I want then to turn the graph into a log-log plot.

This is my attempt:

import networkx as nx
from networkx import *
import matplotlib.pyplot as plt

#Creating the regular network    
N=10 #This can vary
G=nx.grid_2d_graph(N,N)
pos = dict( (n, n) for n in G.nodes() )
labels = dict( ((i, j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds.sort()
vals.sort()
pos2=dict(zip(vals,inds)) #Dict storing the node coordinates
nx.draw_networkx(G, pos=pos2, with_labels=False, node_size = 15)

#Computing the edge length distribution
def plot_edge_length_distribution(): #Euclidean distances from all nodes
lengths={}
for k, item in pos2:
    for t, elements in pos2:
        if k==t:
            lengths[k]=0
        else:
            lengths[k]=((pos2[t][2]-pos2[k][2])**2)+((pos2[t][1]-pos2[k][1])**2) #The square distance (it's ok to leave it like this)
items=sorted(lengths.items())
fig=plt.figure()
ax=fig.add_subplot(111)
ax.plot([k for (k,v) in items],[v for (k,v) in items],'ks-')
ax.set_xscale("log")
ax.set_yscale("log")
title_string=('Edge Length Distribution')
subtitle_string=('Lattice Network | '+str(N)+'x'+str(N)+' nodes') 
plt.suptitle(title_string, y=0.99, fontsize=17)
plt.title(subtitle_string, fontsize=9)
plt.xlabel('Log l')
plt.ylabel('Log p(l)')
ax.grid(True,which="both")
plt.show()

plot_edge_length_distribution()

EDIT

When running, this script throws out the error: TypeError: 'int' object is not iterable, pointing at the line where I wrote for k, item in pos2:. Where is it that I go wrong?

Answer 1

The function scipy.spatial.distance.pdist does this about as efficiently as can be.

Consider the following:

from scipy.spatial import distance
import numpy as np

coords = [np.array(list(c)) for c in [(0,0),(1,0), (2,0)]]
>>> distance.pdist(coords)
array([ 1.,  2.,  1.])

The function returns the upper-right part of the distance matrix - the diagonals are 0, and the lower-left part can be obtained from the transpose.

E.g., the above corresponds to

0 1 2
1 0 1
2 1 0

with

• the 0 diagonal and everything to its lower-left removed.

• the upper-right "flattened" to [1, 2, 1].

It is not difficult to reconstruct the distances from the flattened result.