S35_GraphAlgos_Medium
words.dat the document contains 5,757 unique five letter words. Two words will be considered related (connected by an edge) if they have an edit distance of one (if they differ by one and only one letter). Create an adjacency list from the given dataset. Then create two functions that use DFS and BFS respectively that find the largest connected set of vertices as well as printing out something that demonstrates the differences in the search algorithm of the two algorithms.
Define all your vertices in words.dat then compile and run GraphAlgosMediumTest. The program will automatically form the graph from the given dataset and constraints defined in the problem statement. Then BFS and DFS algorithms will be run on the graph to find the largest subset of connected vertices in the graph. The first 10 elements found will be printed for each algorithm to show that the different algorithms use different methods. Finally the number of vertices in the subset will be printed followed by every vertex in the subset.
All classes are defined using an anonymous type to allow for easy implementation of other data structures besides strings. However the example program only processes strings.
SimpleVertex defines a vertex with methods to easily create, set and check if two vertices are equal.
Vertex extends SimpleVertex and implements the an ArrayList of vertices which contain the vertices which are adjacent to itself in a graph.
An EdgeEvaluator is an interface used to check if two SimpleVertex's create an edge in a graph.
An UndirectedGraph is defined as a list of Vertex's and is created from such list by using an EdgeEvaluator. Once the graph is constructed all relations to the given vertices will be made and the vertices will be stored in verts. findLargestSubsetBFS() and findLargestSubsetDFS() implement BFS and DFS methods respectively to find the largest subset of connected vertices in the graph.
The example program found in GraphAlgosMediumTest creates a list of string vertices given the new line seperated words defined in words.dat and creates an EdgeEvaluator defined in GraphAlgosMediumTest#getEdgeEvaluator(). This evaluators two vertices as edges iff their edit distance between the two words is exactly one.
UML Diagram:
The java documents are served from a local web server on this machine. To start the web server, navigate to the directory immediately above where the source code is checked out (i.e. ~/git ) and then use "python -m SimpleHTTPServer" in that directory.
cd ~/git
python -m SimpleHTTPServer&Note: if you are running python 3 (which you can check via opening a terminal and typing: python --version), then the command is:
python3 -m http.server