Why aren't my Words connecting in Undirected/Unweighted Graph when using BFS?

Question

Issue in my code, not sure why NO connections are found in the Graph built with the words.

ArrayList<String> words = new ArrayList<String>();
words.add("hello");
words.add("there");
words.add("here");
words.add("about");
                
Graph g = new Graph(words.size());
for(String word: words) {
  for(String word2: words){
       g.addEdge(words.indexOf(word), words.indexOf(word2));
  }
}

BufferedReader readValues = 
    new BufferedReader(new InputStreamReader(new FileInputStream("values.txt")));

while(true)
{
    String line = readTestFile.readLine();
    if (line == null) { break; }
    assert line.length() == 11; 
    String start = line.substring(0, 5);
    String goal = line.substring(6, 11);
            
    BreadthFirstPaths bfs = new BreadthFirstPaths(g, words.indexOf(start));
    if (bfs.hasPathTo(words.indexOf(goal))) {
    System.out.println(bfs.distTo(words.indexOf(goal)));
     for (int v : bfs.pathTo(words.indexOf(goal))) {
               System.out.println(v);
     }
    }
    else System.out.println("Nothing");
}

Contents of the Text file:

hello there
hello here
about here

I seem to get:

Nothing
Nothing
Nothing
Nothing
Nothing

Not sure of why?

EDIT: OP seems to have trouble with the code here, especially, the graph. I do not know specifically why, but, I am sure there are those who do.

How does the `BreadthFirstPaths` class look like? Could the error be in that class? — hlg, Nov 28 '20 at 19:16
@hlg, https://algs4.cs.princeton.edu/41graph/BreadthFirstPaths.java.html — , Nov 29 '20 at 18:29
@AlbinM, what are `Graph` and `BreadthFirstPaths`? It's hard to debug your code like this. But I do have a couple of comments. First, it seems that your `substring` indices are not correct. For example `hello here` should throw an exception when doing `line.substring(6, 11)` Please note that. Second, I don't see you added anything to `bfs`, therefore why do you expect this method to result `true`? — Tomer Shetah, Feb 01 '21 at 07:40

jccampanero · Accepted Answer · 2020-11-29T11:35:46.230

I suppose you are using the source code from the excellent book from Robert Sedgewick and Kevin Wayne about algorithms implementation in Java Algorithms, 4th Edition.

There is no reason why your code should not work fine. Please, consider the following test based on your code:

public static void main(String... args) throws IOException {
  ArrayList<String> words = new ArrayList<String>();
  words.add("hello");
  words.add("there");
  words.add("here");
  words.add("about");

  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("values.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)));
        StringBuilder path = new StringBuilder();
        String sep = "";
        for (int v : bfs.pathTo(words.indexOf(goal))) {
          path.append(sep).append(v);
          sep = " -> ";
        }

        System.out.println("Shortest path = " + path.toString());
      } else System.out.println("Nothing");
    }

  } finally {
    if (readValues != null) {
      try {
        readValues.close();
      } catch (Throwable t) {
        t.printStackTrace();
      }
    }
  }
}

If you run this program with the text file that you indicated it will produce an output similar to the following:

Shortest path distance from hello to there = 1
Shortest path = 0 -> 1
Shortest path distance from hello to here = 1
Shortest path = 0 -> 2
Shortest path distance from about to here = 1
Shortest path = 3 -> 2

The main change I introduced is the code related with the calculation of the start and goal variables:

String[] tokens = line.split(" ");
String start = tokens[0];
String goal = tokens[1];

I assume you are using another text file, perhaps another code; with the one provided the assertion will fail or a StringIndexOutOfBounds exception will be raised when you calculate goal as the substring from index 6 to 11.

Apart from that, the algorithm should work fine.

That being said, please, be aware that you are constructing a graph hyperconnected, in which every node has a direct path to a different node and itself. Maybe that could be your objective, but be aware that things get interesting when you do some other kind of stuff.

For instance, if instead of this code:

for(String word: words) {
  for(String word2: words){
    g.addEdge(words.indexOf(word), words.indexOf(word2));
  }
}

You try something like this:

g.addEdge(words.indexOf("hello"), words.indexOf("there"));
g.addEdge(words.indexOf("hello"), words.indexOf("about"));
g.addEdge(words.indexOf("about"), words.indexOf("here"));

The output of the algorithm has more sense:

Shortest path distance from hello to there = 1
Shortest path = 0 -> 1
Shortest path distance from hello to here = 2
Shortest path = 0 -> 3 -> 2
Shortest path distance from about to here = 1
Shortest path = 3 -> 2

