Python代写 | Assignment 09: Graph Searching [cse30s21]

本次代写主要为图搜索相关的assignment

Google Maps driving directions between the first 5 locations in the vertex_locations.txt file
Background
Quoth the arbiter of all human information:
The international E-road network is a numbering system for roads in Europe developed by the United Nations Economic Commission for Europe (UNECE). The network is numbered from
E1 up and its roads cross national borders. It also reaches Central Asian countries like Kyrgyzstan, since they are members of the UNECE.
Lovro Šubelj at the University of Ljubljana compiled a graph of significant parts of the e-road network; nodes represent cities and an edge between two nodes denotes that they are connected by an E-
road.
I have re-assembled Šubelj’s dataset in a slightly more friendly manner, and added geographic latitude/longitude coordinates for each city (according to Google’s Geocoding API). My version of the
dataset consists of three files on our server:
/srv/datasets/e-roads/vertex_names.txt (also available via HTTP) lists the name of each
city, along with a unique  integer ID (separated by a tab character) for each city. Here are the first 5
lines:
1 Greenock
2 Glasgow
3 Preston
4 Birmingham
5 Southampton
/srv/datasets/e-roads/vertex_locations.txt (also available via HTTP) lists a latitude and longitude coordinate for each city. Here are the first 5 lines:
1 55.95647599999999 -4.771983
2 55.864237 -4.251806
3 53.763201 -2.70309
4 52.48624299999999 -1.890401
5 50.90970040000001 -1.4043509
Note that requesting Google Maps directions between those coordinates will demonstrate that these locations represent Greenock, Glasgow, Preston, Birmingham, and Southampton:
https://www.google.com/maps/dir/55.956,-4.772/55.864,-4.252/53.763,-2.703/52.486,-1.890/50.910,-1.404
/srv/datasets/e-roads/network.txt (also available via HTTP) lists the edges in the graph as tuples of city ID numbers. Consider these edges to be bidirectional. Here are the first 5 lines:
1 2
2 3
2 17
3 4
4 5