[Solved] DAT171 Assignment 1-reading in data from a text file and using the NumPy, SciPy, and Matplotlib

The goal of the first computer assignment is to get you comfortable in reading in data from a text file and using the NumPy, SciPy, and Matplotlib libraries. The problem to solve is to construct a graph of neighboring cities and to find the shortest path between two given cities, through the neighboring cities. _{See the example figure at the} end of this document.

Three files are supplied to test your program, with one very small file _{SampleCoordinates.txt} suitable for testing your functions. In task 3 you need a radius that limits what is considered neighboring cities, in task 7 you need to enter start and end cities. You can find these values in the table below (the city no. corresponds to the line in the respective city file).

For convenience, the task is divided into steps as listed below. Please stick to the given function prototypes, as it makes correcting reports much easier (you are of course allowed to write more sub-functions if you want). _Functions must be documented using PyDoc.

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 isnt 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 _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 _{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}
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 _txt: