Reference no: EM133111175

F28DA Data Structures and Algorithms - Heriot-Watt University

Coursework - Flying Planner

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: specific- ally 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.

JGraphT
JGraphT is a Java library of graph theory data structures and algorithms.Note that we will be using JGraphT version 1.3.0 which is not the latest released version of the library.

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's 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

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 hh:mm format (e.g., 18:30). 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. the sequence of connecting flights (with the least cost); 2.the total cost for the journey.

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.

Interfaces to implement
For the purpose of printing such journey, and to complete this part,
• your FlyingPlanner class should implement the IFlyingPlannerPartB<Airport,Flight> interface;
• your Journey class should implement the IJourneyPartB<Airport,Flight> interface;

• your Airport class should implement the IAirportPartB interface;
• your Flight class should implement the IFlight interface.

4 Part C: Advanced FEATURES
Extend your FlightPlanner class with the following extensions.

Journey duration
Extend your program to calculate the total time in the air, i.e., the sum of the durations of all flights in the journey and the total trip time.
Hint: you will need to write functions to perform arithmetic on 24 hour clock times.

Least hops
Extend your program to locate journeys with the fewest number of changeovers. Extend your program to offer the possibility to exclude one or more airports from the journey search.

Directly connected order
Extend your program to calculate for an airport the number of directly connected airports. Two airports are directly connected if there exist two flights connecting them in a single hop in both direction. Extend your program to calculate the set of airports reachable from a given airport that have strictly more direct connections.
Hint: use a directed acyclic graph, available in JGraphT.

Meet-Up search
Extend your program to offer the possibility to search for a least-hop/least-price meet-up place for two people located at two different airports. The meet-up should be different than the two stating airports. Extend your program to offer the possibility to search for a least time meet-up place for two people located at two different airports (considering a given starting time).

In order to score full marks, it will be enough to fully implement two out of the four advanced features. Still, try to implement as many as you can, as implementing more than the minimal two advanced features can help you recuperate some of the marks you drop elswhere in this coursework.

Attachment:- Data Structures and Algorithms.rar