Description
Problem 1
Goal
Work with graphs.
Background
Travel in the times of the covid-19 pandemic can be tricky. Different jurisdictions have different
requirements on
– whether or not you can fly directly to them from other jurisdictions,and
– what kinds of tests you must have before entering.
Add the complexity of different travel opportunities by air vs by train and you start to need an
advanced degree just to make travel arrangements.
Travellers can also have different priorities when making travel plans. Some want to minimize
overall cost. Others want to travel with the least time in shared planes and trains. Still others
want to have the fewest stops in their travels.
You will develop a Java class that will help travellers optimize their travel plans to get from one
city to another.
Problem
Implement a class called TravelAssistant that will accept information that describes the travel
conditions for flights and train rides. The TravelAssistant then finds the best travel plan for
individuals basd on their start and destination cities, their vaccination status, and a description
of what they prioritize in their travel plans.
Your TravelAssistant class will include the following methods, at a minimum:
– boolean addCity( String cityName, boolean testRequired, int timeToTest, int
nightlyHotelCost ) throws IllegalArgumentException
– boolean addFlight( String startCity, String destinationCity, int flightTime, int flightCost) )
throws IllegalArgumentException
– boolean addTrain( String startCity, String destinationCity, int trainTime, int trainCost) )
throws IllegalArgumentException
– List planTrip ( String startCity, String destinationCity, boolean isVaccinated, int
costImportance, int travelTimeImportance, int travelHopImportance ) throws
IllegalArgumentException
Each of the methods operates as follows:
addCity
Indicate that a particular city is a possible starting point or destination in the travel plans. The
parameters provide information about the city:
– cityName – the name of the city, which should be kept unique.
– testRequired – true if someone who is unvaccinated requires a negative covid test to
travel into the city. Vaccinated individuals can enter the city whether or not
testRequired is true or false.
– timeToTest – the number of days that it takes to get a covid test result in the city.
Someone who isn’t starting in this city would spend this many days in a hotel while
waiting for test results. If timeToTest is negative then you cannot get a covid test in the
city.
– nightlyHotelCosts – the cost of spending one night in a hotel in this city. All hotel costs
will be normalized to the same currency before being reported to the TravelAssistant.
The method throws an exception if the input parameters are unacceptable. The method
returns true if the city can now be used in the TravelAssistant, and returns false if the
information contradicts data already known by the TravelAssistant.
addFlight
Record the existence of a one-way flight from the startCity to the destinationCity. Parameter
flightTime is the in-air time of the flight (in minutes) and parameter flightCost is the cost of that
flight.
The method throws an exception if the input parameters are unacceptable. The method
returns true if the flight can be used by the TravelAssistant, and returns false if the information
contradicts data already known by the TravelAssistant.
addTrain
Record the existence of a one-way train ride from the startCity to the destinationCity.
Parameter trainTime is the on-train time of the trip (in minutes) and parameter trainCost is the
cost of that train trip.
The method throws an exception if the input parameters are unacceptable. The method
returns true if the train ride can be used by the TravelAssistant, and returns false if the
information contradicts data already known by the TravelAssistant.
planTrip
Determine the sequence of plane, train, and city stays needed to travel from the startCity to the
destinationCity. You can determine your own way to find the best path, but I recommend
starting with looking at Dijkstra’s algorithm, which computes the shortest path in a graph.
The best path is defined by what the traveller feels is most important. Those importances are
defined by the relative weights of each of cost (both travel cost and hotel cost), travel time, and
number of hops in the travel (taking one flight or one train ride is one “hop”; staying in a city is
not a hop). Those relative weights are non-negative integers:
– costImportance
– travelTimeImportance
– travelHopImportance
For example, if cost is the only factor then costImportance can be 1 with travelTimeImportance
and travelHopImportance both being 0. On the other hand, if the cost of a flight is equally
important to each minute spent travelling then costImportance can be 1, travelTimeImportance
can be 1 and travelHopImportance can be 0.
Boolean variable isVaccinated lets the TravelAssistant know whether or not the traveller is
vaccinated; an unvaccinated individual may need to plan to get a covid test somewhere during
the trip to enter one of the cities.
The method returns the list of cities visited on the trip along with the mode of travel. Each
string in the returned list consists of the mode of travel (start, fly, train), a space, and then the
city at the end of the flight or train ride (or the starting point as the first entry).
If there is no way to travel between the given cities then return null as the list.
Assumptions
You may assume that
– All costs are in comparable currencies.
– All travel times are in minutes.
– When testing your code, the “best” travel plan will be unique, so you don’t need to
worry about which travel plan to return in the case of a tied cost.
Constraints
• You may use any data structures from the Java Collection Framework.
• You may not use a library package to for your graph or for the algorithm on your graph.
• If in doubt for testing, I will be running your program on timberlea.cs.dal.ca. Correct
operation of your program shouldn’t rely on any packages that aren’t available on that
system.
Notes
– You will need to write your own “main()” driver to test your class, or use JUnit to test
your class.
– You will need a class to store each vertex of the graph and a class to store each travel
“hop”.
– You will need to choose whether to store the graph as an adjacency matrix, as an
adjacency list, or as an incidence matrix. Your best bet will likely be an adjacency list.
– You might consider writing your own method to print the graph. It might help simplify
your debugging.
– It may be that you cannot plan travel between every pair of cities.
– When providing relative importance of cost, travel time, and hops, notice that the
underlying units (dollars, minutes, and hops) may not be directly comparable. Valuing
each factor equally may not look like the same integer for each of the factors. Instead,
you might think of the importance as the dollar value to me of each minute of travel
time and the dollar value to me of making one fewer hop. That interpretation shouldn’t
change your code, but it may help you determine test case values.
Marking scheme
• Documentation (internal and external), program organization, clarity, modularity, style –
4 marks
• Thorough (and non-overlapping) list of test cases for the problem – 3 marks
• Efficiency of your data structures and algorithms for the given task, as explained by your
own description of that efficiency (part of external documentation) – 2 marks
• Ability to create the travel network from the inputs and to return appropriately in error
conditions – 4 marks
• Ability to report travel paths correctly – 12 marks
CSCI 3901
