c++ Assignment Problem Description: The Flying Traveller Airline Company (FTAir)

Question

c++ Assignment

Problem Description:

The Flying Traveller Airline Company (FTAir) wants a program to process customer requests to fly from some origin city to some destination city. For each customer, indicate whether a sequence of FTAir flights from the origin city to the destination city exists and produce the itinerary – sequence of flights. Input: Three input text files that specify all the flights information as follow:

• The names of cities that FTAir serves (at least 15 cities).

• Pairs of city names; each pair represents the origin and destination of one of FTAir’s flights.

• Pair of city names; each pair represents a request to fly from some origin city to some destination (at least 5 requests with different scenarios). Each request considered a one-way flight.

Rules:

• Find a path from origin city to destination city, if exists.

• Maintain information about the order in which it visits the cities.

• Do not visit a city more than once.

• If there are multiple paths, you may list them all and find least visited cities. (optional).

Scenario 1: Travel request from PEN to KBR goes through 3 flight sequences.

PEN -> KL
KL -> IPH
IPH -> KBR

Scenario 2: Travel request from JHB to KL is a non-stop flight (one sequence)

JHB -> KL

Scenario 3: Travel request from KL to JHB is not possible (no path)

No flight

Solutions methods: (2 in 1 program)
1. Use Stacks (implement using linked list)
2. Use Recursions

Reports:
• Explain the problems and describe your solutions using stacks and
recursions. It should be correct, efficient, informative, user friendly, flexible,
creative and robust by adding other necessary operations.
• Discuss the relationship between Stacks and Recursions methods in solving
this problem. Relate the way stack organizes the search for a sequence of
flights to the way a recursive algorithms organize the search. Highlight the
key aspects of their common strategy.

Explanation / Answer

To start with :

First of all we need a data structure to contain all the input text files. Let's say we have the name of the cities in an array, pair of cities (origin --> destination) in a 2D array and the reuqest also in a 2D array.

For a path in the request matrix to exits, it has to be served by our FTAir, so for every request we need to search the origin and destination in the array of cities and if both are a match then only we proceed to our next step.

After finding a match, we have to map the request origin to the flight origins i.e. we have to check whether or not there is any flight from the origin required, if not then again there is no possible path for the travel request.

But if there is a match, we put that origin on to a stack and check it's destination and compare it with the destination requested, if that is a match we have got a direct flight and if that isn't put it on to the stack and look for the destination as an origin in the flight's 2D array. Continue to go on with the procedure, until there is a match. But what if we visit a city twice? Keep a check on the data you enter in the stack, if duplication data found, abort !

But where is the recursion part? Well, the same thing can be implemented using recusion call. How? Make a function to check a given input as origin and another input as destination. If the origin matches but the destination doesn't match, make the recursive call for the destination of the matched origin.

Which one is better? Problem with recursion is if the destination isn't reached then stack overflow problem may arise. Recursion method has space requirement but it is just easy to handle. Stack using a linked list can help your program to grow or shrink to the needs of your origin --> destination. But it also uses extra memory.

EDIT : Also, what we can do is form a graph out of the data available and map it accordingly, say for example I have

INPUT 1

1. Kolkata (A)
2. Delhi (B)
3. Mumbai (C)
4. Kerala (D)
5. Bangalore (E)
6. Chicago (F)

and I have INPUT 2 as:

1. (A,B)
2. (C,D)
3. (D,E)
4. (B,C)

Now, to check for a request A to C, I can simply start a DFS(A), if I reach C, then yes and if I don't the answer is no flight !

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.