# Extracting an adjaceny matrix containing haversine distance from points on map

I am extracting 10 lat/long points from Google Maps and placing these into a text file. The program should be able to read in the text file, calculate the haversine distance between each point, and store in an adjacency matrix. The adjacency matrix will eventually be fed to a 2-opt algorithm, which is outside the scope of the code I am about to present.

The following code is functional, but extremely inefficient. If I had 1000 points instead of 10, the adjacency matrix would need 1000 x 1000 iterations to be filled. Can this be optimized?

import csv
from haversine import haversine
import matplotlib.pyplot as plt
import numpy as np

with open(file_name, 'r') as f_input:
csv_input = csv.reader(f_input, delimiter=' ', skipinitialspace=True, )
long = []
lat = []
for col in csv_input:
x = float(col)  # converting to float
y = float(col)
long.append(x)
lat.append(y)

return long, lat

def display_points(long, lat):
plt.figure()
plt.ylabel('longitude')
plt.xlabel('latitude')
plt.title('longitude vs latitude')
plt.scatter(long, lat)
plt.show()

def main():

points = []
for i in range(len(lat)):
coords = tuple([lat[i], long[i]])  # converting to tuple to be able to perform haverine calc.
points.append(coords)

hav = []
for i in range(len(lat)):
for j in range(len(long)):
hav.append(haversine(points[i], points[j]))

np.asarray(hav)
adj_matrix = np.reshape(hav, (10, 10))  # reshaping to 10 x 10 matrix

display_points(long, lat)

main()


Sample Input:

35.905333, 14.471970
35.896389, 14.477780
35.901281, 14.518173
35.860491, 14.572245
35.807607, 14.535320
35.832267, 14.455894
35.882414, 14.373217
35.983794, 14.336096
35.974463, 14.351006
35.930951, 14.401137


Sample Output:

[[ 0.          1.15959635  5.15603243 12.15003864 12.66090817  8.06760374
11.25481465 17.31108648 15.37358741  8.34541481]
[ 1.15959635  0.          4.52227294 11.19223786 11.50131214  7.32033758
11.72388583 18.35259685 16.41378987  9.29953014]
[ 5.15603243  4.52227294  0.          7.44480948 10.26177912 10.15688933
16.24592213 22.1101544  20.18967731 13.40020548]
[12.15003864 11.19223786  7.44480948  0.          7.01813758 13.28961044
22.25645098 29.42422794 27.49154954 20.48281039]
[12.66090817 11.50131214 10.26177912  7.01813758  0.          9.22215871
19.74293886 29.16680205 27.25540014 19.97465594]
[ 8.06760374  7.32033758 10.15688933 13.28961044  9.22215871  0.
10.66219491 21.06632671 19.24994647 12.24773666]
[11.25481465 11.72388583 16.24592213 22.25645098 19.74293886 10.66219491
0.         11.67502344 10.21846781  6.08016463]
[17.31108648 18.35259685 22.1101544  29.42422794 29.16680205 21.06632671
11.67502344  0.          1.93885474  9.20353461]
[15.37358741 16.41378987 20.18967731 27.49154954 27.25540014 19.24994647
10.21846781  1.93885474  0.          7.28280909]
[ 8.34541481  9.29953014 13.40020548 20.48281039 19.97465594 12.24773666
6.08016463  9.20353461  7.28280909  0.        ]]


Plot: • Welcome to Code Review and congratulations on writing a decent question on your first try. – Mast Nov 12 '18 at 9:10
• This is a great first question, I hope you get some good feedback. – esote Nov 12 '18 at 14:54
• If you want your code to be error prone, you actually want it so it is easy to have bugs. You maybe meant error proof? – Graipher Nov 12 '18 at 15:55
• Well spotted @Graipher! Seems like I want suggestions on how to actually include bugs in my code. Thanks for pointing out, will edit. – Rrz0 Nov 12 '18 at 16:11

More than half of your code is being used to convert from one data format to another (from two lat and long list to tuples and then from a list of lists to an array).

The easiest to understand version would be to use numpy.loadtxt:

def read_two_column_file(file_name):


This is then a 2D numpy.array. However, this is actually a lot slower than it could be, so you could also use pandas.read_csv instead:

import pandas as pd



Which one is faster depends on the size of your file.

Now we need to modify the display_points function to work with this new data format:

def display_points(points):
plt.figure()
plt.ylabel('longitude')
plt.xlabel('latitude')
plt.title('longitude vs latitude')
plt.scatter(points[:, 0], points[:, 1])
plt.show()


Now for the actual calculation. First, you can use itertools.combinations_with_replacement to get all pairs of points. Then you can insert them directly into the correct row of an array:

from itertools import combinations_with_replacement

def main():

for i, (point1, point2) in enumerate(combinations_with_replacement(points, 2)):

This can probably be further improved by using numpy.meshgrid to get the combinations of points and using a vectorized version of the haversine function.
• For some reason I'm getting an error on Line 28 being: adj_matrix[i] = haversine(point1, point2). ValueError: not enough values to unpack (expected 2, got 1) I haven't yet found what's wrong. – Rrz0 Nov 12 '18 at 18:36
• @Rrz0: I just tested it again, it works on my machine with Python 3.6.3. Did you maybe not replace the read_two_column_file function? – Graipher Nov 13 '18 at 13:22