5
\$\begingroup\$

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


def read_two_column_file(file_name):
    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[0])  # converting to float
            y = float(col[1])
            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():
    long, lat = read_two_column_file('latlong.txt')

    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
    print(adj_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:

enter image description here

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to Code Review and congratulations on writing a decent question on your first try. \$\endgroup\$ Commented Nov 12, 2018 at 9:10
  • 2
    \$\begingroup\$ This is a great first question, I hope you get some good feedback. \$\endgroup\$ Commented Nov 12, 2018 at 14:54
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ Commented Nov 12, 2018 at 15:55
  • 1
    \$\begingroup\$ Well spotted @Graipher! Seems like I want suggestions on how to actually include bugs in my code. Thanks for pointing out, will edit. \$\endgroup\$ Commented Nov 12, 2018 at 16:11

1 Answer 1

Reset to default
2
\$\begingroup\$

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):
    return np.loadtxt(file_name, delimiter=", ")

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

def read_two_column_file(file_name):
    return pd.read_csv(file_name, header=None).values

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():

    points = read_two_column_file(file_name)

    adj_matrix = np.empty(len(points)**2)
    for i, (point1, point2) in enumerate(combinations_with_replacement(points, 2)):
        adj_matrix[i] = haversine(point1, point2)
    adj_matrix.reshape((len(points), len(points))

    print(adj_matrix)
    display_points(points)

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.

\$\endgroup\$
7
  • \$\begingroup\$ Thanks for the constructive feedback. Will get back after I look into all suggestions and try to implement. \$\endgroup\$ Commented Nov 12, 2018 at 17:51
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Nov 12, 2018 at 18:36
  • \$\begingroup\$ @Rrz0 That sounds odd. Will also investigate when I get home later. \$\endgroup\$ Commented Nov 12, 2018 at 18:43
  • \$\begingroup\$ I suspect tuple unpacking gone wrong, somewhere. \$\endgroup\$ Commented Nov 13, 2018 at 10:29
  • \$\begingroup\$ @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? \$\endgroup\$ Commented Nov 13, 2018 at 13:22

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.