Overview Purpose: The purpose of this assignment is to make you…

Question Answered step-by-step Overview Purpose: The purpose of this assignment is to make you… OverviewPurpose: The purpose of this assignment is to make you practice implementing some graph algorithms and to see how they can be used in a somewhat practical way.Feel free to use as much code as you need from Lab 8 and Lab 9.DetailsYou are to implement a simple information program for a fictional airline.. Your program should be able to handle the following queries as specified in AirlineInterface.java: Load from a file (whose name is input by the user) a list of all of the service routes that your airline runs. These routes include the cities served and the various non-stop destinations from each city. Clearly, you will be interpreting these routes as a graph with the cities being the vertices and the non-stop trips being the edges. To keep things simple, assume that all routes are bidirectional, so that you can use an undirected graph (this is not necessarily an incorrect assumption, as airlines most often fly non-stop routes in both directions). Alternatively, you could use a directed graph, with two edges (one for each direction) for each trip. You can think of these as the current active routes, which would be updated periodically in case a route is cancelled or perhaps snow closes an airport somewhere. The routes (edges) should have 2 different weights: one weight based on the distance in miles between the cities and the other based on the price of a ticket between the cities. There are two example input files in the repository: a4data1.txt and a4data2.txt. Your program may be tested on other data files./** * reads the city names and the routes from a file * @param fileName the String file name * @return true if routes loaded successfully and false otherwise */public boolean loadRoutes(String fileName); Return a set of all city names served by the Airline./** * returns the set of city names in the Airline system * @return a (possibly empty) Set of city names */public Set retrieveCityNames(); Return a set of all non-stop Routes out of a given city. Please check Route.java for the specification of the Route objects./** * returns the set of direct routes out of a given city * @param city the String city name * @return a (possibly empty) Set of Route objects representing the direct routes out * of city * @throws CityNotFoundException if the city is not found in the Airline * system */public Set retrieveDirectRoutesFrom(String city) throws CityNotFoundException; Allow for each of the three “shortest path” searches below. If multiple paths “tie” for the shortest, you should return any one of them. a. Shortest path based on number of hops (individual segments) from the source to the destination. This option could be useful to passengers who prefer fewer segments for one reason or other (e.g., traveling with small children). /** * finds fewest-stops path(s) between two cities * @param source the String source city name * @param destination the String destination city name * @return a (possibly empty) Set> of fewest-stops paths. Each path is an * ArrayList of city names that includes the source and destination * city names. * @throws CityNotFoundException if any of the two cities are not found in the * Airline system */ public Set> fewestStopsItinerary(String source, String destination) throws CityNotFoundException; b. Shortest path based on total miles (one way) from the source to the destination. Assuming distance and time are directly related, this could be useful to passengers who are in a hurry. It would also appeal to passengers who want to limit their carbon footprints. /** * finds shortest distance path(s) between two cities * @param source the String source city name * @param destination the String destination city name * @return a (possibly empty) Set> of shortest-distance paths. Each path is * an ArrayList of Route objects that includes a Route out of source and into destination. * @throws CityNotFoundException if any of the two cities are not found in the * Airline system */ public Set> shortestDistanceItinerary(String source, String destination) throws CityNotFoundException; c. Shortest path from a source city to a destination city through a third (transit) city. In other words, “What is the shortest path from A to B given that I want to stop at C for a while?” /** * finds shortest distance path(s) between two cities going through * a third city * @param source the String source city name * @param transit the String transit city name * @param destination the String destination city name * @return a (possibly empty) Set> of shortest-distance paths. Each path is * an ArrayList of Route objects that includes a Route into source, into and out of transit, and * into destination. * @throws CityNotFoundException if any of the three cities are not found in the * Airline system */ public Set> shortestDistanceItinerary(String source, String transit, String destination) throws CityNotFoundException; Add a new city to be serviced by the Airline./** * adds a city to the Airline system * @param city the city name * @return true if city added successfully and false if the city already exists */public boolean addCity(String city); Add a new route to the schedule. Both cities have to already exist with no prior route between them. Clearly, adding a new route to the schedule may affect the searches and algorithms indicated above./** * adds a direct route between two existing cities to the Airline system * @param source the source city name * @param destination the destination city name * @param distance the int distance between the two cities in miles * @param price the double ticket price in dollars * @return true if route added successfully and false if a route already * exists between the two cities * @throws CityNotFoundException if any of the two cities are not found in the * Airline system */public boolean addRoute(String source, String destination, int distance, double price) throws CityNotFoundException; Update an already existing route between two cities. Clearly, updating a route in the schedule may affect the searches and algorithms indicated above./** * updates a direct route between two existing cities in the Airline system * @param source the String source city name * @param destination the String destination city name * @param distance the int distance between the two cities in miles * @param price the double ticket price in dollars * @return true if route updated successfully and false if no route already * exists between the two cities * @throws CityNotFoundException if any of the two cities are not found in the * Airline system */public boolean updateRoute(String source, String destination, int distance, double price) throws CityNotFoundException;. You must encapsulate the functionality of your airline in a single, cohesive class named AirlineSystem.java, which has to implements the AirlineInterface. You must represent the graph using adjacency lists. The cities should minimally have a string for a name and any other information you want to add. The edges will have multiple weights (distance, price). Again, you may use the code from Lab 8 and Lab 9.. You must use the algorithms and implementations discussed in class for your queries. For example, for the shortest distance paths you must use Dijkstra’s algorithm and to obtain the shortest-hops path you must use breadth-first search. import java.util.Set;import java.util.ArrayList;final public class AirlineSystem implements AirlineInterface { public boolean loadRoutes(String fileName) { } public Set retrieveCityNames() { } public Set retrieveDirectRoutesFrom(String city) throws CityNotFoundException { return result; } public Set> fewestStopsItinerary(String source, String destination) throws CityNotFoundException { return null; } public Set> shortestDistanceItinerary(String source, String destination) throws CityNotFoundException { return null; } public Set> shortestDistanceItinerary(String source, String transit, String destination) throws CityNotFoundException { return null; } public boolean addCity(String city){ return false; } public boolean addRoute(String source, String destination, int distance, double price) throws CityNotFoundException { return false; } public boolean updateRoute(String source, String destination, int distance, double price) throws CityNotFoundException { return false; }}import java.util.Set;import java.util.ArrayList;public interface AirlineInterface { /** * reads the city names and the routes from a file * @param fileName the String file name * @return true if routes loaded successfully and false otherwise */ public boolean loadRoutes(String fileName); /** * returns the set of city names in the Airline system * @return a (possibly empty) Set of city names */ public Set retrieveCityNames(); /** * returns the set of direct routes out of a given city * @param city the String city name * @return a (possibly empty) Set of Route objects representing the * direct routes out of city * @throws CityNotFoundException if the city is not found in the Airline * system */ public Set retrieveDirectRoutesFrom(String city) throws CityNotFoundException; /** * finds fewest-stops path(s) between two cities * @param source the String source city name * @param destination the String destination city name * @return a (possibly empty) Set> of fewest-stops paths. * Each path is an ArrayList of city names that includes the source * and destination city names. * @throws CityNotFoundException if any of the two cities are not found in the * Airline system */ public Set> fewestStopsItinerary(String source, String destination) throws CityNotFoundException; /** * finds shortest distance path(s) between two cities * @param source the String source city name * @param destination the String destination city name * @return a (possibly empty) Set> of shortest-distance * paths. Each path is an ArrayList of Route objects that includes a * Route out of the source and a Route into the destination. * @throws CityNotFoundException if any of the two cities are not found in the * Airline system */ public Set> shortestDistanceItinerary(String source, String destination) throws CityNotFoundException; /** * finds shortest distance path(s) between two cities going through a third * city * @param source the String source city name * @param transit the String transit city name * @param destination the String destination city name * @return a (possibly empty) Set> of shortest-distance * paths. Each path is an ArrayList of city names that includes * a Route out of source, into and out of transit, and into destination. * @throws CityNotFoundException if any of the three cities are not found in * the Airline system */ public Set> shortestDistanceItinerary(String source, String transit, String destination) throws CityNotFoundException; /** * adds a city to the Airline system * @param city the city name * @return true if city added successfully and false if the city already * exists */ public boolean addCity(String city); /** * adds a direct route between two existing cities to the Airline system * @param source the source city name * @param destination the destination city name * @param distance the int distance between the two cities in miles * @param price the double ticket price in dollars * @return true if route added successfully and false if a route already * exists between the two cities * @throws CityNotFoundException if any of the two cities are not found in the * Airline system */ public boolean addRoute(String source, String destination, int distance, double price) throws CityNotFoundException; /** * updates a direct route between two existing cities in the Airline system * @param source the String source city name * @param destination the String destination city name * @param distance the int distance between the two cities in miles * @param price the double ticket price in dollars * @return true if route updated successfully and false if no route already * exists between the two cities * @throws CityNotFoundException if any of the two cities are not found in the * Airline system */ public boolean updateRoute(String source, String destination, int distance, double price) throws CityNotFoundException;}import java.util.ArrayList;import java.util.Set;import java.util.Scanner;import java.io.IOException;final public class AirlineTest { private AirlineInterface airline; private Scanner scan; /** * Test client. */ public static void main(String[] args) throws IOException { new AirlineTest(); } public AirlineTest(){ airline = new AirlineSystem(); scan = new Scanner(System.in); while(true){ try{ switch(menu()){ case 1: readGraph(); break; case 2: printGraph(); break; case 3: shortestHops(); break; case 4: shortestDistance(); break; case 5: shortestDistanceWithTransit(); break; case 6: addCity(); break; case 7: addRoute(); break; case 8: updateRoute(); break; case 9: System.exit(0); break; default: System.out.println(“Incorrect option.”); } } catch (CityNotFoundException e){ System.out.println(“City not found. Please choose from the list ” + “and check spelling: ” + e.getMessage()); } catch (NullPointerException e){ System.out.println(“Null pointer exception ” + e.getMessage()); } System.out.print(“Please press ENTER to continue …”); scan.nextLine(); } } private int menu(){ int choice = -1; System.out.println(“*********************************”); System.out.println(“Welcome to Fifteen O’One Airlines!”); System.out.println(“1. Read routes from a file.”); System.out.println(“2. Display all routes.”); System.out.println(“3. Compute shortest path(s) based on number of stops.”); System.out.println(“4. Compute shortest path(s) based on distance.”); System.out.println(“5. Compute shortest path(s) based on distance ” + “with a specified transit.”); System.out.println(“6. Add a city.”); System.out.println(“7. Add a route.”); System.out.println(“8. Update a route.”); System.out.println(“9. Exit.”); System.out.println(“*********************************”); while(true){ System.out.print(“Please choose a menu option (1-9): “); try{ choice = Integer.parseInt(scan.nextLine()); break; } catch(Exception e){ System.out.println(“Invalid input: ” + e.getMessage()); } } return choice; } private void readGraph() { System.out.println(“Please enter filename:”); String fileName = scan.nextLine(); if(airline.loadRoutes(fileName)){ System.out.println(“Data imported successfully.”); } else { System.out.println(“Error importing data from ” + fileName); } } private void printGraph() throws CityNotFoundException { for(String city: airline.retrieveCityNames()){ System.out.print(city + “: “); for (Route r : airline.retrieveDirectRoutesFrom(city)) { System.out.print(r.destination + “(” + r.distance + ” miles, $” + r.price + “) “); } System.out.println(); } } private void shortestHops() throws CityNotFoundException { for(String city : airline.retrieveCityNames()){ System.out.println(city); } System.out.print(“Please enter source city: “); String source = scan.nextLine(); System.out.print(“Please enter destination city: “); String destination = scan.nextLine(); Set> shortestSet = airline.fewestStopsItinerary(source, destination); System.out.println(“Found ” + shortestSet.size() + ” path(s):”); for(ArrayList shortest : shortestSet){ System.out.print(“The shortest path from ” + source + ” to ” + destination + ” has ” + (shortest.size()-2) + ” stop(s): “); for(String r : shortest){ System.out.print(r + ” “); } System.out.println(); } } private void shortestDistance() throws CityNotFoundException { for(String city : airline.retrieveCityNames()){ System.out.println(city); } System.out.print(“Please enter source city: “); String source = scan.nextLine(); System.out.print(“Please enter destination city: “); String destination = scan.nextLine(); Set> shortestSet = airline.shortestDistanceItinerary(source, destination); System.out.println(“Found ” + shortestSet.size() + ” path(s):”); for(ArrayList shortest : shortestSet){ int totalDistance = 0; for(Route r : shortest){ totalDistance += r.distance; } System.out.print(“The shortest path from ” + source + ” to ” + destination + ” has ” + totalDistance + ” miles: “); System.out.print(source); for(Route r : shortest){ System.out.print(” ” + r.distance + ” ” + r.destination); } System.out.println(); } } private void shortestDistanceWithTransit() throws CityNotFoundException { for(String city : airline.retrieveCityNames()){ System.out.println(city); } System.out.print(“Please enter source city: “); String source = scan.nextLine(); System.out.print(“Please enter destination city: “); String destination = scan.nextLine(); System.out.print(“Please enter transit city: “); String transit = scan.nextLine(); Set> shortestSet = airline.shortestDistanceItinerary(source, transit, destination); System.out.println(“Found ” + shortestSet.size() + ” path(s):”); for(ArrayList shortest : shortestSet){ int totalDistance = 0; for(Route r : shortest){ totalDistance += r.distance; } System.out.print(“The shortest path from ” + source + ” to ” + destination + ” passing by ” + transit + ” has ” + totalDistance + ” miles: “); System.out.print(source); for(Route r : shortest){ System.out.print(” ” + r.distance + ” ” + r.destination); } System.out.println(); } } private void addCity() { System.out.print(“Please enter city name: “); String city = scan.nextLine(); if(!airline.addCity(city)){ System.out.println(“Failed to add city.”); } else { System.out.println(“City successfully added.”); } } private void addRoute() throws CityNotFoundException { for(String city : airline.retrieveCityNames()){ System.out.println(city); } System.out.print(“Please enter source city: “); String source = scan.nextLine(); System.out.print(“Please enter destination city: “); String destination = scan.nextLine(); int distance = 0; while(true){ try{ System.out.print(“Please enter distance: “); distance = Integer.parseInt(scan.nextLine()); break; } catch(Exception e){ System.out.println(“Invalid input: ” + e.getMessage()); } } double price = 0; while(true){ try{ System.out.print(“Please enter price: “); price = Double.parseDouble(scan.nextLine()); break; } catch(Exception e){ System.out.println(“Invalid input: ” + e.getMessage()); } } if(!airline.addRoute(source, destination, distance, price)){ System.out.println(“Failed to add route.”); } else { System.out.println(“Route successfully added.”); } } private void updateRoute() throws CityNotFoundException { for(String city : airline.retrieveCityNames()){ System.out.println(city); } System.out.print(“Please enter source city: “); String source = scan.nextLine(); System.out.print(“Please enter destination city: “); String destination = scan.nextLine(); int distance = 0; while(true){ try{ System.out.print(“Please enter distance: “); distance = Integer.parseInt(scan.nextLine()); break; } catch(Exception e){ System.out.println(“Invalid input: ” + e.getMessage()); } } double price = 0; while(true){ try{ System.out.print(“Please enter price: “); price = Double.parseDouble(scan.nextLine()); break; } catch(Exception e){ System.out.println(“Invalid input: ” + e.getMessage()); } } if(!airline.updateRoute(source, destination, distance, price)){ System.out.println(“Failed to update route.”); } else { System.out.println(“Route successfully updated.”); } }}import java.util.Objects;final public class Route { public String source; public String destination; public int distance; public double price; public Route(String source, String destination, int distance, double price){ this.source = source; this.destination = destination; this.distance = distance; this.price = price; } @Override public boolean equals(Object other){ if (other instanceof Route){ Route otherRoute = (Route) other; return equalEndPoints(otherRoute) && distance == otherRoute.distance && price == otherRoute.price; } return false; } private boolean equalEndPoints(Route otherRoute){ return (source.equals(otherRoute.source) && destination.equals(otherRoute.destination)) ||(source.equals(otherRoute.destination) && destination.equals(otherRoute.source)); } @Override public int hashCode(){ return Objects.hash(source.hashCode() + destination.hashCode(), distance, price); } @Override public String toString(){ return source + ” (” + distance + ” miles, $” + price + “) ” + destination; }}Data:9PittsburghErieAltoonaJohnstownHarrisburgPhiladelphiaScrantonReadingAllentown1 2 127 200.001 4 66 125.001 5 205 125.001 6 306 550.003 4 43 150.003 5 134 225.005 6 105 175.005 8 59 200.006 7 125 275.006 9 62 150.008 9 35 175.00 Computer Science Engineering & Technology Java Programming CS 1501 Share QuestionEmailCopy link Comments (0)