1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
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: bool success;
16: Stack aStack;
17: unvisitAll(); // Clear marks on all cities
18: // Push origin city onto aStack and mark it as visited
19: aStack.push(originCity);
20: markVisited(originCity);
21:
22: City topCity = aStack.peek();
23: while (!aStack.isEmpty() && (topCity != destinationCity))
24: {
25: // The stack contains a directed path from the origin city
26: // at the bottom of the stack to the city at the top of
27: // the stack
28:
29: // Find an unvisited city adjacent to the city on the
30: // top of the stack
31: City nextCity = getNextCity(topCity, nextCity);
32:
33: if (nextCity == NO_CITY)
34: aStack.pop(); // No city found; backtrack
35: else // Visit city
36: {
37: aStack.push(nextCity);
38: markVisited(nextCity);
39: } // end if
40:
41: if (!aStack.isEmpty())
42: topCity = aStack.peek();
43: } // end while
44:
45: return !aStack.isEmpty();
46: } // end isPath