C++ PROBLEM Complete the solution to the HPAir problem. The input to the program

Question

C++ PROBLEM

Complete the solution to the HPAir problem. The input to the program consists of three text fi les, as
follows:
cityFile Each line contains the name of a city that HPAir serves. The names are in
alphabetical order.
flightFile Each line contains a pair of city names that represent the origin and destination
of one of HPAir’s fl ights.
requestFile Each line contains a pair of city names that represent a request to fl y from
some origin to some destination.

You can make the following assumptions:
• Each city name contains at most 15 characters. Pairs of city names are separated by a comma.
• HPAir serves at most 20 cities.
• The input data is correct.
For example, the input fi les could appear as
cityFile: Albuquerque
Chicago
San Diego

flightFile: Chicago, San Diego
Chicago, Albuquerque
Albuquerque, Chicago

requestFile: Albuquerque, San Diego
Albuquerque, Paris
San Diego, Chicago

For this input, the program should produce the following output:
Request is to fly from Albuquerque to San Diego.
HPAir flies from Albuquerque to San Diego.
Request is to fly from Albuquerque to Paris.
Sorry. HPAir does not serve Paris.
Request is to fly from San Diego to Chicago.
Sorry. HPAir does not fly from San Diego to Chicago.
Begin by implementing the ADT fl ight map as the C++ class Map . Use the stack version of isPath . Because
getNextCity is the primary operation that the search algorithm performs on the fl ight map, you should choose
an implementation that will effi ciently determine which cities are adjacent to a given city. If there are n cities
numbered 1, 2, . . ., n , you can use n chains of linked nodes to represent the fl ight map. You place a node on list
i for city j if and only if there is a directed path from city i to city j . Such a data structure is called an adjacency
list; Figure 6-14 illustrates an adjacency list for the fl ight map in Figure 6-6 . Chapter 20 discusses adjacency
lists further when it presents ways to represent graphs. At that time, you will learn why an adjacency list is a
good choice for the present program.
To simplify reading the input text fi les, defi ne a class that includes the following methods:
// Returns a name from the next line in a text file.
+getName(): string
// Returns a pair of two names from the next line in a text file.
+getNamePair(): Pair

Explanation / Answer

//HpMap.h

#ifndef _HPMAP_H
#define _HPMAP_H
// Include the required header files
#include "ListP.h"
#include "StackP.h"
const int HPMAX_MAP = 20;
using namespace std;
class HpMap
{
   // Declare the required method protocols
   public:  
       HpMap();
        void HPreadFlightMap(string HpcityFileName, string HpflightFileName);
       void HPdisplayFlightMap() const;
       void HPdisplayAllCities() const;
       void HPdisplayAdjacentCities(int HPcity) const;
       void HPmarkVisited(int HPcity);
       void HPunvisitAll();
       bool HPisVisited(int HPcity) const;
       void HPinsertAdjacent(int HPaCity, int HPadjCity);
       bool HPgetNextCity(int HPfromCity, int &HPnextCity) const;
       bool HPisPath(int HPoriginCity, int HPdestinationCity);
       string HPcityName(int HPnumber) const;
  
   // Declare the required variables
   private:
      string HPnamesOfCities[HPMAX_MAP];
       bool HPmark[HPMAX_MAP];
       List HPadjList[HPMAX_MAP];
       int HPnumberOfCities;
       int HPcityNumber(string HPname) const;
  
};

#endif /* _MAP_H */


//HpMAP.CPP

#include <string>
#include <iostream>
#include <fstream>
#include "HpMap.h"

using namespace std;

// constructor
HpMap::HpMap() : HPnumberOfCities(0){}

