# plz help me by solving this problm

• 05-25-2006, 07:41 AM
sukumardas
plz help me by solving this problm
i got this assignment ,plz help me by solving this problm.the problem is like this. i have attached the problem as word document.

0. Introduction. The Ballarat Airline Company (BAC) wants a simple program to process customer requests to fly from some origin city to some destination city: For each customer request, the program has to indicate whether a sequence of BAC flights exists from the origin city to the destination city, and, if such a sequence exists, the program prints it.
The following figure represents the routs that BAC flies (for simplicity cities on the figure are denoted by C1, C2, …, C9):

Notice that not all BAC flights have return flights, for example there is a BAC flight from C1 to C2, but not a BAC flight from C2 to C1.

The algorithm for processing customer requests is described in the following section and uses stacks. You must “translate” the algorithm into Java, and create auxiliary Java classes as specified below.
1. The Main Algorithm. Let us assume that we have a request to find a sequence of flights from X to Y. The request must be processed in the following way:

I We create an empty stack;
II All cities are marked as “unvisited”;
III We mark city X as “visited” and push it onto the stack;
IV While the stack is not empty and top city in the stack is not the destination city Y:
• If there is some “unvisited” city adjacent to the top city, we mark it as “visited” and push it onto the stack
• Else we pop the stack
IV Return the stack. If the stack is not empty it contains the sequence of flights from X to Y. If the stack is empty, such sequence does not exist.

2. Generic classes Stack<T> and List<T >.
Create generic classes Stack<T> and List<T>. You need to make necessary changes to the classes Stack and List discussed in the lectures. Class Stack<T> must contain a method that prints contents of the stack.

3. Class City :Create a class City, which has the following instance variables:

• private String name; // name of the city
• private List<City> nextCities; // List of cities to which there is a flight from this
• private boolean visited; // the variable that shows whether the city has been //already visited during the request processing algorithm.

The class also must contain constructor(s) and get and set methods for the instance variables.
There also must be a method “public City getNextUnvisitedCity()” which returns some “unvisited” city from the nextCities list, if there is any, otherwise returns null.

4. Class RequestProcessor. This class has one instance variable: “private List<City> cities” – which refers to the list of City objects in the flight map;
A constructor that receives a parameter of List<City> type to initialize the instance variable;
And two methods:

• “public Stack<City> isPath(City originCity, City destinationCity)” – method implements the Main Algorithm described in section 1.
• main method, in which you create 9 cities according to the information given in the flight map (figure in section 0) and then process customer requests for three different pairs of cities (you can choose the pairs yourself).

• 05-25-2006, 02:27 PM
nspils
This is a directed graph problem. The algorithm is implementing a depth first search, looking for one or more path(s) from X to Y.

What part of the solution are you working on, first? Where are you stuck?
• 05-26-2006, 01:59 AM
sukumardas
i donot know how to begin n where to begin.
Quote:

Originally Posted by nspils
This is a directed graph problem. The algorithm is implementing a depth first search, looking for one or more path(s) from X to Y.

What part of the solution are you working on, first? Where are you stuck?

I donot know how to proceed towards the solution atall. but i know DFS algorithm. as i m new to Java, n got it as assignment. plz just give hint to solve. how i proceed. i donot want fully code , but just a pseudocode.which will help me to solve .
• 05-26-2006, 07:24 AM
nspils
You have the pseudocode, already. I am not going to write it for you. I will look over your shoulder while you write it, however.