import os os.chdir("/media/guerzhoy/Windows/cs_for_docs/phase2/assignments/cities_epidemic/A2/starter") 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 build_direct_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 (in unvisited) updated, if going through C leads to a shorter total distance - dictionary distances is not changed 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 = build_direct_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. # find the city that is closest next_city_tuple = get_closest(unvisited) # remove it from unvisited # find index index = find_city(next_city_tuple[0], unvisited) # remove it unvisited[index:index+1] = [] # add to visited list visited.append(next_city_tuple) ############################################################################ # 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 neighbour_list = distances[next_city_tuple[0]] for i in range(len(neighbour_list)): neighbour = neighbour_list[i] index_in_unvisited = find_city(neighbour[0], unvisited) if find_city(neighbour[0], visited) >= 0: pass elif index_in_unvisited >= 0: # if going through next_city is faster, then update the distance new_route_distance = neighbour[1] + next_city_tuple[1] if new_route_distance < unvisited[index_in_unvisited][1]: unvisited[index_in_unvisited] = (unvisited[index_in_unvisited][0], new_route_distance) else: # this is the first route we have discovered to reach this city # so distance is distance to next_city PLUS distance from next_city to neighbour unvisited.append((neighbour[0], neighbour[1] + next_city_tuple[1])) def visit_all(departure_city, distances): '''Return the list of shortest distances from departure_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 build_direct_distances() >> distances = build_direct_distances(open("cities.txt").readlines()) >> visit_all('Toronto', distances) [('Mexico City', 7), ('New York', 3), ('San Francisco', 6), ('Toronto', 0), ('Washington', 5)] ''' unvisited = [(departure_city, 0)] visited = [] while len(unvisited) > 0: visit_next(visited, unvisited, distances) visited.sort() return visited distances_cities_txt = {'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)]} distances_difficult = {"A": [('B', 1), ('D', 5)], "B": [('A', 1), ('C', 1), ('D', 3)], "C": [('B', 1), ('D', 1)], "D": [('A', 5), ('B', 3), ('C', 1)]} distances = distances_cities_txt unvisited = [('Toronto', 0)] visited = [] visit_next(visited, unvisited, dist) if visited == [('Toronto', 0)]: print("Test 1 passed") if unvisited == [('Mexico City', 7), ('New York', 3), ('San Francisco', 6)]: print("Test 2 passed") visit_next(visited, unvisited, distances) if visited == [('Toronto', 0), ('New York', 3)]: print("Test 3 passed") if unvisited == [('Mexico City', 7), ('San Francisco', 6), ('Washington', 5)]: print("Test 4 passed") visit_next(visited, unvisited, distances) if visited == [('Toronto', 0), ('New York', 3), ('Washington', 5)]: print("Test 5 passed") if unvisited == [('Mexico City', 7), ('San Francisco', 6)]: print("Test 6 passed") visit_next(visited, unvisited, distances) if visited == [('Toronto', 0), ('New York', 3), ('Washington', 5), ('San Francisco', 6)]: print("Test 7 passed") visit_next(visited, unvisited, distances) if visited == [('Toronto', 0), ('New York', 3), ('Washington', 5), ('San Francisco', 6), ('Mexico City', 7)]: print("Test 8 passed") ########################################################################################################################### if visit_all("Toronto", distances) == [('Mexico City', 7), ('New York', 3), ('San Francisco', 6), ('Toronto', 0), ('Washington', 5)]: print("Test 9 passed") if visit_all("New York", distances) == [('Mexico City', 10), ('New York', 0), ('San Francisco', 7), ('Toronto', 3), ('Washington', 2)]: print("Test 10 passed") if visit_all("San Francisco", distances) == [('Mexico City', 3), ('New York', 7), ('San Francisco', 0), ('Toronto', 6), ('Washington', 5)]: print("Test 11 passed") if visit_all("Mexico City", distances) == [('Mexico City', 0), ('New York', 10), ('San Francisco', 3), ('Toronto', 7), ('Washington', 8)]: print("Test 12 passed") if visit_all("Washington", distances) == [('Mexico City', 8), ('New York', 2), ('San Francisco', 5), ('Toronto', 5), ('Washington', 0)]: print("Test 13 passed") ########################################################################################################################### if visit_all('A', distances_difficult) == [('A', 0), ('B', 1), ('C', 2), ('D', 3)]: print("Test 14 passed")