Paper, Order, or Assignment Requirements

This lab will process a dataset containing the direct connection distances between cities
in Montana. (Each connection does not necessarily exist in our current road network.)
Assume that some devastating earthquakes occurred and the direct road connections between
some cities were broken, say between Bozeman and Billings. Assume also that all
other tools like GPS do not work anymore and all we have is this file:
http://www.cs.montana.edu/bhz/classes/spring-2016/csci305/LAB2/city1.txt
You need to first import this file and build a data structure to store it. Then you need
to build a tool to facilitate the reconstruction of Montana’s Road Network. Your Python
code must support the following queries:
Task 1. Number of cities directly connected to a query city.
For instance, if you input: Bozeman, the result should be 23.
Task 2. Given two query cities, return YES/NO for whether there is a direct
connection (edge) between them.
For instance, if you input: Bozeman, Billings, the result should be NO.
Task 3. Given two query cities and an integer d, return YES/NO for whether
there is a k-hop connection, k ≤ d, between them; if YES, print one solution
out, to gether with the total distance of the d hops.
We say that hv1,v2,…,vd+1i forms a d-hop connection between v1 and vd+1 if (vi
,vi+1)
is a direct link for i = 1,…,d (i.e., between two cities vi and vi+1 there is a non-zero distance
in city.txt).
1
Task 4. Given two query cities, return YES/NO for whether there is a connection
(not necessarily direct) between them; if YES, print one solution out,
together with the actual total distance of the connection.