Due 11:00 PM Tuesday, March 18 Wednesday, March 19
The Project 4 specification document has been posted.
The Project 4 warmup has been incorporated into spec pp. 7-8, with big-O requirements that can be met with a binary search tree implementation that does not try to stay balanced.
The posted provided code includes a main routine you can use to test the whole system, as well as the provided.h and provided.cpp files the spec says we will provide.
Updates
3/13 11:30pm: We decree: An itinerary is not valid if the same airport appears more than once in the itinerary. This simplifies things if you choose to implement A*. The note below has the reasoning behind the decree.
3/13 11:10pm: In provided.h, the file main.cpp was updated to include <cmath> and to print the arrival time at the source airport in the itinerary (so the output matches what's shown in the spec). Also, the sample parameter file shown on spec p. 13 was updated to having no preferred airlines (so the output produced would match what's shown in the spec).
Notes
(The airport file was extracted from Arash Partow's Global Airport Database at http://www.partow.net/miscellaneous/airportdatabase/index.html. Flight schedules were obtained from https://aviation-edge.com.)
If you had to wait for three hours for a departing flight, would you rather wait at the airport, or fly to some nearby place and fly back within those three hours? Probably the former; the latter is more hassle, costs more, and risks a flight delay that causes you to miss the flight you're waiting to take. So it's not unreasonable for us to reject itineraries like this that revisit airports. (Of course, in the real world, there are people who would take the brief round trip because they love flying or because they need the miles/spend to reach the next tier of their frequent flyer program.)
Here's how this can arise:
You want to go from LAX to JFK. You're starting at LAX at 00:00. Your max layover time is 4 hours, min connection time is 1 hour, and maximum duration is 12 hours. Here are all the flights:
Let's do A*. You reject the 06:00 flight, since you'd have to wait 6 hrs for it, exceeding our max layover. The only flight that goes in the priority queue is the 00:00 flight to SAN. After 1 hour flying and 1 hour min connection, the only flight out is the 02:00 back to LAX. If we were to allow taking that, you'd return to LAX at 03:00. But now you could layover for only 3 hours and take the 06:00 flight to JFK. In general, it would complicate the A* algorithm and take more time to find an itinerary if you might have to rexplore parts of the graph because edges that were formerly unusable become usable.
If we reject returning to an airport we were already at, then in this little example there's nowhere else to go from SAN, so we can't form an itinerary that satifies the constraints.