F28DA: Data Structures & Algorithms, Heriot-Watt University, UK

Assessed Individual Coursework — Flying Planner

1 Overview

Your task is implement a Flying Planner which uses a graph library to represent airline data, and which supports searching. You should carefully test all of the code you write, generating new test files as necessary, and include illustrations of your Flying Planner user interface in your report.

The coursework aims to reinforce your understanding of course material, specifically the following learning objectives:

• Gain an understanding of a range of graph classes and their use to represent realistic data.

• Gain further experience in object-oriented software engineering with a non-trivial class hierarchy: specifically selecting an appropriate class; reusing existing classes; extending existing classes.

• Using generic code: reusing generic graph classes, and parameterising a class with different types.

• You will also gain general software engineering experience, specifically downloading and using Open Source software, using a general method for a specific purpose, and issues with reusing existing code.

• Gain further experience with Java programming.

Coursework Parts

Part A: Representing direct flights and least cost connections

Write a program FlyingPlannerMainPartA (containing a single main method) to represent the following direct flights with associated costs as a graph. For the purpose of this exercise assume that flights operate in both directions with the same cost, e.g. Edinburgh Ø Heathrow denotes a pair of flights, one from Edinburgh to Heathrow, and another from Heathrow to Edinburgh.

Hint: Flights are directed, i.e. from one airport to another, and weighted by the ticket cost, hence use the JGraphT SimpleDirectedWeightedGraph class. You should display the contents of the graph (and may omit the weights).

Extend your program to search the flights graph to find the least cost journey between two cities consisting of one or more direct flights.

Hint: use methods from the DijkstraShortestPath class to find the journey. A possible interface for your program might be one where you suggest a start and an end city and the cost of the entire journey is added up and printed.

The following airports are used :

Edinburgh

Heathrow

...

Please enter the start airport

Edinburgh

Please enter the destination airport

Kuala Lumpur

Shortest ( i . e . cheapest ) path :

1. Edinburgh -> Dubai

2. Dubai -> Kuala Lumpur

Cost of shortest ( i . e . cheapest ) path = £ 360

Java hint: You can redefine the .toString() method in your classes to customise printing of information. By Implement the main method your FlyingPlannerMainPartA program. This FlyingPlannerMainPartA do not need to use or implement the provided interfaces. No test is provided nor necessary for his part.

Part B: Use provided flights dataset, add flight information

You should now write a program FlyingPlannerPartBC (containing a single main method) which will make use of your class FlyingPlanner (this is the central class of your program although it does not have to have a main method).

Add flight information

Your program should be operating on a flight graph that will now include the following information about each flight. The flight number, e.g. BA345; the departure time; the arrival time; the flight duration; and the ticket price, e.g. 100. All times should be recorded in 24 hour hhmm format, e.g. 1830. Individual flight durations are under 24h.

Use the additional flight information to print the least cost journey in a format similar to the following example. The key aspects are:

1. A sequence of connecting flights (with least cost),

2. A total cost for the journey.

An example journey for Part B (and Part C) might resemble the following when the departure city is

Edinburgh and the destination Sydney:

Journey for Newcastle ( NCL ) to Newcastle ( NTL )

Leg Leave At On Arrive At

1 Newcastle ( NCL ) 1918 KL7893 Amsterdam ( AMS ) 2004

2 Amsterdam ( AMS ) 0747 CX0831 Hong Kong ( HKG ) 1702

3 Hong Kong ( HKG ) 0748 CX7100 Brisbane ( BNE ) 1427

4 Brisbane ( BNE ) 1628 QF0640 Newcastle ( NTL ) 1729

Total Journey Cost = £ 1035

Total Time in the Air = 1061

Java hint: You should use String.format to align the information you are printing.

Use provided flights dataset

Build your graph of flights using the provided flights dataset and its reader (FlightsReader). The dataset is composed of a list of airports (indexed by a three character code), and a list of flights (indexed by a flight code). The list of airports and flights originated from the Open Flights open source project. In addition to these initial lists the following information were automatically and randomly generated: the flight numbers, departure and arrival times, cost.