def process_line(line):
""" (str) -> (str, str, number)
Process one line of data from a data file (in the same format as
cities.txt) to extract the first city's name, the second city's name, and the
distance. Return these values in a tuple..
Parameters:
line-- a single line from a data file, in the format specified in the
project handout (first city:second city distance)
Return value:
(first, second, distance), where first is the name of the first city,
second is the name of the second city, and distance is the distance
Side-effects:
None
Examples:
>>> process_line("A:B 3")
('A', 'B', 3)
>>> process_line("some city:B 2")
('some city', 'B', 2)
>>> process_line("A:other city 5")
('A', 'other city', 5)
"""
def get_distances(lines):
""" Read distances between cities from the lines read from a data file,
which is in the same format as cities.txt, and
return a dictionary structure that contains all of this information.
Parameters:
lines -- a list of lines read in from a data file in the same format as
cities.txt
Return value:
a dictionary whose keys are city names and whose values are lists of
pairs of the form (city_name, distance).
The cities must be sorted in alphabetical order. (Note:
sorted([("B", 3), ("A", 2)]) returns [('A', 2), ('B', 3)]
Side-effects:
None
Examples:
# The second line below violates style guidelines (it is too long) because
# this is required for doctest to work properly.
>>> get_distances(open("cities.txt").readlines()) # assuming the data file from the handout
{'Mexico City': [('San Francisco', 3), ('Toronto', 7)],
'New York': [('Toronto', 3), ('Washington', 2)],
'San Francisco': [('Mexico City', 3), ('Toronto', 6), ('Washington', 5)],
'Toronto': [('Mexico City', 7), ('New York', 3), ('San Francisco', 6)],
'Washington': [('New York', 2), ('San Francisco', 5)]}
"""
pass
def get_closest(unvisited):
""" Returns a tuple from list unvisited that has the shortest distance
(return the first such tuple in case of ties). Assumes unvisited is not
empty.
Parameters:
unvisited-- a list of (city_name, distance) pairs
Return value:
the first tuple in unvisited whose distance is minimum
Side-effects:
None
Examples:
>>> get_closest([('A', 3)])
('A', 3)
>>> get_closest([('A', 3), ('B', 2)])
('B', 2)
>>> get_closest([('A', 3), ('C', 4)])
('A', 3)
>>> get_closest([('A', 3), ('B', 2), ('C', 4), ('D', 2)])
('B', 2)
"""
# Examine every tuple and remember the index of the one with the smallest
# distance so far-- starting with the first tuple.
def find_city(city, city_list):
""" Return the index of the first tuple that contains city in city_list, or
-1 if city does not appear in city_list.
Parameters:
city-- the name of a city to look for (a string)
city_list-- a list of tuples of the form (city_name, distance)
Return value:
the index of the first tuple in city_list that contains city; -1 if no
tuple in city_list contains city
Side-effects:
None
Examples:
>>> find_city('A', [('A', 2)])
0
>>> find_city('A', [('B', 3), ('C', 2)])
-1
>>> find_city('A', [('B', 3), ('C', 2), ('A', 2)])
2
>>> find_city('C', [('B', 3), ('C', 2), ('A', 2), ('C', 4)])
1
"""
def visit_next(visited, unvisited, distances):
""" Move the next closest city from the unvisited list to the visited list.
Update the distances in the unvisited list if a shorter path exists to one
of the unvisited cities, as described in the handout. Assumes that the
unvisited list is non-empty.
Parameters:
visited-- a list of tuples for cities that have been "visited", i.e.,
their minimum distance to the city of origin is known, and their
neighbours already belong to the visited or unvisited list
unvisited-- a list of tuples for cities that have not yet been visited
distances-- a dictionary of direct flight lengths between cities,
such as what is returned by get_distances()
Return value:
None
Side-effects:
- the first city C whose distance is minimum in unvisited is removed
from unvisited and added to visited
- neighbours of C that did not already belong to either list are added
to unvisited (with their distance from C)
- neighbours of C that were already in unvisited have their distance
updated, if going through C leads to a shorter total distance
Examples:
# This needs to be tested much more thoroughly than the few cases below, to
# take into account all the possible situations that could come up.
>>> distances = get_distances(open("cities.txt").readlines())
>>> unvisited = [('Toronto', 0)]
>>> visited = []
>>> visit_next(visited, unvisited, distances)
>>> visited
[('Toronto', 0)]
>>> unvisited
[('New York', 3), ('Mexico City', 7), ('San Francisco', 6)]
>>> visit_next(visited, unvisited, distances)
>>> visited
[('Toronto', 0), ('New York', 3)]
>>> unvisited
[('Mexico City', 7), ('San Francisco', 6), ('Washington', 5)]
>>> visit_next(visited, unvisited, distances)
>>> visited
[('Toronto', 0), ('New York', 3), ('Washington', 5)]
>>> unvisited
[('Mexico City', 7), ('San Francisco', 6)]
"""
# Step 1:
# Find the city to move from the unvisited list to the visited list, and
# move it.
############################################################################
# Step 2:
# Find every neighbour of the that was moved to visited and update each
# one's distance as approrpiate
# Loop through every neighbour:
# For each neighbour, there are three cases to consider:
# ...(a) neighbour is already visited: do nothing
# ...(b) neighbour is already unvisited: update its distance
# ...(c) neighbour is not even unvisited: add it to unvisited
def visit_all(city, distances):
'''Return the list of shortest distances from city city to every city in
the dictionary distances. This is accomplished by repeatedly calling
visit_next inside a while loop.
Arguments:
distances-- a dictionary of direct flight lengths between cities,
such as what is returned by get_distances()
>> distances = get_distances(open("cities.txt").readlines())
>> visit_all('Toronto', distances)
[('Mexico City', 7),
('New York', 3),
('San Francisco', 6),
('Toronto', 0),
('Washington', 5)]
'''
pass
def get_all_cities(distances):
'''Return a list of all the cities that appears in the dictionary
distances, which was returned by get_distances. The cities are to be
sorted in alphabetic order
>> distances = {'Washington': [('New York', 2), ('San Francisco', 5)],
'Toronto': [('New York', 3)]}
>> get_all_cities(distances)
['New York', 'San Francisco', 'Toronto', 'Washington']
'''
def get_all_dists(distances):
'''Return a dictionary all_dists whose keys are cities which appear in
the argument distances
(either as source cities or destination cities) and whose values are the
shortest path distance to every other city (i.e., the values are return
values of visit_all
Arguments:
distances-- a dictionary of direct flight lengths between cities,
such as what is returned by get_distances()
>> distances = get_distances(open("cities.txt").readlines())
>> get_all_dists(distances)
{'Mexico City': [('Mexico City', 0),
('San Francisco', 3),
('Toronto', 7),
('Washington', 8),
('New York', 10)],
'New York': [('New York', 0),
('Washington', 2),
('Toronto', 3),
('San Francisco', 7),
('Mexico City', 10)],
'Toronto': [('Toronto', 0),
('New York', 3),
('Washington', 5),
('San Francisco', 6),
('Mexico City', 7)],
'San Francisco': [('San Francisco', 0),
('Mexico City', 3),
('Washington', 5),
('Toronto', 6),
('New York', 7)],
'Washington': [('Washington', 0),
('New York', 2),
('San Francisco', 5),
('Toronto', 5),
('Mexico City', 8)]}
'''