S35_GraphAlgos_Hard
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. Then using this subset find the minimum spanning tree (MST) using Prim's algorithm and print out the total weight of the MST. The weight between to edges is defined as
Weight = MIN(magnitude(w1), magnitude(w2))
Where w1 and w2 are two connected words and the magnitude of a word is defined as the sum of the characters when cast to integer values. To get the integer value of the character, use Character.getNumericvalue().
The program can be started by compiling and running GraphAlgosHardTest. The program will immediately build an non-directed weighted graph from the string vertices defined in words.dat and will build the relationship between the vertices as described in the problem statement above. Then the MST will be found from the graph and the weight of the total MST will be printed to the screen. Changing the words defined in words.dat will allow other graphs to be found in the same manner.
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.
Edge consists of two vertices and a boolean tied to whether the edge is directed or not.
WeightedEdge extends Edge and adds a weight value to the edge which is the weight of an edge in the graph.
EdgeEvaluator is an interface used to check if two SimpleVertex's create an edge in a graph.
EdgeWeightEvaluator is and interface used to define a weight between any two vertices.
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.
WeightedUndirectedGraph extends UndirectedGraph and is constructed with an additional EdgeWeightEvaluator allowing the graph to associate weights between adjacent vertices.
The minimum spanning tree is implemented in MST and upon construction it creates the MST from the given non-directed weighted graph using prims algorithm. The edges are stored in a hash map mst where the key is a unique vertex in the graph and the value is the lightest WeightedEdge it makes with another vertex in the MST. Prim's algorithm is implemented using a priority queue pq where indices are sorted based on the lightest edges that immediately connect the the current MST using the hash map vertexWeight. The key in the hashmap is a vertex immediately connected to the current MST and the value is the weight of such edge. Then all vertices in the MST is stored in the set of vertices inMST where if a value is present it is in the MST.
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