Graph Word Chains

Instructions

For this project you will be designing and implementing a system, in either C or C++, to determine if it is possible to transform one word into another by repeatedly altering single letters and having all interim strings still be considered words in some language.

Requirements

This assignment has two parts: a design portion and an implementation portion. Design Document.

For the design portion, you must generate documentation, in PDF format, describing your system and design process. The purpose of this is for you to explain not just what your system is doing, and how it is doing it, but why. You will need to justify your design decisions in a concise, informative manner. Justifications such as "I did this because it was easy" are not sufficient, as you should actually explain why a particular data structure or algorithm was more efficient, effective, or optimal. Additionally, commented code, while sometimes helpful in small examples, is not a sufficient explanation in and of itself. Your explanations and justifications are expected to be presented in prose and in paragraph format, i.e. not bulleted lists. Further, part of the evaluation of your design document is the apparent amount of thought and effort that went into its creation. This document should be divided into four main parts each with an appropriate header.

In the first part, you should describe your design process. Did you work out the algorithm on paper or a whiteboard before hand?

Did you draw UML diagrams of the system? Did you create a small prototype?

Did you simply start coding away and then recode once or twice with newfound understanding?

In a few paragraphs, describe in detail how you went about designing the system, and be sure to provide sufficient justification of your methodology.

For the second part, you should describe the data structures you used in your system. What, if any, objects or structs did you create to store data? How did you organize and manage them? What types of formal data structures did you make use of (trees, graphs, arrays, hashes, etc)? In a few paragraphs, describe in detail how you stored the various data elements in your system and be sure to provide sufficient justification of your methodology.

For the third part, you should describe functionality of your system. How is data moved and transformed? How is it read in? How is it output? What are the various major functions you constructed and how do they work? In a few paragraphs, describe in detail how your system works and be sure to provide sufficient justification of your methodology. You might also consider including diagrams to more easily visualize how all the pieces fit together.

Implementation

Your program must provide the following functionality and adhere to the following constraints:

• Allow the user to choose the file that contains all of the words in the language
  • Each word will be on a separate line
  • All words will be lowercase and contain no symbols or spaces.
  • The word list should be stored as a undirected graph, where each word is represented by a single node and two nodes are considered adjacent if they differ by exactly one letter
  • the graph should be constructed as either an adjacency list or an adjacency matrix.
• Allow the user to manually input two words to determine if it is possible to transform one into the other.
  • The first word is the source word and the second word is the destination word
  • You must use the graph to determine if the transformation is possible
  • You may not use any of the searching algorithms provided by any C/C++ libraries, the STL, or the Boost libraries. You must write your own searching algorithm.
• Your program should output the in-order list of transformations, starting with the source and ending with the destination, to get from the source to the destination words, along with the total number of interim words required.
  • Each subsequent word in the list must differ by only one letter
  • Additionally, your system must find at least one shortest path (i.e. the smallest number of transformations) between the source and destination nodes. There could be multiple shortest paths, but you need only output one.
• Your code must be well commented.
• You must provide a short README file which includes your name and explains how to compile and run your program.
• Additionally, you may write a makefile if you want your code to compile with additional flags.