Last Modified: Sat Nov 22 11:37:15 EST 2003
|
C M S C 2 1 4 C o m p u t e r S c i e n c e I I F a l l 2 0 0 3 |
Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.
Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.
Hardcoding is considered a violation of academic integrity
Note in particular that the code you submit should be the work of your own and not that of another person or persons (with the exception of assistance from the 214 instructional staff).
In this project you will read in information related to a map of streets. Your program will store this information in a graph representation and then will permit someone to interactively request directions from one place to another.
You may assume that in the current directory, where your program is running, there will be a file named map.data and this text file will contain all of the information regarding streets found in the maps database including the intersections of streets with each other. This file will exist and will be readable and will contain information for at least one street (and possibly many more, no maximum limit specified) according to the following BNF (see the posting account files for an actual example):
[mapData] := [street][streets] | [street]
[streets] := [street][streets] |
[street] := [sInfo][nl][intersects]
[sInfo] := [ws*][name][nl][ws*][code][ws+][speed][ws+][numI][ws+][cf][ws*]
[name] := a string with no leading ws
[code] := [type]-[roadNum]
Note: each street will be UNIQUE -
meaning no two streets will have the same name or code
[speed] := any integer >= 1 representing the speed limit,
in miles per hour (MPH), of the road
[numI] := any integer >= 2
[cf] := any float to two decimal places >= 0.5
[type] := IR | UR | SR | CR
[roadNum] := any integer >= 1
[intersects] := [interInfo][intersects] | [interInfo][interInfo]
Note: the number of intersections listed here (one per
line) for each street will match exactly the number
specified by numI
[interInfo] := [ws*][code][ws+][dist][item][ws*][nl]
[dist] := any float to one decimal place >= 0.1
[item] := L | S |
[nl] := 1 newline
[ws] := 1 piece of whitespace (tab, blank, or newline)
[ws*] := [ws][ws*] |
[ws+] := [ws][ws+] | [ws]
Each street intersection represents a VERTEX in the graph and there exists an undirected EDGE between two vertices if and only if a street directly connects them. The (standard) weight of an edge is the length of the street (in miles - and will be a float with up to 1 decimal place) between the two intersections.
NOTE: if a street S connects two intersections (A and B) then a car can travel in both directions on street S - from A to B or from B to A - and the distance is the same both ways. Thus our map system can not handle one way streets (this is prefectly fine as there are many other limitations to our system as well).
NOTE: there can be more than one edge between two vertices and if so each edge will more than likely have a different weight (but they can be the same).
NOTE: not all parts of the data file may be needed for each option/choice below. For example in option/choice 1 the [speed], [cf] and [item] parts are not needed whereas in option/choice 2 the [item] part is not needed.
MORE DETAILS COMING SOON - It is recommended that for the first two days you do not actually start implementing this project, rather you should read it and think about it and how you plan to accomplish it. Basically spend some time designing your project first. Several header files will be provided on Monday which you can use - however you are free to use your own header files as well - but again it is recommended that you do not actually start implementing this until you have spent a couple days thinking about the project and how you would design the code to solve it.
Try to think about the two different parts of this project - part 1 - writing a generic (perhaps templatized) graph class (along with vertex and edge classes) and then - part 2 - using the graph class(es) to solve the specific problem(s) below which may involve writing some other classes like street or intersection and a main routine to process all of this.
NOTE: in this project you have more flexibility in designing the classes used - spending time in advance "planning" will hopefully assist you when implementing the code - additionally example generic graph code can be found in your textbook and in other published sources - if you use any such code directly or as a basis for your own code you need to thoroughly document this in the main comment at the top of each and every file containing any of this code (and by documenting you need to adequately describe the source/location from where you obtained the code). Additionally you should not discuss this (the location/source of borrowed code) with other students as that is in effect discussing your own code with them - it is each students responsibility for designing and creating their own code. Taking/using code from an unpublished source is not permitted - if there is any question regarding whether or not a source is considered published you should ask an instructor in office hours or before/after class.
In addition to using and designing several classes, you must write a file named main.cpp (named exactly that main.cpp). In particular this will be the program that users of your code can use to calculate paths in the graph.
The first noticeable item your program should do is print a single blank line and then the following message:
Welcome to the Map Calculator -----------------------------Followed by 1 single blank line. Next the program will print out the following menu and then process requests as they are entered:
Please choose from the following menu of options:
1) Calculate shortest route,
2) Calculate quickest route,
3) Calculate least # lights & stops,
4) Avoid major highways,
5) Quit
Enter choice now (1-5):
You may assume that the user will enter a valid request 1 through 5.
After reading the users choice your program should print a single
blank line and then process the request as specified below.
NOTE: prior to printing out this "menu" your program must read in and store all of the data from the map data file and may NOT create any additional files. Additionally it may not read from the map data file anymore once the "menu" is first displayed and may not create any additional files.
Quit (choice 5)
If the user chooses to quit, your program should print a single blank line and then end and return to the Unix prompt (releasing any dynamic memory it created properly). There is no additional output.
Shortest Route (choice 1)
If the user chooses this option your program should ask the user for the intersection at which they will begin and the intersection at which they intend to end using the following two prompts:
Please enter the starting intersection:and
Please enter the ending intersection:and then the user will enter two syntactically correct intersections (one after each prompt) each according to the following bnf:
[input1] := [ws*][code][ws+][code][ws*][nl]Your program should read in the two intersections and then print a single blank line.
If either intersection is not contained in the graph, your program should print the following message (error message 1):
Sorry, one or both of those intersections could not be found.If both intersections are contained in the graph your program should calculate the shortest path (using Dijkstra's algorithm) between the two intersections (which may be the same, in which case the shortest path is of length 0.0). If no such shortest path exists (from the first intersection to the second intersection) the following message should be output (error message 2):
Sorry, no route exists between those two stops.If there is a shortest path (note: there may be multiple answers, any one of which is acceptable) your program should output the path according to the following BNF:
[output1] := [intersections][routeLength] |
[start][intersections][end][routeLength]
Note: for the maximum amount of credit the 2nd option
here, with both [start] and [end], must be done -
however to pass primary the first above will work.
[start] := Starting at [name] and [name],[nl]
[intersections] := [entry][intersections] | [entry]
Note: every intersection visited must be displayed
[entry] := Go [dist] on [code] to [code][nl]
[end] := ending at [name] and [name].[nl]
[routeLength] := Total distance traveled: [dist] miles[nl]
After processing the users input for choice 1, as specified,
your program should print one additional blank line and then redisplay
the menu above and wait for the users next choice.
NOTE: if the starting and ending intersections are the same no [entry]s should be output and the distance traveled will be 0.0 miles.
For Dijkstra's algorithm (and all parts of this project) you should choose reasonably large values to represent INFINITY (for example you could determine what is the largest possible float value and use that for most of the choices).
Quickest Route (choice 2)
NOTE: This option is perhaps the hardest of the four choices and thus it is strongly recommended that you thoroughly plan out all four choices before starting to implement this choice.
If the user chooses this option your program should ask the user for the intersection at which they will begin and the intersection at which they intend to end using the same prompt and format used for choice 1.
The user will then enter two syntactically correct intersections using the same format as choice 1 - your program should read in this information and then print a single blank line.
If you did not get this option working your program should now (after reading in the two bus stops) print the following message (error message 3):
Sorry, this menu option is not available.If you did get this option working (it doesn't have to be perfect, but hopefully it doesn't crash) then your program should check the two intersections entered and if either is not contained in the graph your program should output error message 1 found in choice 1 above. If both are in the graph but there isn't any path from the starting to the ending intersection your program should output error message 2 found in choice 1.
If both stops are contained in the graph and a path exists between them, your program should calculate the quickest route and output that path according to the following bnf:
[output2] := [intersections][routeLength][routeTime] |
[start][intersections][end][routeLength][routeTime]
Note: for the maximum amount of credit the 2nd option
here, with both [start] and [end], must be done.
[start] := Starting at [name] and [name],[nl]
[intersections] := [entry][intersections] | [entry]
Note: every intersection visited must be displayed
[entry] := Go [dist] on [code] to [code][nl]
[end] := ending at [name] and [name].[nl]
[routeLength] := Total distance traveled: [dist] miles[nl]
[routeTime] := Total time: [time] minutes[nl]
[time] := a float to one decimal places
Note: there may be multiple valid answers to this problem (with the
same quickest time), and if that is the case your program should
only output one of the possible answers (any one).
After processing the users input for choice 2, as specified, your program should print one additional blank line and then redisplay the menu above and wait for the users next choice.
To calculate the TIME it takes to travel on a street you need several items - the speed limit (in MPH) of the street, the distance being traveled on that specific portion of the street and the [cf] (Congestion Factor) of the street. What follows are some examples which thoroughly describe how the time is calculated.
EXAMPLE 1 (and the "formula"):
Say that you travel a section (one edge) of a street and the length
is 2.0 (miles) and the speed limit of that street is 30 (MPH) and the
[cf] is 1.0 - then you would calculate the time it takes to travel that
edge as follows:
NOTE: that you assume a car is always traveling at top speed (except as limited by the congestion factor). When calculating the TOTAL ROUTE TIME you must do so ONE EDGE AT A TIME ACCORDING TO THE RULES ABOVE (and thus use a float variable - must be a float and not a double - to keep track of the total time - which is initially 0.0 and then gets added to it as each edge is traversed).
HINT: there are a number of differences between this choice and choice 1 however if you implement choice 1 with a little extra work the main difference (in determining the "shortest path") will be that the cost function used in Dijkstra's algorithm will be different - other than that the rest is pretty similar.
Least # Lights & Stops (choice 3)
If the user chooses this option your program should ask the user for the intersections at which they will begin and end using the same prompt and format used for choice 1.
The user will then enter two syntactically correct intersections using the same format as choice 1 - your program should read in the intersections and then print a single blank line.
If you did not get this option working your program should now (AFTER reading in the specified input) print error message 3 (see above).
If you did get this option working (it doesn't have to be perfect, but hopefully it doesn't crash) then your program should check the two intersections entered and if either is not contained in the graph your program should output error message 1. If both intersections are in the graph, but no path exists from the starting to the ending intersections, your program should output error message 2.
If both intersections are contained in the graph and a path exists (see below) between them, your program should calculate the path which involves the shortest number of lights and stop signs and output that path according to the following bnf:
[output3] := [intersections][routeLength] |
[start][intersections][end][routeLength]
Note: for the maximum amount of credit the 2nd option
here, with both [start] and [end], must be done.
[start] := Starting at [name] and [name],[nl]
[intersections] := [entry][intersections] | [entry]
Note: every intersection visited must be displayed
[entry] := Go [dist] on [code] to [code][nl] |
Go [dist] on [code] to [code] [item][nl]
[end] := ending at [name] and [name].[nl]
[routeLength] := Total distance traveled: [dist] miles[nl]
After processing the users input for choice 3 your program should print
one additional blank line and then redisplay the menu above and wait for
the users next choice.
Note: [output3] is very similar to [output1] HOWEVER the [entry]s might have [item] printed out which may be L or S
FOR THIS CHOICE you are attempting to find the path/route which involves the shortest number of stop lights (L) and stop signs (S) - so distance and time are not a factor. There may be multiple valid answers (say one route includes 2 lights and 1 stop sign and another included 2 stop signs and 1 light) and as long as your program outputs one of them you will pass this test.
If there is a stop sign or light at the STARTING intersection you do NOT count it. If there is a stop sign (or light) at the ENDING intersection you DO count it.
HINT: again, here the primary (not not necessarily only) difference between this choice and the others is that the cost function used is different.
Avoid Major Highways (choice 4)
If the user chooses this option your program should ask the user for the intersection at which they will begin and the intersection at which they intend to end using the same prompt and format used for choice 1.
The user will then enter two syntactically correct intersections using the same format as choice 1 - your program should read in the intersections and then print a single blank line.
EXTRA INPUT - next the user will enter the maximum "size street" they would like to travel on. Your program should print out the following prompt:
Please enter the largest size street to travel (1, 2, or 3 lanes):and then the user will enter a VALID size according to the following bnf:
[input4] := [ws*][size][ws*][nl] [size] := 1 | 2 | 3Your program should read in this size and then print a single blank line.
If you did not get this option working your program should now (AFTER reading in ALL of the specified input) print error message 3 (see above).
If you did get this option working (it doesn't have to be perfect, but hopefully it doesn't crash) then your program should check the two intersections entered and if either is not contained in the graph your program should output error message 1. If both are in the graph but there isn't any path (according to the rules below) from the starting to the ending intersection your program should output error message 2.
If both intersections are contained in the graph and a path (see below) exists between them, your program should output the shortest (in miles) such path/route that exists according to the following bnf (which is identical to [output1]):
[output4] := [intersections][routeLength] |
[start][intersections][end][routeLength]
Note: for the maximum amount of credit the 2nd option
here, with both [start] and [end], must be done.
[start] := Starting at [name] and [name],[nl]
[intersections] := [entry][intersections] | [entry]
Note: every intersection visited must be displayed
[entry] := Go [dist] on [code] to [code][nl]
[end] := ending at [name] and [name].[nl]
[routeLength] := Total distance traveled: [dist] miles[nl]
After processing the users input for choice 4 your program should print
one additional blank line and then redisplay the menu above and wait for
the users next choice.
FOR THIS CHOICE you are attempting to find the shortest (in miles) path/route which involves ONLY roads/streets with lanes less than or equal to the number input by the user. There may be multiple valid answers (in which case your program should output only one).
THE WAY YOU CAN TELL HOW MANY LANES A STREET HAS is by looking at its [type] (which is the first part of its [code]) and if the [type] is:
A project that performs any 3 choices (of 1-4) correctly for any valid graph we use/test will receive a maximum of 100% (assuming it is turned in ontime and written well using proper style, documentation and appropriate programming constructs).
If your program performs all 4 choices (of 1-4) correctly, as well as all other items specified for this project, then you will receive a maximum of 110% (meaning 10 possible bonus points).
If you have any questions/concerns regarding this project see someone in office hours per the guidelines/instructions outlined on the course syllabus. Do not email project related questions to the instructional staff (unless you are pretty certain there is an error in the description - if so email both instructors).
Read the checklist (see link near very top) for instructions on submitting. NOTE: failure to follow the guidelines specified on the checklist when submitting may result in the loss of MANY points on this project - be certain to follow the guidelines as specified on the checklist.
| See the class syllabus for policies concerning email
Last Modified: Sat Nov 22 11:37:15 EST 2003 |
|
|
|
|
|