The project requires that you maintain a list of cities. A city is described by a pair of integers representing the x,y coordinates of the city (which we could imagine are latitude and longitude). These coordinates are to be recorded as a list of length 2. A list of cities is therefore a list of [x, y] pairs like this:
[[12,24], [100,23], [76,123] ]
In this part of the project you are to write two functions that return lists of cities, one that reads the city data from a file, and a second that generates a list of randomly generated cities.
Reading City Data
Write a function called read_cities(fname) that reads coordinates from a file whose name is given in the string parameter and that returns a list of lists (or an empty list if the file does not exist) of the coordinates from the file.
The city files contain a series of lines where each line contains the x and y coordinates of a single city. The x and y coordinate of each city are separated by a single space. Here is a example of what a file containing three cities might look like:
-23 54
21 134
93 -67
You can find a file that matches these coordinates here. There is no need to write your own city files, although feel free to do so to test your read (and other) functions.
Opening and Reading Files
To open a file for reading use the open function.
f = open("test.txt", 'r') #opens a file called "text.txt" for reading
To read all of the lines of a file into a list of strings where each string represents a single line of the file use the readlines() method.
lines = f.readlines() #reads the entire file that f refers to into a list of strings
To seperate components of a string use the string split method. The split method splits a string on the given character (discarding that character) and returns a list of strings.
str = "hello world"
words = str.split(" ") #creates a list of words, in this example words contain: ["hello", "world"]
Finally, don't forget that you will need to record the coordinates as integers, not as strings.
Generating Random Cities
Write a function called generate_cities(min_x, max_x, min_y, max_y, n, distance) that generates a list of cities with random coordinates. The parameters represent the following:
* min_x, max_ x: the minimum and maximum values for the x coordinate of each city
* min_y max_ y: the minimum and maximum values for the y coordinate of each city
* n: the number of cities to be generated (that is the number of [x, y] lists)
* distance: the minimum distance allowed between any two cities
Here is a brief description of how you can generate your cities while ensuring that they are not too close to each other
repeat n times
generate random coordinates for new_city
too_close = True
while too_close == True
too_close = False
for each city in the city list so far
if the new_city < distance from city
too_close = True
generate new random city point
break
add new_city to the results list
You can find the distance between two cities by calculating the straight line distance between two points by writing a function with this header:
* get_distance(x1, y1, x2, y3) - calculates the straight line distance from point {x1, y1} to {x2, y2}. To calculate this, recall that the length of the hypotenuse is equal to the square root of the sum of the squares of the other two sides of the triangle.
Part 1 Summary
You should at least write the following functions (and may write other function that you consider necessary):
* read_cities(fname) - reads a file containing city data, and returns a list of cities (a list of pair-lists)
* generate_cities(min_x, max_x, min_y, max_y, n, distance) - generates a list of n random cities
Accessing Lists in Lists
You will need to access the city list pairs in side a list of cities. To do this use the indexes of the cities, and to access the x and y coordinates individually use the indexes 0 and 1. Here is a brief example of this:
>>> cities = [[20,30],[44,32],[55,23] ]
>>> cities[1]
[44, 32]
>>> cities[1][0]
44
>>>
And here is another example that prints the x and y coordinates in a for loop, note that the for loop has a variable that is assigned each of the values in the cities list, that is an individual city.
>>> for c in cities:
print "x =", c[0], "y=", c[1]
x = 20 y= 30
x = 44 y= 32
x = 55 y= 23
>>>
Part 2 Finding A Single Hub
In this section you will write functions to find a single hub in a list of cities. To do this you will first write a function that computes the total distance from each city to all the other cities, and that then returns a list of these distances. This list can then be searched to find the minimum total distance allowing this distance and the hub city to be displayed.
Computing Total Distances
Write a function called total_distances(cities) that returns a list of total distances between each of the cities in the cities list (a list of pair-lists). That is, the function should calculate the total distances between each city and all the other cities. The index of the results list should correspond to the index in the cities list so that index i in the results list represents the total distance between cities and all the other cities.
Sample Input and Output
* city1 = 30,40
* city2 = 0, 0
* city3 = 90,120
The cities list would therefore look like this:
[[30,40],[0,0],[90,120] ]
The total distances between cities are as follows
* distance between city1 and city2 is 50, and distance between city1 and city3 is 100, total = 150
* distance between city2 and city1 is 50, and distance between city2 and city3 is 150, total = 200
* distance between city3 and city1 is 100, and distance between city3 and city2 is 150, total = 250
The list that results from get_distance would therefore look like this:
[150,200,250]
where 150 is the total distance between city1 and the other two cities, 200 is the distance between city2 and the other two cities and 250 is the distance between city3 and the other two cities.
Finding the Minimum Distance
Write a called get_min(ls) that returns the index of the smallest value in the list parameter. For example get_min([23,12,56,10,91]) returns 3 (the index of the smallest value, 10).
Displaying the Hub City
Write a function called print_hub(cities, show_all) that has a city list cities parameter and a boolean show_all parameter. The function should use the other functions in part 2 to print the index of the hub city and the total distances from that city. If the boolean show_all parameter is True the function should also display the total distance from each cities.
Sample Output
Using generate_cities to first generate a list of cities
>>> cities = generate_cities(-200, 200, -100, 100, 10 ,10)
>>> cities
[[-162, -35], [-156, 26], [-104, -27], [-42, -76], [-141, -91], [-177, -84], [12, -78],
[23, -98], [-47, 14], [66, 86] ]
>>> print_hub(cities, True)
The hub is city 2 : {-104, -27}
The total distance to other cities = 924.926326081
city 0 : [-162, -35] : 1115.49644342
city 1 : [-156, 26] : 1273.42241125
city 2 : [-104, -27] : 924.926326081
city 3 : [-42, -76] : 1001.6712545
city 4 : [-141, -91] : 1119.48150226
city 5 : [-177, -84] : 1276.70675541
city 6 : [12, -78] : 1204.99978574
city 7 : [23, -98] : 1335.8061475
city 8 : [-47, 14] : 1074.10257815
city 9 : [66, 86] : 1951.43937627
Test Function
Write a test function called hub(useFile) that creates a city list, determines the hub city (the city with the minimum total distance to other cities) and displays the results.
Your function should read the city data from a file if the Boolean useFile parameter is True, and should ask the user the name of the file to be opened (using raw_input). If useFile is False the function should get user input (using raw_input) for the number of cities to be randomly generated. Where cities are to be randomly generated the function should not request user input for the min_x, max_x, min_y, max_y and distance parameters; instead you should use sensible values for these parameters (see the sample above for examples).
Part 2 Summary
You should at least write the following functions (and may write other function that you consider necessary):
* total_distances(cities) - returns a list of total distances from each city, i in cities to all other cities
* get_min(ls) - returns the index of the minimum value in ls
* print_hub(cities, show_all) - finds the hub city in cities, and displays this city and its total distances to the other cities
* hub(useFile) - allows the user to select the input method to create a city list and then calls print_hub
Part 3 - Display with Turtle Graphics
In this part of the project you are to display the results of calling our functions from parts 1 and 2 in turtle graphics. You are to write a function called show_hub that computes the hub from a list of cities and a test function called hub_turtle that generates a city list and displays it. You should also write some helper functions to do the work of displaying the cities and their connecting lines.
Cities should be represented by coloured circles, with the hub city being a different colour form the other cities. Lines should be drawn between cities that represent flight paths from your hub city(ies) to the spoke cities, so you should start off by writing and testing two turtle graphics functions that will do most of this low level work
Drawing a City
Write a function called circleAt(x ,y ,r ,g , b, radius) - draws a circle centred at x, y with the given radius and color (the color is specified by the r, g, b parameters which should be between 0 and 1.0). The turtle circle function draws a circle starting at the bottom centre if it is pointing to the right, so you will need to adjust for this in the circleAt function. Remember to lift the turtle up, go to the correct location, put the turtle down and orient (setheading) the turtle so it is pointing to the right before drawing the circle. You might want to provide default values for the color and radius parameters as most of the circles you will be drawing will probably be the same size and color.
Drawing a Flight Path
Write a function called lineFromTo(x_start, y_start, x_end, y_end, r, g, b) - draws a line from point {x_start, y_start} to {x_end, y_end}. The color of the line is specified by the r, g, and b parameters (which you might want to provide default values for).
Displaying the Hub and Spokes
Write a function called show_hub(cities) that has a city list cities parameter. The function should use the functions from part 2 to generate a list of total distances and find the hub city. The hub city and its spokes should then be displayed using the turtle functions described above. Your display should meet the following requirements:
* The circle representing the hub city should be slightly larger, and a different colour, than the circles representing the other cities
* Lines should be drawn from the hub city to the spoke cities.
* The total distance covered by the flight paths should be displayed in the turtle window.
Test Function
Write a test function called hub_turtle(useFile) that creates a city list, determines the hub city (the city with the minimum total distance to other cities) and shows the results using the show_hub function.
Your function should read the city data from a file if the Boolean useFile parameter is True, and should ask the user the name of the file to be opened (using raw_input). If useFile is False the function should get user input (using raw_input) for the number of cities to be randomly generated. Where cities are to be randomly generated the function should not request user input for the min_x, max_x, min_y, max_y and distance parameters.
Making Sure that Cities Appear
You must ensure that your cities appear in the turtle graphics window, this requires you to do some additional work to create the city list.
* If the city coordinates are read from a file then the cities list should be mapped, in-place, to a new list where the coordinates are scaled so that they fit in the turtle graphics window. You should write a function called scale_list(cities) that returns a new list of cities whose coordinates are in the turtle graphics window. You should not just scale down coordinates so that they appear in the window but should also scale up coordinates so the cities are not all clustered in one part of the window. Here is another file that requires this scaling up process.
* If the city coordinates are generated then just use the coordinates for the left, right, bottom, and top for the min and max x and y values in the generate_cities function.
Part 3 Summary
You should at least write the following functions (and may write other function that you consider necessary):
* circleAt(x ,y ,r ,g , b, radius) - draws a circle of the given colour and radius at the given location
* lineFromTo(x_start, y_start, x_end, y_end, r, g, b) - draws a line of the given colour between the given points
* show_hub(cities) - finds the hub city in cities, and uses turtle graphics to display the hub and spoke cities
* hub_turtle(useFile) - allows the user to select the input method to create a city list and then calls show_hub
* scale_list(cities) - returns a list of cites scaled to fit in the turtle graphics window
Part 4 - n cities, 4 Hubs
Consider the case where there are n cities and four hubs are to be determined to minimize the total distances (each hub will be connected to its spokes and the other hubs). You are to write functions to determine a reasonable (not optimal) choice for the four hubs. Spoke cities should only be connected to one hub.
Detailed Requirements
* The results are to be displayed graphically using the functions in part 3, you must show the total distance covered by the flight paths in the turtle window, this total should include the paths between the four hubs.
* In text (not as part of your program) provide an estimate of how many different possible ways there are of connecting any n cities. Note any simplifying assumptions that you made in your estimate. Provide your estimate in comments in your solution file.
Hints and Notes
* Solving this in the same general way as the previous questions (by exhaustively going through all of the calculations) is not practical.
* Feel free to select any strategy you think is reasonable, note that the better your solution (or the more ingenious your strategy) the more marks you will get!
* Make sure that parts 1 to 3 are complete (including comments and style issues) before attempting part 4
I really need your guys assistance
[[12,24], [100,23], [76,123] ]
In this part of the project you are to write two functions that return lists of cities, one that reads the city data from a file, and a second that generates a list of randomly generated cities.
Reading City Data
Write a function called read_cities(fname) that reads coordinates from a file whose name is given in the string parameter and that returns a list of lists (or an empty list if the file does not exist) of the coordinates from the file.
The city files contain a series of lines where each line contains the x and y coordinates of a single city. The x and y coordinate of each city are separated by a single space. Here is a example of what a file containing three cities might look like:
-23 54
21 134
93 -67
You can find a file that matches these coordinates here. There is no need to write your own city files, although feel free to do so to test your read (and other) functions.
Opening and Reading Files
To open a file for reading use the open function.
f = open("test.txt", 'r') #opens a file called "text.txt" for reading
To read all of the lines of a file into a list of strings where each string represents a single line of the file use the readlines() method.
lines = f.readlines() #reads the entire file that f refers to into a list of strings
To seperate components of a string use the string split method. The split method splits a string on the given character (discarding that character) and returns a list of strings.
str = "hello world"
words = str.split(" ") #creates a list of words, in this example words contain: ["hello", "world"]
Finally, don't forget that you will need to record the coordinates as integers, not as strings.
Generating Random Cities
Write a function called generate_cities(min_x, max_x, min_y, max_y, n, distance) that generates a list of cities with random coordinates. The parameters represent the following:
* min_x, max_ x: the minimum and maximum values for the x coordinate of each city
* min_y max_ y: the minimum and maximum values for the y coordinate of each city
* n: the number of cities to be generated (that is the number of [x, y] lists)
* distance: the minimum distance allowed between any two cities
Here is a brief description of how you can generate your cities while ensuring that they are not too close to each other
repeat n times
generate random coordinates for new_city
too_close = True
while too_close == True
too_close = False
for each city in the city list so far
if the new_city < distance from city
too_close = True
generate new random city point
break
add new_city to the results list
You can find the distance between two cities by calculating the straight line distance between two points by writing a function with this header:
* get_distance(x1, y1, x2, y3) - calculates the straight line distance from point {x1, y1} to {x2, y2}. To calculate this, recall that the length of the hypotenuse is equal to the square root of the sum of the squares of the other two sides of the triangle.
Part 1 Summary
You should at least write the following functions (and may write other function that you consider necessary):
* read_cities(fname) - reads a file containing city data, and returns a list of cities (a list of pair-lists)
* generate_cities(min_x, max_x, min_y, max_y, n, distance) - generates a list of n random cities
Accessing Lists in Lists
You will need to access the city list pairs in side a list of cities. To do this use the indexes of the cities, and to access the x and y coordinates individually use the indexes 0 and 1. Here is a brief example of this:
>>> cities = [[20,30],[44,32],[55,23] ]
>>> cities[1]
[44, 32]
>>> cities[1][0]
44
>>>
And here is another example that prints the x and y coordinates in a for loop, note that the for loop has a variable that is assigned each of the values in the cities list, that is an individual city.
>>> for c in cities:
print "x =", c[0], "y=", c[1]
x = 20 y= 30
x = 44 y= 32
x = 55 y= 23
>>>
Part 2 Finding A Single Hub
In this section you will write functions to find a single hub in a list of cities. To do this you will first write a function that computes the total distance from each city to all the other cities, and that then returns a list of these distances. This list can then be searched to find the minimum total distance allowing this distance and the hub city to be displayed.
Computing Total Distances
Write a function called total_distances(cities) that returns a list of total distances between each of the cities in the cities list (a list of pair-lists). That is, the function should calculate the total distances between each city and all the other cities. The index of the results list should correspond to the index in the cities list so that index i in the results list represents the total distance between cities and all the other cities.
Sample Input and Output
* city1 = 30,40
* city2 = 0, 0
* city3 = 90,120
The cities list would therefore look like this:
[[30,40],[0,0],[90,120] ]
The total distances between cities are as follows
* distance between city1 and city2 is 50, and distance between city1 and city3 is 100, total = 150
* distance between city2 and city1 is 50, and distance between city2 and city3 is 150, total = 200
* distance between city3 and city1 is 100, and distance between city3 and city2 is 150, total = 250
The list that results from get_distance would therefore look like this:
[150,200,250]
where 150 is the total distance between city1 and the other two cities, 200 is the distance between city2 and the other two cities and 250 is the distance between city3 and the other two cities.
Finding the Minimum Distance
Write a called get_min(ls) that returns the index of the smallest value in the list parameter. For example get_min([23,12,56,10,91]) returns 3 (the index of the smallest value, 10).
Displaying the Hub City
Write a function called print_hub(cities, show_all) that has a city list cities parameter and a boolean show_all parameter. The function should use the other functions in part 2 to print the index of the hub city and the total distances from that city. If the boolean show_all parameter is True the function should also display the total distance from each cities.
Sample Output
Using generate_cities to first generate a list of cities
>>> cities = generate_cities(-200, 200, -100, 100, 10 ,10)
>>> cities
[[-162, -35], [-156, 26], [-104, -27], [-42, -76], [-141, -91], [-177, -84], [12, -78],
[23, -98], [-47, 14], [66, 86] ]
>>> print_hub(cities, True)
The hub is city 2 : {-104, -27}
The total distance to other cities = 924.926326081
city 0 : [-162, -35] : 1115.49644342
city 1 : [-156, 26] : 1273.42241125
city 2 : [-104, -27] : 924.926326081
city 3 : [-42, -76] : 1001.6712545
city 4 : [-141, -91] : 1119.48150226
city 5 : [-177, -84] : 1276.70675541
city 6 : [12, -78] : 1204.99978574
city 7 : [23, -98] : 1335.8061475
city 8 : [-47, 14] : 1074.10257815
city 9 : [66, 86] : 1951.43937627
Test Function
Write a test function called hub(useFile) that creates a city list, determines the hub city (the city with the minimum total distance to other cities) and displays the results.
Your function should read the city data from a file if the Boolean useFile parameter is True, and should ask the user the name of the file to be opened (using raw_input). If useFile is False the function should get user input (using raw_input) for the number of cities to be randomly generated. Where cities are to be randomly generated the function should not request user input for the min_x, max_x, min_y, max_y and distance parameters; instead you should use sensible values for these parameters (see the sample above for examples).
Part 2 Summary
You should at least write the following functions (and may write other function that you consider necessary):
* total_distances(cities) - returns a list of total distances from each city, i in cities to all other cities
* get_min(ls) - returns the index of the minimum value in ls
* print_hub(cities, show_all) - finds the hub city in cities, and displays this city and its total distances to the other cities
* hub(useFile) - allows the user to select the input method to create a city list and then calls print_hub
Part 3 - Display with Turtle Graphics
In this part of the project you are to display the results of calling our functions from parts 1 and 2 in turtle graphics. You are to write a function called show_hub that computes the hub from a list of cities and a test function called hub_turtle that generates a city list and displays it. You should also write some helper functions to do the work of displaying the cities and their connecting lines.
Cities should be represented by coloured circles, with the hub city being a different colour form the other cities. Lines should be drawn between cities that represent flight paths from your hub city(ies) to the spoke cities, so you should start off by writing and testing two turtle graphics functions that will do most of this low level work
Drawing a City
Write a function called circleAt(x ,y ,r ,g , b, radius) - draws a circle centred at x, y with the given radius and color (the color is specified by the r, g, b parameters which should be between 0 and 1.0). The turtle circle function draws a circle starting at the bottom centre if it is pointing to the right, so you will need to adjust for this in the circleAt function. Remember to lift the turtle up, go to the correct location, put the turtle down and orient (setheading) the turtle so it is pointing to the right before drawing the circle. You might want to provide default values for the color and radius parameters as most of the circles you will be drawing will probably be the same size and color.
Drawing a Flight Path
Write a function called lineFromTo(x_start, y_start, x_end, y_end, r, g, b) - draws a line from point {x_start, y_start} to {x_end, y_end}. The color of the line is specified by the r, g, and b parameters (which you might want to provide default values for).
Displaying the Hub and Spokes
Write a function called show_hub(cities) that has a city list cities parameter. The function should use the functions from part 2 to generate a list of total distances and find the hub city. The hub city and its spokes should then be displayed using the turtle functions described above. Your display should meet the following requirements:
* The circle representing the hub city should be slightly larger, and a different colour, than the circles representing the other cities
* Lines should be drawn from the hub city to the spoke cities.
* The total distance covered by the flight paths should be displayed in the turtle window.
Test Function
Write a test function called hub_turtle(useFile) that creates a city list, determines the hub city (the city with the minimum total distance to other cities) and shows the results using the show_hub function.
Your function should read the city data from a file if the Boolean useFile parameter is True, and should ask the user the name of the file to be opened (using raw_input). If useFile is False the function should get user input (using raw_input) for the number of cities to be randomly generated. Where cities are to be randomly generated the function should not request user input for the min_x, max_x, min_y, max_y and distance parameters.
Making Sure that Cities Appear
You must ensure that your cities appear in the turtle graphics window, this requires you to do some additional work to create the city list.
* If the city coordinates are read from a file then the cities list should be mapped, in-place, to a new list where the coordinates are scaled so that they fit in the turtle graphics window. You should write a function called scale_list(cities) that returns a new list of cities whose coordinates are in the turtle graphics window. You should not just scale down coordinates so that they appear in the window but should also scale up coordinates so the cities are not all clustered in one part of the window. Here is another file that requires this scaling up process.
* If the city coordinates are generated then just use the coordinates for the left, right, bottom, and top for the min and max x and y values in the generate_cities function.
Part 3 Summary
You should at least write the following functions (and may write other function that you consider necessary):
* circleAt(x ,y ,r ,g , b, radius) - draws a circle of the given colour and radius at the given location
* lineFromTo(x_start, y_start, x_end, y_end, r, g, b) - draws a line of the given colour between the given points
* show_hub(cities) - finds the hub city in cities, and uses turtle graphics to display the hub and spoke cities
* hub_turtle(useFile) - allows the user to select the input method to create a city list and then calls show_hub
* scale_list(cities) - returns a list of cites scaled to fit in the turtle graphics window
Part 4 - n cities, 4 Hubs
Consider the case where there are n cities and four hubs are to be determined to minimize the total distances (each hub will be connected to its spokes and the other hubs). You are to write functions to determine a reasonable (not optimal) choice for the four hubs. Spoke cities should only be connected to one hub.
Detailed Requirements
* The results are to be displayed graphically using the functions in part 3, you must show the total distance covered by the flight paths in the turtle window, this total should include the paths between the four hubs.
* In text (not as part of your program) provide an estimate of how many different possible ways there are of connecting any n cities. Note any simplifying assumptions that you made in your estimate. Provide your estimate in comments in your solution file.
Hints and Notes
* Solving this in the same general way as the previous questions (by exhaustively going through all of the calculations) is not practical.
* Feel free to select any strategy you think is reasonable, note that the better your solution (or the more ingenious your strategy) the more marks you will get!
* Make sure that parts 1 to 3 are complete (including comments and style issues) before attempting part 4
I really need your guys assistance
