In class, we discussed two different applications of state space search: (1) finding a flight path between two cities and (2) generating a word ladder between two words. For this assignment, you will write your own classes that encapsulate domain-specific content for these two problems and utilize the general-purpose code for performing depth-first and breadth-first searches (found in AdjacencyGraph and PathFinder).
Define a class named FlightGraph that implements the AdjacencyGraph interface. Your class should have a constructor that takes a file name as input, and reads flight info from that file into an internal data structure. Your choice of data structure should make it possible to access all flights from a given city in no worse than O(log C + F) time, where C is the total number of cities and F is the number of flights leaving the specified city. Each line of the input file will consist of two city names (with no whitespace in a name), designating a flight between those two cities. For example, the first line in the sample file flights.txt designates a flight from Omaha to Chicago.
Using your FlightGraph class and the flights.txt data file, report the lengths of flight paths between the following cities:
| Departure - Arrival | # of flights using DFS | approx time using DFS | # of flights using BFS | approx time using BFS |
|---|---|---|---|---|
| Omaha - Lincoln | ||||
| Lincoln - Omaha | ||||
| Omaha - L.A. | ||||
| L.A - Omaha. | ||||
| Miami - Omaha | ||||
| Orange_County - Lincoln |
Note: your timings do not need to be exact. Possible answers include: instantaneous, less than a second, around a second, several seconds, less than a minute, I gave up after a minute, and the program died (out of memory).
The DictionaryGraph class discussed in class suffices for simple word ladder problems. However, it is grossly inefficient, requiring O(D) time to find adjacent words, where D is the size of the entire dictionary. Reimplement the class so that it performs the same functionality but using more efficient data structures. In particular, it must be able to find all adjacent words (i.e., words that differ from the given word by one letter) in no worse than O(log D + W) time, where D is the size of the dictionary and W is the number of adjacent words.
Using your new DictionaryGraph class and the smallDictionary.txt dictionary file, report the lengths of the word ladders between the following words:
| Start - End | # of words using DFS | approx time using DFS | # of words using BFS | approx time using BFS |
|---|---|---|---|---|
| reed - head | ||||
| reed - king | ||||
| shade - white | ||||
| sleep - snore | ||||
| treats - stared | ||||
| white - house |