A word ladder is a sequence of words such that each word differs from the previous word in only one position. In graph theoretic terminology one can think of this as a path with the vertices being the words and the transition being the letters. For example, the following is a word ladder starting at ``words'' and ending at ``graph''.
words wolds golds goads grads grade grape graph
The distance between adjacent vertices is the absolute value of the difference in the positions of the alphabet of the non-matching letter. For example, the distance between ``words'' and ``wolds'' is the position of r minus the position of l, which is 6. The length of a path is the maximum distance between consecutive words in that path. So the above word ladder is the maximum of 6, 14, 11, 3, 14, 12, 3 = 14. In this assignment we will only be interested in 5 letter words. The official list of 5 letter words for this assignment can be found in a file words.dat. The * and + symbols, and the numbers after the words have no significance for this assignment. You will write a sequence of programs for this data.
Program 1: Your program should read in the initial graph from the file adjlist.txt. The format of this file should be self explanatory. Your program should then create the edge weighted graph described above. You must represent the graph as an adjacency list. You should then find the connected components of the graph. You should output the collection of words in each connected component as you explore that connected component. Each word should only be output once. At the end of the program you should output the number of connected components that your program found. Your program must run in linear time.
Program 2: This program will extend program 1. The diameter of a connect component is the maximum length of a shortest path between vertices s and t in the connected component. For each connected component, you should output:
You can find the diameter of a connected component by applying Dijkstra's (priority first) Shortest Path algorithm starting from every vertex s in the connected component. Note again that path length here is the maximum of the edge weights, not the sum of the edge weights. You should then implement a variation of Dijkstra's algorithm to find the shortest paths. Since the range of possible keys in the priority-queue (boundary) is small, [1 25], you should use the following non-standard implementation of a priority queue. Your priority queue PQ should be a 1-dimensionary array of size about 26. The ith array entry PQ[i] should be a doubly linked list of those vertices with key equal to i. You will need a separate array Val, whereVal[i] gives the value of the key for vertex i. You will also need another array Position, where Position[i] is a pointer to the node holding the vertex i in one of the doubly linked lists pointed to by entry in PQ. These data structures will allow you to implement DeleteMinimum and DecreaseKey in constant time per operation.
There is no write-up required for this assignment. Just turn in your programs, the output of your programs, and the assignment information sheet.