DAT171-Assignment 1 Solved

1.      Create the function read_coordinate_file(filename) that reads the given coordinate file and parses the results into an array of coordinates. The coordinates are expressed in the format: {a, b} where a is the latitude and b is the longitude (in degrees). Convert these using the Mercator projection to obtain the coordinates in xy-format:

                                                                                       πb                              π                πa 

                                                                               x = R180,          y = Rln tan        4 + 360

The radii in the table are given for the normalized R = 1. (Measuring distances on a Mercator projection isn’t very accurate, but will suffice for this task.)

Hints: Use the function split for the strings. Convert a string to a number with the function float. Make sure to use a NumPy array to store the data for performance (i.e. the function must return a 2D NumPy array).

2.      Create the function plot_points(coord_list) that plots the data points read from the file. Hints: Remember to call plt.show() after plot commands are finished.

3.      Create the function construct_graph_connections(coord_list, radius) that computes all the connections between all the points in coord_list that are within the radius given. Simply check each coordinate against all other coordinates to see if they are within the given radius using two nested loops. The output should contain the 2 indices in one NumPy array and the distance in another. Hints: Have a look at the Python method enumerate.

4.      Create the function construct_graph(indices, distance, N) that constructs a sparse graph. The graph should be represented as a compressed sparse row matrix (csr_matrix in scipy.sparse). Each element at index [i, j] in the matrix should be the distance between city i and j. Construct the matrix with csr_matrix((data, ij), shape=(M, N)). Hints: You need to provide a size N as input to this function. What

is N? The SciPy manual contains examples on how to create the matrices: https://docs.scipy.org/doc/scipy/ref erence/generated/scipy.sparse.csr_matrix.html

5.      Extend plot_points(coord_list, indices) to also include the graph connections from task 3. Hints: Use

Matplotlib:s LineCollection instead of plotting the lines individually, since it is much faster.

6.      Create the function find_shortest_paths(graph, start) that finds the shortest paths from start to all other cities, using the functions in scipy.sparse.csgraph. Please make sure you properly document this function! Hints: The function shortest_path finds the shortest path, it lets the user input what indices (starting nodes) the path should be computed for. This saves significant computational effort! https://docs.scipy.org/doc /scipy/reference/sparse.csgraph.html

7.      One of the outputs from the shortest path functions in SciPy is a “predecessor matrix”. The columns represent the predecessor when taking the shortest path to the given column index (this seems complicated, but is actually a clever way to store the shortest paths to every possible end node). Write a function compute_path(predecessor_matrix, start_node, end_node) that takes a predecessor matrix, start and end nodes, and converts it to a sequence of nodes that represent the shortest path. Hints: The

file SampleCoordinatex.txt should generate the sequence [0, 4, 3, 5], the total distance for this path

is 0.16446989717973517.

8.      Extend plot_points(coord_list, indices, path) to also include the shortest path. Make the shortest path more visible by making it stand out (thicker line width and a noticeable color for example).

9.      Record the total time for each of the functions (see the table below for reference). Which routine consumes the most time? Hints: Use time.time()

10.   Create the function construct_fast_graph_connections(coord_list, radius) that computes all the connections between all the points in coord_list that are within the radius given. This time, use the cKDTree from SciPy to find the closest coordinates quickly. (The cKDTree is an optimized version of the KDTree.) Note!

You must be able to swap construct_graph_connections with construct_fast_graph_connections in your code (without any other alterations)! Hints: Instead of checking a coordinate against all the other coordinates,

we can filter the number of points by for example using the method query_ball_points(coord, radius) on the KDTree.

For reference, here is the expected output for HungaryCities.txt:

Shortest path from 311 to 702 is: [311, 19, 460, 629, 269, 236, 781, 50, 193, 571, 624, 402, 370,

153, 262, 554, 126, 251, 368, 221, 827, 300, 648, 253, 836, 73, 35, 219, 503, 789, 200, 702]

Total distance: 0.1114486118821533

 

Additional instructions

Besides the general General instructions for computer assignments please consider the items below for Computer Assignment 1:

1.   Reading the input file:

•     Process each line as it is read.

•     Use strip, split, and so on for processing each line, not indexing or similar.

•     Remember to close files.

2.   As part of the report, the resulting pictures must be handed in. Make sure the pictures have a correct aspect ratio.

3.   The output of the program must include the total distance and the shortest path found.

4.   Timing information for the major routines must be provided. On a quite old machine (Intel Core i7-2600) the following results (to one digit precision) can be used as a hint on the expected results for GermanyCities.txt:

function
time (s)
read_coordinate_file
0.03
construct_graph_connections
70
construct_graph
0.002
Task 6+7
0.007
plot_points (from task 8, excluding plt.show)
2
construct_fast_graph_connections
0.3
Running the entire program using the fast version, excluding plotting
1