Note: Please document all of your classes and methods with Javadoc for this assignment.
The flight-scheduling team of the merged airline has already created a large graph of all the existing flights offered across the partner airlines. Your job is to write a program to (a) help find the gaps in the service and (b) suggest how they might fill in those gaps. There may have been gaps in the service within an individual regional airline, so viewing the gaps solely through the regional airlines' networks will not help here. To find the gaps in service, we first need to break the national flight graph into subsets of cities that can reach one another, but cannot reach cities in any other subset. For example, assume we have flights between Boston/Worcester, Boston/Hartford, Chicago/Denver, Phoenix/Houston, and Houston/Tulsa. This graph would yield three subsets: (Boston, Worcester, Hartford), (Chicago, Denver), and (Phoenix, Houston, Tulsa). We'll refer to each subset as a network.
Node
that consists of the name of a city and
a list of Nodes to which there exist a direct flight (as we developed in class).
Unlike the code we developed in class,
a connection between two cities should denote that there are flights in either
direction between the cities (in other words, if you can fly from city A to
city B, you can fly from city B to city A).
Graph
that contains a list of Nodes. Create at least one non-trivial example of a Graph (you may use the example described above
if you wish).
Network
that is a LinkedList of city names
(Strings).
getNetworks()
on graphs that returns a
LinkedList
of Networks.
Hints: Don't attempt to code this method until you understand what's being asked for. Work out examples on paper. Draw pictures of the data. Write
your test methods in the Examples class before you start to code. You will need
to keep track of visited Nodes; if you use a LinkedList of Nodes to do this,
then code getNetworks()
as a wrapper method that calls a helper
with an empty visited list as an argument.
newFlights()
on graphs that returns a list of
pairs of city names such that adding flights between each pair would turn the
entire graph into one network. Your returned list should have as few pairs as
possible, but does not need to account for any other constraints (such as the
distance between cities for the proposed flights).
Using web-based turnin, submit .java files containing the final versions of all classes, interfaces, and examples developed for this assignment. Do not submit the .class files. Create a zip file containing the separate files for each class/interface.