1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: /** Tests whether a sequence of flights exists between two cities.
5: Nonrecursive stack version.
6: @pre originCity and destinationCity both exist in the flight map.
7: @post Cities visited during the search are marked as visited
8: in the flight map.
9: @param originCity The origin city.
10: @param destinationCity The destination city.
11: @return True if a sequence of flights exists from originCity
12: to destinationCity; otherwise returns false. */
13: bool Map::isPath(City originCity, City destinationCity)
14: {
15: Stack cityStack;
16:
17: unvisitAll(); // Clear marks on all cities
18:
19: // Push origin city onto cityStack and mark it as visited
20: cityStack.push(originCity);
21: markVisited(originCity);
22:
23: City topCity = cityStack.peek();
24: while (!cityStack.isEmpty() && (topCity != destinationCity))
25: {
26: // The stack contains a directed path from the origin city
27: // at the bottom of the stack to the city at the top of the stack
28:
29: // Find an unvisited city adjacent to the city on the top of the stack
30: City nextCity = getNextCity(topCity);
31:
32: if (nextCity == NO_CITY)
33: cityStack.pop(); // No city found; backtrack
34: else // Visit city
35: {
36: cityStack.push(nextCity);
37: markVisited(nextCity);
38: } // end if
39:
40: if (!cityStack.isEmpty())
41: topCity = cityStack.peek();
42: } // end while
43:
44: return !cityStack.isEmpty();
45: } // end isPath