Given a list L of words, one can define an undirected graph, called a WordGraph on the set of words as follows. We have one vertex for each word, and an edge between two words word1 and word2 if one can transform one of the words to the other via a character insertion or a character substitution.

For example, suppose L = [pain, gain, pan, span, gait, wait]. In the corresponding WordGraph, (pain, gain) is an edge because we can substitute the character `p' in `pain' with a `g' to obtain `gain'. The pair (pain, pan) is an edge because we can insert `i' in `pan' to obtain `pain'.

In the example, the edge set is {(pain, gain), (pain, pan), (gain, gait), (pan, span), (gait, wait)}.

Write a WordGraph class (in either Java or Python) with the following functionality:

You may assume that words only have characters from the English alphabet, and we don't distinguish upper and lower case letters. For testing, we plan to use subsets from the Stanford GraphBase's list of five-letter words. Please test your program on this list to check if the functions complete in a reasonable amount of time. We will also test on other hand-crafted lists.

I will post submission instructions a bit later here, and any additional clarifications as needed. The homework is due on Tuesday, October 3.

Update: Please upload the source files for your assignment to the Homework3 folder in ICON.