I have written a bigger program, I am constructing a graph Graph(V,E), from words in a data file. Then I am parsing another file with words on same line: "other there" <-- like that, the first string is start word, the second is end word, as seen below:
while (true) {
String line = reader.readLine();
if (line == null) { break; }
assert line.length() == 11;
String start = line.substring(0, 5);
String goal = line.substring(6, 11);
System.out.println(
G.findShortestPath(
words.indexOf(start),
words.indexOf(goal)));
}
I am using undirected graphs with BFS. I am doing word transformation word chain, like this: climb → blimp → limps → pismo → moist → stoic
The input file contains words of length five, and a path/connection is defined as such so it goes from Xto Y in one step, only if, and only if the four last letters in Xare found in Y.
What is known, and I have calculated.
Time complexity: O(V + E) for building the graph G(V, E) of words. The second part of the program consists of a while loop and a for loop of finding the shortest path (using BFS), which is O(V^2).
Space complexity: O(V) in the worst case. The graph holds all the words. The nodes are made up of a single node class object which contains n neighbor(s).
Process:
- Program loads into buffer a file with words.
- The program builds the graph.
- The program runs test and loads into buffer information from a test file (different file). Then selects start and end node and performs the shortest path search.
If there's a connection, the code returns the shortest path length. If there's no connection between two words or end/goal cannot be reached, we return -1.
Now, I am trying to come up with an O(?) time algorithm or total time complexity for V,E,F, where:
- V is the number of vertices
- E is the number of edges
- F is the number of test cases (number of lines in the test file)*
*Number of test cases in function: public void performTest(String filename) throws IOException. The body of such function is here, see above. Now, I know, that for lines n, there will be same n amount of test cases. F=O(n). But, in what way, can one incorporate or add this calculation to make a general O expression with variables that holds for whatever amount of words in list and words in graph and words from testfile.
The main body of the BFS algorithm is the nesting of two loops, the while loop visits each vertex once, so it is O(|V|), and the for nested in the while , Since each edge will be checked only once when its starting vertex u is dequeued, and each vertex will be dequeued at most once, so the edge will be checked at most once, and the total is 0 (|E|).The time complexity of BFS is 0 (|V|+|E|)
Contents in Testfile: The first word becomes the starting word, the second on the same line becomes the end or target word.
blimp moist
limps limps
Some other code, I've written previously:
public static void main(String... args) throws IOException {
ArrayList<String> words = new ArrayList<String>();
words.add("their");
words.add("moist");
words.add("other");
words.add("blimp");
Graph g = new Graph(words.size());
for(String word: words) {
for(String word2: words){
g.addEdge(words.indexOf(word), words.indexOf(word2));
}
}
BufferedReader readValues = null;
try {
readValues =
new BufferedReader(new InputStreamReader(new FileInputStream("testfile.txt")));
String line = null;
while ((line = readValues.readLine()) != null) {
// assert line.length() == 11;
String[] tokens = line.split(" ");
String start = tokens[0];
String goal = tokens[1];
BreadthFirstPaths bfs = new BreadthFirstPaths(g, words.indexOf(start));
if (bfs.hasPathTo(words.indexOf(goal))) {
System.out.println("Shortest path distance from " + start + " to " + goal + " = " + bfs.distTo(words.indexOf(goal)));
} else System.out.println("Nothing");
}
} finally {
if (readValues != null) {
try {
readValues.close();
} catch (Throwable t) {
t.printStackTrace();
}
}
}
