Old Republic Spaceways has a small fleet of ten ships but wishes to offer passage between all planets.
At the start time
Tstart
each ship is in its respective home port.
All scheduled departures and arrivals are relative to the start
time. Times are in 1-hour increments.
An imperial day is 24 hours.
Each ship follows its assigned route stopping at each port-of-call and departing on schedule. The route may visit some planets more than once, and others not at all. The ships do not have to return to their home ports at the end of the schedule period1.
At every stop, there is a minimum layover of 4 hours to allow refuelling, reprovisioning, and the off-loading/on-loading of passengers and cargo. A ship may be scheduled to wait longer than its minimum time if it will improve connection times.
When a passenger's itinerary requires transferring ships, a "legal connection" is a minimum of 6 hours between arrival and departure to allow passengers to clear customs, file the neccessary paperwork and pay the requisite bribes.
Enroute travel times between any pair of planets is determined by the following chart found somewhere in the flotsam of space. Collect the data into a text file that your progrm will read on startup. You may define the format of the file. Consider using somthing compatible with the routing file format so you can reuse code. Pass the name of timing file as a command-line argument.
Define a route structure that makes it possible to travel between all pairs of planets, even if there is no direct link between some pair. A ship may visit a planet zero, one or several times and a planet may be visited by multiple ships.
Your program will read the route structure in from an input file and validate the input to verify that ships obey the transit and layover times. Be sure that ships don't magically disappear and reappear or show up in two places at once.
If the route structure is invalid or some destination cannot be reached from an origin planet, the program should terminate with a non-zero exit status.
Determining a routing structure that maximizes revenue is a highly nontrivial problem. Your task is considerably simpler: just come up with a workable schedule, not necessarily an optimal one.
In a terrestrial-based production system, the schedule would be stored in a standard file format, such as XML, JSON, or protobufs, and parsed using a library. Since the old republic never heard of these things, you're going to have to roll your own as follows.
The file will use tab-separated values, similar to CSV. Use the
tab character (control-I, ASCII value 0x08) as the field separator
within each line. Blank lines and lines beginning with the comment
character
#
in column 1 are ignored.
Each record consists of the following fields:
Read the input from standard input. The program should terminate with error status if malformed input is received.
To validate the route structure and determine its goodness, find the weighted diameter of the graph: the longest shortest-path between pairs of planets. Use Dijkstra's algorithm, which solves the single-source shortest path problem, iteratively2.
For the purpose of calculating travel time, use the earliest possible arrival time at the destination. We could equally well seek to minimize enroute time (difference between arrival and departure time), or in-space time (subracting out layover time).
Your program should emit the longest shortest-path itinerary in the same format as the input route structure file. Your README file should report the arrival time, total time enroute, and time in space. You may hand-calculate the values, have your program compute them (and write to standard error), write a stand-alone C++ program (reusing whatever you can), or write a script3.
You may use
std::vector
and
std::map,
but marks will be forfeited if you do an
O(log N)
dictionary lookup when a simple
O(1)
pointer or vector dereference would have worked.
Hint: use the
map
to find the node corresponding to a given planet name while
building the graph from its textfile description.
Note that the STL
priority_queue
class is missing the
decrease_key
operation required by Dijkstra's algorithm, so you couldn't use it
even if it were permitted. Which it isn't. Good thing you happen
to have some old priority queue implementation lying around from
assignment 3 that you can adapt.
Doing a linear search instead of a log-time search for the next
planet will result in suboptimal performance of the algorithm and
consequently a suboptimal grade.
Since there may be multiple flights between a pair of planets, you may encode this as a multi-graph (multiple edges connecting the nodes), or as a simple graph with a complex edge structure.
Use an edge list4, not an adjacency matrix.
Build
&
Run
scripts
README
file with additional notes & comments
Your routing data will be run against the instructor's reference implementation to verify your solution.
vector class implements the list abstraction.