Question: Java. I need to write a test for this word ladder code. import stdlib.*; import algs13.Bag; /** * The {@code Graph} class represents an undirected
Java. I need to write a test for this word ladder code.
import stdlib.*;
import algs13.Bag;
/**
* The {@code Graph} class represents an undirected graph of vertices
* named {@code 0} through {@code V-1}.
* It supports the following operations: add an edge to the graph,
* iterate over all of the neighbors adjacent to a vertex.
* Parallel edges and self-loops are permitted.
*
* For additional documentation, see Section 5.1 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*/
public class Graph {
private final int V;
private int E;
final Bag
String[] labels;
/**
* Create an empty graph with V vertices.
*/
@SuppressWarnings("unchecked")
public Graph(int V) {
if (V < 0) throw new Error("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
this.adj = new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<>();
}
labels = new String[V];
}
/**
* Return the number of vertices in the graph.
*/
public int V() { return V; }
/**
* Return the number of edges in the graph.
*/
public int E() { return E; }
/**
* Add the undirected edge v-w to graph.
* @throws java.lang.IndexOutOfBoundsException unless both {@code 0 <= v < V} and {@code 0 <= w < V}
*/
public void addEdge(int v, int w) {
if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
if (w < 0 || w >= V) throw new IndexOutOfBoundsException();
E++;
adj[v].add(w);
adj[w].add(v);
}
/**
* Return the list of neighbors of vertex v as in Iterable.
* @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= v < V}
*/
public Iterable
if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
return adj[v];
}
/**
* Returns the degree of vertex {@code v}.
*
* @param v the vertex
* @return the degree of vertex {@code v}
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public int degree(int v) {
if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
return adj[v].size();
}
/**
* Return a string representation of the graph.
*/
public String toString() {
StringBuilder s = new StringBuilder();
String NEWLINE = System.getProperty("line.separator");
s.append(V + " vertices, " + E + " edges " + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (int w : adj[v]) {
s.append(w + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
/**
* Save a graphviz representation of the graph.
* See graphviz.org.
*/
public void toGraphviz(String filename) {
GraphvizBuilder gb = new GraphvizBuilder ();
for (int v = 0; v < V; v++) {
gb.addNode (v);
boolean showSelfLoop = false;
for (int w : adj[v]) {
if (v < w) // only once each edge
gb.addEdge (v, w);
if (v == w) {
showSelfLoop = !showSelfLoop;
if (showSelfLoop)
gb.addEdge (v, w);
}
}
}
gb.toFileUndirected (filename);
}
/**
* Test client.
*/
public static void main(String[] args) {
//args = new String [] { "data/tinyCG.txt" };
args = new String [] { "bin/algs41/words4.txt" };
//args = new String [] { "20", "40" };
//args = new String[] { "FOOL", "POOL", "POLL", "POLE", "PALE", "SALE", "SAGE" };
Graph G;
if (args.length == 1) {
In in = new In(args[0]);
G = GraphGenerator.fromIn (in);
} else {
int V = Integer.parseInt (args[0]);
int E = Integer.parseInt (args[1]);
G = GraphGenerator.simple(V, E);
}
StdOut.println(G);
//G.toGraphviz ("g.png");
}
}
////////////////////////////////////////////////
import java.util.*;
public class wordLadder {
//string of words for word ladder
static String[] words = { "FOOL", "POOL", "POLL", "POLE", "PALE", "SALE", "SAGE" };
//graph of words
Graph G;
//Hash map
HashMap
//Generate a word ladder graph based on the words from the string array
public wordLadder() {
G = new Graph(words.length);
wordToVertex = new HashMap<>();
for (int i = 0; i < words.length; i++) {
wordToVertex.put(words[i], i);
}
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (oneLetterDifferent(words[i], words[j])) {
G.addEdge(i, j);
}
}
}
}
//Detects if the words are different by one letter
private boolean oneLetterDifferent(String word1, String word2) {
int count = 0;
for (int i = 0; i < word1.length(); i++) {
if (word1.charAt(i) != word2.charAt(i)) {
count++;
}
if (count > 1) {
return false;
}
}
return count == 1;
}
//Returns an array with the shortest path between two words within the array
//using BFS algorithm
public String[] path(String s, String t) {
int start = wordToVertex.get(s);
int end = wordToVertex.get(t);
int[] prev = new int[words.length];
Arrays.fill(prev, -1);
boolean[] visited = new boolean[words.length];
Queue
q.offer(start);
visited[start] = true;
while (!q.isEmpty()) {
int v = q.poll();
for (int neighbor : G.adj[v]) {
if (!visited[neighbor]) {
prev[neighbor] = v;
visited[neighbor] = true;
q.offer(neighbor);
}
if (neighbor == end) {
return reconstructPath(prev, start, end);
}
}
}
return null;
}
private String[] reconstructPath(int[] prev, int start, int end) {
List
int current = end;
while (current != start) {
pathList.add(0, words[current]);
current = prev[current];
}
pathList.add(0, words[start]);
return pathList.toArray(new String[0]);
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help