Last Modified: Tue Apr 29 12:00:26 EDT 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 S p r i n g 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
In this project you will read in information related to a fictional set of bus schedules and the stops for each of the busses in that schedule. Your program will store this information in a graph representation and then will permit someone to interactively request bus routes between stops.
You may assume that in the current directory, where your program is running, there will be a file named schedule.txt and the file will contain all of the information regarding bus routes and the schedules for each bus and its stops. This file will exist and will be readable and will contain information for at least one bus and its route (and possibly many more, no maximum limit specified) according to the following BNF (see the posting account files for an actual example):
[schedule] := [route][routes] | [route]
[routes] := [route][routes] |
[route] := [busInfo][nl][stops]
[busInfo] := [ws*][bus][ws+][numStops][ws+][interval][ws+][numRuns][ws*]
[bus] := [Alpha]-[busInt]
Note: each bus will be UNIQUE -
meaning no two busses will have the same "name"
[numStops] := any integer >= 2
[interval] := any integer >= 1
[numRuns] := any integer >= 1
[Alpha] := any CAPITAL letter A through Z
[busInt] := any integer >= 0
[stops] := [stopInfo][stops] | [stopInfo][stopInfo]
Note: the number of stops for each bus route will match exactly
the number of stops specified by numStops
[stopInfo] := [ws*][stop][ws+][time][ws*][nl]
[stop] := [Alpha][Alpha][Alpha]
[time] := [hour]:[min]
Note: time will be in "military" format from 00:00 up
to 23:59 and each time for stopInfo will be at least
1 minute later (but still in the same day) as the prior
stopInfo time for this bus
[hour] := 00 | 01 | 02 | ... | 09 | 10 | 11 | ... | 23
[min] := 00 | 01 | 02 | ... | 09 | 10 | 11 | ... | 24 | 25 | ... | 59
[nl] := 1 newline
[ws] := 1 piece of whitespace (tab, blank, or newline)
[ws*] := [ws][ws*] |
[ws+] := [ws][ws+] | [ws]
Each stop represents a VERTEX in the graph and there exists a directed EDGE between two vertices if and only if a bus travels from the first vertex to the second one. The weight of an edge is the number of minutes the bus takes to get from the first vertex to the second one (so for example if the bus arrives at the first vertex at 12:30 and gets to the second vertex at 13:05 then the directed edge from the first vertex to the second vertex (for this bus) has a weight of 35).
NOTE: bus routes only go in one direction - from the first stop, then to the next stop, then ... finally to the last stop. Thus edges between vertices also go in one direction (the same direction as the bus traveling that route).
NOTE: there may be more than one edge between two vertices and each edge may have a different weight (or the same weight).
The [interval] and [numRuns] parts are only used in option/choice 3 below and unless you plan to attempt that optional part you can ignore this part of the data file (it will still be there, but you can just read over it). [numRuns] represents the number of times each day a bus leaves from its first stop to travel to its last stop. Additionally [interval] represents the duration of time (in minutes) that elapses between each run. So, for example, if a bus has 3 runs (with an interval of 90) and leaves from stop AAA at 10:30 and arrives at its "second" stop at 10:45 and its third stop at ... THEN another bus (with the same name) will leave from stop AAA at 12:00 (90 minutes after the first run) and the last bus (with the same name) will leave from stop AAA at 13:30 and it will arrive at its "second" stop at 13:45 and its third stop at ... You may assume that the last bus leaving a stop will always finish its run (aka: reach its last stop) by 23:59 at the very latest.
MORE DETAILS COMING SOON - DO NOT START IMPLEMENTING THIS PROJECT READ IT AND THINK ABOUT IT AND VERY SOON THERE WILL BE PROVIDED FILES (.h files) WHICH YOU WILL BE REQUIRED TO USE.
In addition to using the classes specified above, and those that you create, 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 Bus Route 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 path,
2) Calculate shortest # stops,
3) Calculate REAL shortest path,
4) Calculate shortest # transfers,
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.
Quit (choice 5)
If the user chooses to quit, your program should end and return to the Unix prompt (releasing any dynamic memory it created properly). There is no additional output.
Shortest Path (choice 1)
If the user chooses this option your program should ask the user for the bus stop at which they will begin and the bus stop at which they intend to end using the following prompt:
Please enter the starting and ending stops:and then the user will enter two syntactically correct bus stops according to the following bnf:
[input1] := [ws*][stop][ws+][stop][ws*][nl]Your program should read in the two stops and then print a single blank line.
If either stop is not contained in the graph your program should print the following message (error message 1):
Sorry, one or both of those stops are not serviced by this bus company.If both stops are contained in the graph your program should calculate the shortest path (using Dijkstra's algorithm) between the two stops (which may be the same stop, in which case the shortest path is of length 0). If no such shortest path exists (from the first stop to the second stop) 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] := [actualStops][transitTime]
[actualStops] := [entry][actualStops] | [entry]
Note: even if a traveler is not transferring from
one bus to another, every bus stop visited
must be displayed
[entry] := Take [bus] from [stop] to [stop][nl]
[transitTime] := Total time: [hour]:[min][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: for choice 1 you must assume that busses are always waiting at a stop for a passenger and then once a passenger arrives they instantaneously switch (transfer) from one bus to another (if necessary) and then continue on that next bus without having to wait for it to show up. Your program must make this assumption for choice 1. Additionally the travel time (cost) from one stop to another is the weight of the edge (again this is a simplification and does not necessarily reflect reality).
For Dijkstra's algorithm (and all parts of this project) you may assume INFINITY is equal to the total number of minutes in a day plus 1.
Shortest Number of Stops (choice 2)
If the user chooses this option your program should ask the user for the bus stop at which they will begin and the bus stop at which they intend to end using the same prompt and format used for choice 1.
The user will then enter two syntactically correct bus stops using the same format as choice 1 - your program should read in the two stops 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 stops entered and if either stop is not contained in the graph your program should output error message 1 found in choice 1 above. If both stops are in the graph but there isn't any path from the starting to the ending stop 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 shortest path (with regards to the number of bus stops visited) and output that path according to the following bnf:
[output2] := [actualStops][stopTotal]
[stopTotal] := Total stops: [stopInt]
[stopInt] := an integer >= 0
Note: the stopInt will equal the number of lines
output in the actualStops portion or 0 if the
start and end stops are the same
Note: there may be multiple valid answers to this problem (with the
same shortest "length"), 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.
Note: this problem is very similar to the first part (choice 1) and if implemented well only one or two very small "twists"/modifications need to be done to enable you to use the exact same code used in choice 1 to solve this problem. You may ignore time completely for this problem.
REAL Shortest Path (choice 3)
Choices 3 and 4 are harder options and should be attempted last (choice 4 is not necessarily harder than choice 3 they just had to be put in some order). See below for a very high level grading criteria that we will use (and how choices 1 and 2 are much more important).
If the user chooses this option your program should ask the user for the bus stop at which they will begin and the bus stop at which they intend to end using the same prompt and format used for choice 1.
The user will then enter two syntactically correct bus stops using the same format as choice 1 - your program should read in the two stops and then print a single blank line.
EXTRA INPUT - next the user will enter the time that they plan to show up at the starting bus stop. Your program should print out the following prompt:
Please enter the time you plan to start at:and then the user will enter a VALID time according to the following bnf:
[input3] := [ws*][time][ws*][nl]Your program should read in this starting time and then print a single blank line - this time can be any time from 00:00 up to 23:59.
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 stops entered and if either stop is not contained in the graph your program should output error message 1. If both stops are in the graph, but there isn't any REAL path from the starting to the ending stop, your program should output error message 2.
If both stops are contained in the graph and a REAL path exists (see below) between them, your program should calculate the path which involves the shortest amount of time and output that path according to the following bnf:
[output3] := [actualStops][transitTime]
Note: this is identical to [output1] and there is no
visible difference - this time however the transit
time will include any/all time a person has to spend
waiting for a bus to show up!
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.
Ideally for debugging purposes your program should not only print just the [entry] information but also the time of arrival and/or departure from each stop - you can/should do this for testing purposes however DO NOT DO THIS in your final submission for grading as it will lose all points for this part/choice 3.
Note: You may assume that if someone shows up for a bus at a specific time (say 10:35) and a bus is leaving at that time they are able to get on the bus. Also this means that if a bus arrives at 10:35 and the next one leaves at 10:35 they will be able to transfer to the other bus (if necessary). The only "unrealistic" assumptions that are being made for this part are that: 1) transfering from one bus to another one takes no time and 2) that busses always show up on time and arrive exactly on time.
Hint: choice 3 is probably harder than choice 4 - so you may want to try choice 4 first. One possible way to solve choice 3 is to add many "extra" edges to the graph (and each edge will need to store a little more information than what was needed for choices 1, 2 and 4) and additionally use a special cost function like the one that was recommended for choice 4. In particular the cost function needs to take into account the wait time (which involves the arrival time and the departure time) - it does NOT need to know which bus you are arriving on - merely the time you will be arriving.
Shortest Number of Transfers (choice 4)
Choices 3 and 4 are harder options and should be attempted last. See below for a very high level grading criteria that we will use.
If the user chooses this option your program should ask the user for the bus stop at which they will begin and the bus stop at which they intend to end using the same prompt and format used for choice 1.
The user will then enter two syntactically correct bus stops using the same format as choice 1 - your program should read in the two stops and then print a single blank line.
EXTRA INPUT - next the user will enter the bus that they plan to start on (this simplifies the problem a little bit). Your program should print out the following prompt:
Please enter the bus you will start on:and then the user will enter a VALID bus according to the following bnf:
[input4] := [ws*][bus][ws*][nl]You may assume that this bus DOES either start at this vertex/bus stop or that it passes through this bus stop at some point in time (and does not end at this bus stop). Your program should read in this bus "number" 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 stops entered and if either stop is not contained in the graph your program should output error message 1. If both stops are in the graph but there isn't any path from the starting to the ending stop your program should output error message 2.
If both stops are contained in the graph and a path exists between them, your program should calculate the path which involves the fewest number of transfers and output that path according to the following bnf:
[output4] := [actualStops][transferTotal]
[transferTotal] := Total transfers: [transferInt]
[transferInt] := an integer >= 0
Note: the transferInt will equal the number of
transfers that occur and actualStops will print
out ALL of the bus stops visited, even if a
transfer does not take place
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.
Note: You may ignore time completely for this problem. A TRANSFER is when you are on a bus and have to switch to another bus in order to get to your final destination. For example say you are on a bus and you can stay on that bus and get to your final destination (without having to leave that bus and get on another one) then you transfered 0 times and that would be "shortest transfer path". It is possible for there to be multiple valid answers - your program should only output one such answer (any valid shortest one is fine).
Hint: if you think about how to assess the cost factor involved and if you modified the code to use a cost function inside of Dijkstra's algorithm (rather than using a fixed weight/cost on the edges), then this may actually be an easy problem to solve. Note: you would also need to know which bus the user is starting on and/or coming from.
A project that performs choices 1, 2 and 5 correctly for any valid graph we use/test and implements the required classes/member functions correctly will receive a maximum of 90% (assuming it is turned in ontime and written using proper style and documentation).
In order to obtain 100% the program must also perform 1 of either choice 3 or choice 4 (your choice) correctly for any valid graph we use/test.
If your program performs both choice 3 and choice 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.
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: Tue Apr 29 12:00:26 EDT 2003 |
|
|
|
|
|