To get **O(V + E)**, I assume I must loop over Vertices and Edges? — , Nov 30 '20 at 10:05
Sorry for the late reply @AlbinM. Sorry, but I do not understand the question. Yes, the algorithm will provide you O(V+E) time complexity, where V denotes the number of vertices and E the number of edges, I think O(V²) in your case as you are providing every word to work combination. Please, can you clarify your question? — jccampanero, Nov 30 '20 at 22:02
Do I have to loop over Edges and Vertices, to find out if they are connected? — John Smith, Dec 05 '20 at 21:24
Hi John. Yes, I think so, if you want to find all the connections in the whole graph. The `BreadthFirstPaths` class provides a constructor that you can use to indicate the source vertex you want to check, and the node `Graph`. If you only want to verify if that vertex is connected with other you can use the method `hasPathTo`. But you need to repeat this process for every vertex you want to find if a connection exists and for every source vertex you take as origin. — jccampanero, Dec 05 '20 at 22:24
@jccampanero, thx. But, how would I do this? Would I loop with two loops over vertices and another loop over edges and then compare? This is a "word chain problem". — John Smith, Dec 06 '20 at 08:54
It is ok @JohnSmith, I think I understand your problem now: please, be aware that your question has no indication to the actual problem you are trying to solve. Does the algorithm have any restrictions? I mean, can you use the whole words? Do they have to share characters in common? Which are the rules? — jccampanero, Dec 06 '20 at 11:19
I realized that Albin have some comments that reference the [WordLadder](https://algs4.cs.princeton.edu/41graph/WordLadder.java.html) example presented in the Algorithms 4th ed book. Is that what you are trying to achieve, but maybe for every word in the whole graph? — jccampanero, Dec 06 '20 at 11:27
Thank you John. And, why don't you follow an approach similar to the one exposed in the `WordLadder` class? They are creating a graph of neighbors, in which each word in the dictionary is surrounded by edges with words that only differs one letter. It is a quite good approach. — jccampanero, Dec 06 '20 at 15:25
We are. See the code above. But, when using BFS, to get V+E, I do need to loop over both Vs and Es, right? But we don't know how. — John Smith, Dec 06 '20 at 23:23
@jccampanero, so you saying: `O(V^2)`, but, how can all of this be expressed: O() for a generalized time complexity of this entire code. Reading in each line of the file in the while loop and find performing BFS. V, E, F. **F** => *is the number of test cases (number of lines in the test file)*. — , Feb 20 '21 at 11:15

score 0 · Answer 2 · answered Nov 29 '20 at 13:11

I suppose you are using code from Java Textbook

your code should be

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;


public class words_sof {

    public static void main(String[] args) throws IOException {

        ArrayList<String> words = new ArrayList<String>();
        words.add("hello");
        words.add("there");
        words.add("here");
        words.add("about");

        Graph g = new Graph(words.size());
        for (String word : words) {
            for (String word2 : words) {
                g.addEdge(words.indexOf(word), words.indexOf(word2));
            }
        }

        try (BufferedReader readValues = new BufferedReader(new InputStreamReader(new FileInputStream("values.txt")))) {

            while (true) {
// ORIGINAL     String line = readTestFile.readLine();
// Should be
                String line = readValues.readLine();
                if (line == null) {
                    break;
                }
                
// ORIGINAL parse like this is not appropriate              
//              assert line.length() == 11;
//              String start = line.substring(0, 5);
//              String goal = line.substring(6, 11);
                // Use something like https://stackoverflow.com/questions/20728050/split-strings-in-java-by-words
                 String [] tokens = line.split("[\\s']");
                 
                 String start = tokens[0];
                 String goal = tokens[1];
                 
                BreadthFirstPaths bfs = new BreadthFirstPaths(g, words.indexOf(start));
                if (bfs.hasPathTo(words.indexOf(goal))) {
// Captions added for clarity                   
                    System.out.println("Distance : " + bfs.distTo(words.indexOf(goal)));
                    for (int v : bfs.pathTo(words.indexOf(goal))) {
                        System.out.print(" -> " + v);
                    }
                    System.out.println();
                } else
                    System.out.println("Nothing");
            }
        }
    }

}

Please notice modifications to the

// ORIGINAL lines.

The code above yields

Distance : 1
 -> 0 -> 1
Distance : 1
 -> 0 -> 2
Distance : 1
 -> 3 -> 2

Why aren't my Words connecting in Undirected/Unweighted Graph when using BFS?

2 Answers2