// Method to read the flight data
void HpMap::HPreadFlightMap(string HpcityFileName, string HpflightFileName)
{
    string HPname1;
    string HPname2;

    ifstream HPinClientFile1;
    HPinClientFile1.open(HpcityFileName.c_str());

    while(HPinClientFile1 >> HPname1)
        HPnamesOfCities[HPnumberOfCities++] = HPname1;

    HPinClientFile1.close();

    HPdisplayAllCities();

    ifstream HPinClientFile2(HpflightFileName.c_str());

    while(getline(HPinClientFile2, HPname1,','))
    {
        getline(HPinClientFile2, HPname2);
        HPinsertAdjacent(HPcityNumber(HPname1), HPcityNumber(HPname2));
    }

    HPinClientFile2.close();

    HPdisplayFlightMap();

}

// Method to insert the adjacent
void HpMap::HPinsertAdjacent(int HPaCity, int HPadjCity)
{
    if(HPaCity >= 0 && HPadjCity >= 0)
        HPadjList[HPaCity].insert(1, HPadjCity);
}

// Method to mark node as visited
void HpMap::HPmarkVisited(int HPaCity)
{
    HPmark[HPaCity] = true;
}

// Method to mark the node as unvisited
void HpMap::HPunvisitAll()
{
    for(int lp = 0; lp < HPMAX_MAP; lp++)
        HPmark[lp] = false;
}

// Method to check weather nodes is visited
bool HpMap::HPisVisited(int HPaCity) const
{
    return HPmark[HPaCity];
}

// Method to check next city
bool HpMap::HPgetNextCity(int HPfromCity, int &HPnextCity) const
{
    int HPadjCity;

    for(int lp = 1; lp <= HPadjList[HPfromCity].getLength(); lp++)
    {
        HPadjList[HPfromCity].retrieve(lp, HPadjCity);

        if(!HPisVisited(HPadjCity)) {
            HPnextCity = HPadjCity;
            return true;
        }
    }

    return false;
}

// Method to get city name
string HpMap::HPcityName(int HPnumber) const
{
    return HPnamesOfCities[HPnumber];
}

// Method to get city number
int HpMap::HPcityNumber(string HPname) const
{
    for(int lp = 0; lp < HPnumberOfCities; lp++)
    {
        if(HPname == HPnamesOfCities[lp])
            return lp;
    }

    return -1;
}

// Method to display adjacent city
void HpMap::HPdisplayAdjacentCities(int HPcity) const
{
    int HPadjCity;

    for(int lp = 1; lp <= HPadjList[HPcity].getLength(); lp++)
    {
        HPadjList[HPcity].retrieve(lp, HPadjCity);
        cout << HPnamesOfCities[HPcity] << " -> " << HPnamesOfCities[HPadjCity] << endl;
    }

}

// Method to display flight map
void HpMap::HPdisplayFlightMap() const
{
    int HPadjCity;

    cout << "The map is: " << endl;

    for(int lp = 0; lp < HPnumberOfCities; lp++)
    {
        HPdisplayAdjacentCities(lp);
    }
}

// Method to display all cities
void HpMap::HPdisplayAllCities() const
{
    for(int lp = 0; lp < HPnumberOfCities; lp++)
    {
        cout << lp << ": " << HPcityName(lp) << endl;
    }
}

// Method to check it is path or not
bool HpMap::HPisPath(int HPoriginCity, int HPdestinationCity)
{
    Stack aStack;
    int topCity, HPnextCity;
    bool success;

    HPunvisitAll();

    try
    {
        aStack.push(HPoriginCity);
        HPmarkVisited(HPoriginCity);

        aStack.getTop(topCity);

        while(!aStack.isEmpty() && (topCity != HPdestinationCity))
        {
            success = HPgetNextCity(topCity, HPnextCity);

            if(!success)
            {
                aStack.pop();
            }
            else
            {
                aStack.push(HPnextCity);
                HPmarkVisited(HPnextCity);
            }

            if(!aStack.isEmpty())
                aStack.getTop(topCity);

        }

        if(aStack.isEmpty())
            return false;
        else
            return true;
    }
    catch (StackException e)
    {
        cout << e.what() << endl;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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