This assignment tasks you with devising all feasible flight routes for individuals desiring to travel between two distinct cities served by an airline, along with calculating the total incurred cost for the entire journey. To accomplish this, you'll utilize data from two input files to compute the trip plan and overall expenses. Figure $1-$ Sample Directed Graph

Sample Data: Here's an example of a flight data input file:

$4$

Dallas$|$Austin$|98|47$

Austin$|$Houston$|95|39$

Dallas$|$Houston$|101|51$

Austin$|$Chicago$|144|192$

The first line denotes the total number of data rows in the file. Each subsequent row contains two city names, the flight cost, and the flight duration, separated by a pipe symbol.

Requested Flight Plans: An example of a requested flight plans input file is provided below:

$2$

Dallas$|$Houston$|$T

Chicago$|$Dallas$|$C

The first line specifies the number of flight plans requested. Subsequent lines consist of pipe$-$delimited city pairs followed by a trailing character indicating sorting preference for the output flights by time $($T$)$ or cost $($C$).$ Your solution will identify all flight paths between these cities $($if any exist$)$ and calculate the total cost and time spent in the air. Output File: For each flight in the Requested Flight Plans file, your program will print the three most efficient flight plans based on the sorting preference $($time or cost$).$ If fewer than three possible plans exist, all of them should be output. If no flight plan is viable, an error message should be printed.

Example output:

Flight $1$: Dallas, Houston $($Time$)$

Path $1$: Dallas $->$ Houston. Time: $51$ Cost: $101\mathrm{.}00$

Path $2$: Dallas $->$ Austin $->$ Houston. Time: $86$ Cost: $193\mathrm{.}00$

Flight $2$: Chicago, Dallas $($Cost$)$

Path $1$: Chicago $->$ Austin $->$ Dallas. Time: $237$ Cost: $242\mathrm{.}00$

Path $2$: Chicago $->$ Austin $->$ Houston $->$ Dallas. Time: $282$ Cost: $340\mathrm{.}00$

Implementation Details and Requirements: For representing the structure of flights serviced by the company, you'll utilize a straightforward adjacency list data structure. Essentially, this structure consists of a linked list of linked lists. Each distinct city will have its own linked list, containing information about the cities reachable from it$.$ Below is an illustration of an adjacency list for the graph depicted in Figure $1,$ demonstrating this concept.

Figure $2$: Adjacency list representation of graph from Figure $1.$ Letter in node represents first letter of city name from Figure $1.$ The larger squares depicted on the left side represent a list of cities, with each city having its own node. Each node in this list points to another list representing cities reachable from the corresponding parent node. For instance, from city A$,$ flights are available to cities B and D$.$

To address this challenge, you'll need to conduct an exhaustive search of all flight paths. This will entail implementing an iterative backtracking algorithm, utilizing a stack. The stack will serve to track your progress during the search, remembering the current state and enabling backtracking in case a dead end is reached. This algorithmic approach will be covered in lecture, and it's recommended to supplement your understanding with additional research.

You're required to implement both a linked list class and a stack class. Your stack class could leverage functionality from the linked list class. Furthermore, your implementation should adhere to an objectoriented design and approach. It's essential to minimize the code within your main method. Note that merely bundling multiple methods within a single class does not constitute an object$-$oriented design; instead, ensure that your solution is structured around meaningful objects with clearly defined responsibilities and interactions. This assignment tasks you with devising all feasible flight routes for individuals desiring to travel between two distinct cities served by an airline, along with calculating the total incurred cost for the entire journey. To accomplish this, you'll utilize data from two input files to compute the trip plan and overall expenses.

$1.$ Origination and Destination Data: This file contains a series of city pairs denoting various flight legs that could be considered when formulating a flight plan. Each leg includes a corresponding dollar cost and travel time. It's assumed that flights are bi$-$directional for each pair in the file.

$2.$ Requested Flights: This file comprises a sequence of origin$/$destination city pairs. Your program's task is to determine the feasibility of each flight. If viable, it will output the flight plan along with the total cost to an output file. If not feasible, an appropriate error message will be generated.

The filenames for the input files as well as the output file will be provided via command line arguments.

Flight Data: Imagine a flight from Dallas to Paris. This could involve a direct flight or necessitate a layover, perhaps in Chicago. A layover in Chicago would entail two flight legs. The entirety of flights between cities served by our airline can be visualized as a dir