F28DA: Data Structures & Algorithms - Coursework - A Travel Agent System
Assessed Individual Coursework — A Travel Agent System
1 Overview
Your task is implement a system for a travel agency which uses a graph library to represent airline data, and supports searching based on criteria the travel agent sets. For this reason, the system should allow inputs from the user and an output in an appropriate format.
Some code is provided to help you in getting started with JUnits for checking your code. We also provide you with a Dataset that you should use for your system. Your code should work with any dataset, and we will use a different dataset during assessment.
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.
Part A: Week 8-9 Familiarise yourself with JGraphT (see Section 2). Create graphs by hand from vertices and edges. Search for shortest paths
Part B: Week 9-10 Build graph from provided flights data. Add information to the graph’sedges Other path searches
Part C: Week 10-11 Implement all extensions:
Calculate and display the total journey duration Find the path with the least number of plane changes during a single trip Display the path in an appropriate way Do a Shortest and a Critical Path search, displaying the information in an appropriate manner for a travel agent to understand.
2 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 at the time of writing this coursework specifications. The reason we are not using the latest version is to ensure compatibility across all machines (lab+personal).
2.1 Preliminary Part: Installation and get familiar with JGraphT
To use the library, you need to have a personal copy of the Open Source JGraphT graph library in your working environment. As we explain below, this could be automatically done with Maven. Find also in this section instructions to manually install in Eclipse, and under Linux. You can get more information about JGraphT on its public website, and more information about the classes the library provides in its Javadoc documentation available online: https://jgrapht.org/ https://jgrapht.org/javadoc/ https://jgrapht.org/javadoc-1.3.0/
2.2 GitLab-Student and Maven
A coursework starting point project is available as a repository on GitLab-Student. You should all be able to Fork this project. If you cannot access it, talk to your lecturer during your next Lab session
As JGraphT releases are published to the Maven Central Repository, this coursework project includes the necessary dependency in the Maven setting (pom.xml file).
< group Id > org . jgrapht </ group Id > < artifact Id >jgrapht - core </ artifact Id > < version >1.3.0 </ version >
On GitLab-Student, or on an IDE supporting Maven, you should not need to manually install JGraphT as it will be installed by Maven. The following subsections give you however instructions on how to manually install JGraphT. These instructions could be informative to read and help you understand better how such Java library works.
2.3 (Optional) Instructions to manually install JGraphT
JGraphT package download . Download the Open Source JGraphT graph library by following the instructions on: http://jgrapht.org/ The following instructions are for jgrapht-1.3.0 on a Unix machine using bash. . Decompress and extract the tarball (this will create a 88M jgrapht-1.3.0 directory), e.g. $ tar zx vf jgrapht -1.3.0. tar . gz . Delete the tarball to save 45M (47M for the zip file), e.g. $ rm jgrapht -1.3.0. tar . gz
In the following, we assume that the extracted jgrapht-1.3.0 directory is located at /path/to/your/login/path/to/
Setup for Eclipse integration To use and integrate JGraphT in Eclipse, you need to Configure the Java Build Path of your project. You will need to apply the following changes in Libraries: . Add the external archive jgrapht-core-1.3.0.jar . Once the archive is added, you can attach its sources by deploying its menu and edit Source attachment to point to the external directory location /path/to/your/login/path/to/jgrapht-1.3.0/source/jgrapht-core/src This will make the sources of JGraphT directly available within Eclipse for documentation and debugging purposes. . Similarly, you can add the documentation by editing Javadoc location path to be /path/to/your/login/path/to/jgrapht-1.3.0/javadoc/. This will make the documentation of JGraphT directly available within Eclipse.
Setup for command line compilation and execution . Add JGraphT’s core JAR file jgrapht-core-1.3.0.jar to your class path by adding the following commands at the end of your .profile file in your home directory. Alternatively, you could pass the additional class path information to javac and java with the -cp command line argument. The following line adds JGraphT’s core JAR to your class path (this could be repeated for other JGraphT JAR, to run JGraphT’s HelloJGraphT demo you will need to also include jgrapht-io-1.3.0.jar). export CLASSPATH =/ path / to / your/ login / path / to / jgrapht -1.3.0/ lib / jgrapht - core ê -1.3.0 . jar : $CLASSPATH Note that when you copy-paste these commands, you will need to edit the text lines your obtain to remove spaces and some line breaks. . Execute your new .profile for the setting to betaken into account, e.g. $ source ~/ . profile
3 Coursework Parts
Part A: Representing direct flights and Cheapest connections Week 8–9
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 to 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 cheapest 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
Cheapest path :
1. Edinburgh -> Dubai
2. Dubai -> Kuala Lumpur
Number of plane changes: 1
Cheapest path = £ 320Java hint: You can redefine the .toString() method in your classes to customise printing of information. by mid Week 9 Implement the main method your FlyingPlannerMainPartA program. This FlyingPlannerMainPartA does not need to use or implement the provided interfaces. No test is provided nor necessary for this part. You should aim to complete this part by mid Week 9.
Part B: Use provided flights dataset, add flight information Week 9–10 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 cheapest journey in a format similar to the following example. The key aspects are:
- A sequence of connecting flights (with cheapest),
- A total cost for the journey. An example journey for Part B (and Part C) might resemble the following when the departure city is Newcastle (NCL) and the destination Newcastle (NTL): 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 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 https://openflights.org/ 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, by mid Week 10 Implement the main method of your FlyingPlannerMainPartBC program and the methods of FlyingPlanner, Journey, Airport, Flight according to the provided interfaces.
Your FlyingPlanner class should past the Part B test cases of the provided FlyingPlannerProvidedTest JUnit test class. Implement additional test cases in FlyingPlannerTest. You should aim to complete this part by mid Week 10.
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 starting 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).
AirMiles scheme The travel agency also wants to reward customers giving them airmiles they can later spend in their online shop (shop not part of this coursework). These airmiles are calculated by multiplying the flight time (time on air only) by 3% 30% of the total cost of a journey. Airmiles can only be whole numbers. The system should ignore any decimal points. Implement a function to display the air mile points awarded per chosen flight. Interfaces to implement To complete this part, . your FlyingPlanner class should implement the IFlyingPlannerPartC<Airport,Flight> interface; . your Journey class should implement the IJourneyPartC<Airport,Flight> interface; . your Airport class should implement the IAirportPartC interface, . your Flight class should implement the IFlight interface, =ñ by mid Week 11 Implement the methods of FlyingPlanner, Journey, Airport, Flight according to the provided interfaces. Your FlyingPlanner class should past the Part C test cases of the provided FlyingPlannerProvidedTest JUnit test class. You may implement additional test cases in FlyingPlannerTest to help you. You should aim to complete this part by the end of week 11.
4 Coding Style
Your mark will be based partly on your coding style. Here are some recommendations: . Variable and method names should be chosen to reflect their purpose in the program. . Comments, indenting, and whitespace should be used to improve readability. . No variable declarations should appear outside methods (“instance variables”) unless they contain data which is to be maintained in the object from call to call. In other words, variables which are needed only inside methods, whose value does not have to be remembered until the next method call, should be declared inside those methods. . All variables declared outside methods (“instance variables”) should be declared private (not protected) to maximize information hiding. Any access to the variables should be done with accessors methods.
