The HPAir problem was the subject of Programming Problems 11 through 14 of Chapter 6. Revise these problems by implementing the ADT flight map as a derived class of the graph class that you wrote for Programming Problem 3.

Programming Problem 3:

Repeat Programming Problems 1 and 2, but allow the graph to be either weighted or unweighted and either directed or undirected.

Programming Problems 1:

Write a C++ class derived from Graph Interface, as given in Listing 20-1. Use an adjacency matrix to represent the graph.

Programming Problems 2:

Repeat the previous programming problem, but represent the graph using an adjacency list instead of an adjacency matrix.

Chapter 6 Programming Problems 11:

Complete the solution to the HPAir problem. The input to the program consists of three text fi les, as follows:

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

For this input, the program should produce the following output:

Begin by implementing the ADT flight map as the C++ class Map. Use the stack version of is Path. Because get Next City is the primary operation that the search algorithm performs on the flight map, you should choose an implementation that will efficiently 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 flight 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 flight 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, define a class that includes the following methods:

Chapter 6 Programming Problems 14:

What modifications to the previous programming problem are required to find a least-cost trip for each request? How can you incorporate time considerations into the problem?