Brandeis Map Project
Implement a walking map utility for the Brandeis campus. Your program will ask for a begin location, a finish location, whether using a skateboard, and whether to minimize distance or time. All code you submit must be created and written by you, and other than for basic input-output functions, your program should be completely self-contained and not include libraries for any data structures. It should be an implementation of Dijkstra's algorithm using an adjacency list representation of the graph and a "full tree" array heap data structure as presented in class.
You are provided the following files:
BrandeisMapLabeled, BrandeisMapLabeledCropped: The full map is useful as a reference, but it may be convenient to display the cropped version.
MapDataVertices: A list of vertices, one line for the information associated with each vertex.
MapDataEdges: A list of directed edges, one line for the information associated with each edge.
Display: Programs in different languages (take your pick) to display a route on the Brandeis map.
SampleOutputs: Sample input/output from a working program.
What to pass in (e.g., if you are John Smith, pass in SmithJohn.zip containing these items):
ReadMe.txt : A plain text file that describes how your code works (for both Parts 1 and 2), which begins with how to compile and run your code in a UNIX terminal window in the COSCI Lounge. For example, if your program was a C program, the command line might be:
gcc -std=c99 -Wall -o Map Map.c
Note:You may likely develop code on your own machine, but before passing it in, to receive full credit, it must work in a UNIX terminal window in the COSCI Lounge using exactly the command line in your ReadMe.txt file.
MapFolder: A folder with all of your source code (for both Part 1 and 2), which must be written in one of the languages C, C++, JAVA, or Python. Your program should be named Map with the appropriate extension (.c, .cpp, .java, or .py) and compiled into the executable called Map. It is ok to break your code into multiple files that are included to the main program, and at the very least the code for Part 2 should be in a separate file.
Output.txt :A single plain text file of the output generated when providing these 12 inputs:
1. U14 L24 board=y time=y2. U14 L24 board=y time=n3. U14 L24 board=n time=n4. U37 L5 board=y time=y5. U37 L5 board=y time=n6. U37 L5 board=n time=n7. U40 + board=y time=y8. U40 + board=n time=n9. U17 L36 board=y time=y10. L1 A4 board=n time=y11. L36 $ board=n time=y12. ! = board=n time=n
TourOutput :See Part 2 of this assignment (next page).
Make a campus tour, which would be great if it was a shortest possible Hamilton cycle or Hamilton path (i.e., a solution for this graph to the Traveling Salesman problem), but will just be the best you can come up with for a minimal length cycle or path that visits all locations on the map.
WARNING: Don't do this, don't even think about it, until you have the basic Part 1 project fully working!
Implement Prim's minimum spanning tree algorithm and then traverse the resulting tree in pre-order to create a cycle that has cost that is twice the sum of the edges of the spanning tree (i.e., upon returning, preorder visits the edge in the opposite direction).
Grading criteria:For full credit, it needs to work, make use of the graph and heap structures from Part 1, and be reasonably well written and documented.
Make a tour better than the one computed in Part 2A.
Grading criteria: At a minimum, "shortcutting" should be implemented by using edges that are not in the tour computed in Part 2A to replace a successive pair of edges currently in the tour. Full credit requires going beyond this base approach, such as better shortcutting methods for the spanning tree, the option of Kruskal's algorithm instead of Prim (it is ok if it produces the same tree, you get credit for doing it), different approaches to path construction (e.g., base it on starting with an Euler path), and offering the option of having the tour end at a different location. Credit will depend on how well your code is implemented and on your degree of success. in the tour computed in Part 2A to replace a successive pair of edges currently in the tour. Full credit requires going beyond this base approach, such as better shortcutting methods for the spanning tree, the option of Kruskal's algorithm instead of Prim (it is ok if it produces the same tree, you get credit for doing it), different approaches to path construction (e.g., base it on starting with an Euler path), and offering the option of having the tour end at a different location. Credit will depend on how well your code is implemented and on your degree of success.The TourOutput folder:
Provide as many of these files as you like or are able:
OutputTourP.txt: Minimal spanning tree using Prim's Algorithm, starting at vertex J.
OutputTourPP.txt: Pre-order traversal of the Prim spanning tree to form a cycle.
OutputTourJ.txt: Your shortest distance cycle tour, no skateboard, starting at vertex J.
OutputTourJS.txt: Your minimum time cycle tour, with skateboard, starting at vertex J.
OutputPathJC.txt: Your shortest distance path tour, no skateboard, vertex J to castle.
OutputPathJCS.txt: Your minimum time path tour, with skateboard, vertex J to castle.
OutputTour1.txt, OutputTour2.txt, ... :
At most 9 other outputs to demonstrate your program. Do not include these files unless you really need them to demonstrate something above and beyond the files listed above.
Computation of Time
Based on 3.1 miles per hour as the average human walking speed on level ground (e.g., see Wikipedia), in units of feet per minute, use this constant for the human walking speed on level ground:
WalkSpeed = (3.1 miles/hr) * (5280 ft/mile) / (60 mins/hr) = 272 feet / minute
For special kinds of edges, the speed at which the edge may be traversed must further be adjusted by these constants:
WalkFactorU = 0.9 - Multiply WalkSpeed by this for walk up.
WalkFactorD = 1.1 - Multiply WalkSpeed by this for walk down.
SkateFactorU = 1.1 - Multiply WalkSpeed by this for skateboard up.
SkateFactorF = 2.0 - Multiply WalkSpeed by this for skateboard flat.
SkateFactorD = 5.0 - Multiply WalkSpeed by this for skateboard down.
StepFactorU = 0.5 - Multiply WalkSpeed by this for walk up steps.
StepFactorD = 0.9 - Multiply WalkSpeed by this for walk down steps.
BridgeFactor = 1.0 - Multiply WalkSpeed by this for walking on a bridge.
Using the correct adjusted speed in units of feet per minute, the time to traverse an edge is it length in feet divided by the traversal speed, times 60 to get the time in seconds.
Note: Use of skateboards is not allowed on steps or bridges.
Input-Output Format For Part 1
To facilitate grading, make your input-output format as close as possible to this sample (additional samples are provided in the SampleOutputs folder):
************* WELCOME TO THE BRANDEIS MAP *************
Enter start (return to quit): castle
Enter finish (or return to do a tour): farber l
Have a skateboard (y/n - default=n)?
Minimize time (y/n - default=n)?
FROM: (U40) Usen Castle
ON: Usen Driveway
Walk 126 feet in direction 273 degrees West.
TO: (7) Usen Main Entrance
FROM: (7) Usen Main Entrance
ON: Path Between Usdan and Kutz/Schwartz/Lemberg
Walk 553 feet in direction 282 degrees West.
TO: (U) Between Social Sciences And Library
FROM: (U) Between Social Sciences And Library
Walk 160 feet in direction 262 degrees West.
TO: (U23) Pearlman Hall
FROM: (U23) Pearlman Hall
Walk 182 feet in direction 307 degrees NW.
TO: (U22) Farber Library
legs = 4, distance = 1021 feet, time = 3.8 minutes
Input-Output Format For Part 2
After the user returns instead of providing a finish location in response to the second question, how you ask subsequent questions for different options is up to you. Be sure that your questions are selfexplanatory so it is clear what options you have implemented (Prim tree, basic shortcutting, tour cycle vs tour path, ending location for a tour path, etc.) and the grader can easily test them.Output:
The output format for Part 2 should be the same as that for Part 1.Plotting A Route
Your program should output files Route.txt and RouteCropped.txt for plotting the route on the Brandeis map (useful for debugging and also grading). They list the start and end points of each edge traversed in units of pixels (one edge per line). For the example on the preceding page, these two files are:
1886 471 1829 4691829 469 1582 4131582 413 1509 4261509 426 1443 375
The numbers in feet in the map files must be scaled according to constants that describe the image size:1736 346 1679 3441679 344 1432 2881432 288 1359 3011359 301 1293 250
MapWidthFeet 5521 /*Width in feet of map.*/
MapHeightFeet 4369 /*Height in feet of map.*/
MapWidthPixels 2528 /*Width in pixels of map.*/
MapHeightPixels 2000 /*Height in pixels of map.*/
CropLeft 150 /*Pixels cropped from left of map.*/
CropDown 125 /*Pixels cropped from top of map.*/
That is, for an edge going from vertex (v,w) to vertex (x,y) the numbers a, b, c, d for the corresponding line in Route.txt are obtained by doing (use floating point computation and then convert to integer):
a = v * MapHeightPixels / MapHeightFeet
b = w * MapWidthPixels / MapWidthFeet
c = x * MapHeightPixels / MapHeightFeet
d = y * MapWidthPixels / MapWidthFeet
and for RouteCropped.txt by in addition doing:
a = a - CropLeft
b = b - CropDown
c = c - CropLeft
d = d - CropDown
Here is the route that is plotted for the example above: