Help with Graphs (BFS mostly)

SilvarHawke · October 25, 2012, 6:52am

Okay so I posted a thread about my project before, how I need to create generated word ladders and all that. Now I am to the point where I need to create a method which will find the shortests path between a start word and an end word. For example:

startWord: Head
endWord: Feet

And then a wordLadder would be something like...

Head, Heat, Feat, Feet,

Now I know that I am expected to use a graph here, and I was suggested to use a Breath First Search as I believe this works between two points or something along those lines. Expect I am not sure how to use this with my program. Here is my current code to give you guys an idea of how I made the program so far.

I've bolded and put the discover method in Italic to make sure it stands out more than the other methods, easier to read hopefully...

package uk.ac.aber.dcs.cs21120.wordplay.data;

import java.util.;
import java.io.;

/**

This class has all the records to run the menu aspect to the game,

as well as the main method to start the program.
*/
public class WordLadder {
private String word;
private ArrayList<String> words = new ArrayList<String>();
private String fileName = "";
private InputStream in;
private BufferedReader buf;
private int number;
private Hashtable<String,String> hashWords;
private Scanner scan, scanGen;

/**

This is the method for the WordLadder class, though it wouldn't have anything added to it.
*/
public WordLadder() {
}

/**

This method is used to read in what the user enters at the start of the program,

and then load a dictionary text file depending on the value they entered.
*/
public void initialize() {

in = System.in; //keyboard input
scan = new Scanner(in);
/*

Ask user for length of word input.
*/
System.out.println("How many characters does the word contain?\n" +
"Enter a value between 2 and 7 inclusive.");
String wordLength = scan.nextLine();
int wl = 0;
try {
wl = Integer.parseInt(wordLength);
} catch (NumberFormatException e) {
wl = 0;
}
while (!((wl>=2)&&(wl<=7))) {
System.out.println("Sorry, could not understand your request.\n" +
"Re-enter a value between 2 and 7 inclusive.");
wordLength = scan.nextLine();
try {
wl = Integer.parseInt(wordLength);
//used to turn any input that isn't a number into '0'.
} catch (NumberFormatException e) {
wl = 0;
}
}
fileName = "dict" + wordLength + ".dat";
readFromFile(fileName);

}

/**
*

@param fileName -
/
public void readFromFile(String fileName) {
words.clear();
try {
/

Construct the BufferedReader object
*/
buf = new BufferedReader(new FileReader(fileName));
String line = null;

while ((line = buf.readLine()) != null) {
/*

Process the data, here we just print it out
/
words.add(line);
}
} catch (FileNotFoundException ex) {
System.out.println("Sorry this file could not be found.");
ex.printStackTrace();
this.initialize();
} catch (IOException ex) {
ex.printStackTrace();
this.initialize();
} finally {
/

Try-Catch to close the BufferedReader
/
try {
if (buf != null)
buf.close();
} catch (IOException ex) {
ex.printStackTrace();
this.initialize();
}
/

Create the HashTable with the same capacity as the number of words

in the ArrayList (Dictionary)
/
hashWords = new Hashtable<String,String>(words.size());
/

Loop through the ArrayList and place each word into the HashTable.
*/
for (String w: words)
{
hashWords.put(w,w);
}
}
}

/**

This is used to create a word ladder of word between the values of 2 and 8.

This is done by using methods from the class including validate and searchForNewWord,

while also using ArrayLists and a HashTable.

@throws IOException - Input/Output Exception for any invalid string text

entered when scanners ask for them.
/
public void generate() throws IOException {
int stepNumber=0;
scanGen = new Scanner(in);
/

Ask user for word input.
*/
System.out.println("What word would you like to use?");
String userWord=scanGen.nextLine();
userWord=userWord.toLowerCase();

/*Must check that the word is in the dictionary.

Calls validate() method.
*/
if(!(validate(userWord))) {
System.out.println("Sorry, this word is not in my dictionary." +
" Please try again.");
return;
}
System.out.println("How many Numbers do you want generated?\n" +
"Enter a value between 2 and 8 inclusive.");
try {
stepNumber = Integer.parseInt(scanGen.nextLine());
}

catch (NumberFormatException e) {
stepNumber = 0;
}
/*

Must check if stepNumber is more than or equal to 2 or less than or equals to 8
*/

while (!((stepNumber>=2)&&(stepNumber<=8))) {

System.out.println("Sorry, could not understand your request.\n" +
"Re-enter a value between 2 and 8 inclusive.");

try {
stepNumber = Integer.parseInt(scanGen.nextLine());
}
catch (NumberFormatException e) {
stepNumber = 0;
}
}

/*

Calls the searchForNewWord() method for passing in the userWord and stepNumber
*/
String ladder = "Your word ladder is\n" + userWord + "\n";
String nextWord;
ArrayList<String> ladderWords = new ArrayList<String>();
ladderWords.add(userWord);

for(int g=0;g<stepNumber-1;g++) {
nextWord = searchForNewWord(userWord);

/if(nextWord==null) {
System.out.println("Sorry, I could only find " + (g+1) + " steps for this ladder.");
break;
}
else if(ladderWords.contains(nextWord)) {
g--;
}/

if(nextWord==null) {
System.out.println("Sorry, I could only find " + (g+1) + " steps for this ladder.");
break;
}
if(ladderWords.contains(nextWord)) {
System.out.println("Sorry, I could only find " + (g+1) + " steps for this ladder.");
break;
//g--; Infinite loop?
}
else {
userWord = nextWord;
ladderWords.add(userWord);
ladder = ladder +nextWord+"\n";
}

}
System.out.println(ladder);
}
/**

validate is used to check if the userWord (which the user has input) is

actually in the text file.

@param wordToCheck - which is the userWord.

@return true or false.
*/
public boolean validate(String wordToCheck) {
if(hashWords.contains(wordToCheck)) {
return true;
}
else {
return false;
}
}

/**

This method is used to search for a new word while removing the word that was
currently used to search for this new word.

@param word - This is the word that is entered by the user.

@return
/
public String searchForNewWord(String word) {
String userWord = word;
int numChars = userWord.length();
ArrayList<String> pileWords = new ArrayList<String>();
/

finds all words for the amount of steps given, so a loop is needed
*/
for(String w:words) {
int match = 0;
for(int p=0;p<numChars;p++) {
if(w.charAt(p)==userWord.charAt(p)) {
match++;
}
}
if(match==numChars-1) {
pileWords.add(w);
}
}

int pileNumber = pileWords.size();
if(pileNumber==0) {
return null;
}
else if(pileNumber==1) {
return pileWords.get(0);
}
/*

A Random() is used to produce a random selection of pileWords

from the pileNumber arrayList.
*/
else {
Random rand = new Random();
int ranWord = rand.nextInt(pileNumber);
return pileWords.get(ranWord);
}
}

public void discover() {
//get word from user
//Ask user for starting word.
System.out.println("What word would you like to start with?");
String startWord=scanGen.nextLine();
startWord=startWord.toLowerCase();
//Must check that the starting word is in the dictionary.
if(!(validate(startWord))) {
System.out.println("Sorry, this word is not in my dictionary." +
" Please try again.");
return;
}

//Ask user for step number input.
System.out.println("What word would you like to find the path to?");
String endWord=scanGen.nextLine();
endWord=endWord.toLowerCase();
//Must check that the ending word is also in the dictionary.
if(!(validate(endWord))) {
System.out.println("Sorry, this word is not in my dictionary." +
" Please try again.");
return;
}

String wordPath;
String ladder = "The shortest word path between " +startWord+ " and "
+endWord+ " is\n" + wordPath + "\n";
ArrayList<String> ladderWords = new ArrayList<String>();
ladderWords.add(startWord);
ladderWords.add(endWord);
}

/**

This runMenu() method runs the many options that are linked to the printMenu() method.

@throws IOException - This Input Output Exception is used in case any input that

isn't shown in the menu commands is entered.
*/
public void runMenu()throws IOException{
String response="";
do {
printMenu();
response=scan.next();
if (response.equals("1")|| response.equals("Generate")|| response.equals("exit")) {
generate();
}
else if (response.equals("2")|| response.equals("Discover")|| response.equals("discover")) {
discover();
}
else if (response.equals("3")|| response.equals("Re-Enter")|| response.equals("re-enter")|| response.equals("Reenter")|| response.equals("reenter")) {
initialize();
}
else if (response.equals("Q")|| response.equals("q")|| response.equals("Quit")|| response.equals("quit")) {
System.out.println("Thanks you for using Word Play, I hope you enjoyed your time!");
}
else {
System.out.println("Sorry, didn't quite get that. Could you repeat yourself?");
}
} while (! ( (response.equals("Q")|| (response.equals("q")|| response.equals("Quit")|| response.equals("quit")))));
}

/**

printMenu() method runs from the menu and shows all commands for the runMenu() method.

This shows what the main menu will looks like when it is run from the 'WordPlay'class.
*/

private void printMenu() {
System.out.println("What would you like to do?");
System.out.println("1 - Generate");
System.out.println("2 - Discover");
System.out.println("3 - Re-enter character length");
System.out.println("Q - Quit the game");
}

}

Depending if I cant understand graphs in the next hour or not, I may be able to edit in my other problems I am having, otherwise explaining to to use BFS Graphs would be brilliant, especially in this example.

Don_Cragun · October 25, 2012, 8:58am

I'm glad to see that you're making some progress on your homework assignment from what you originally showed us four days ago on the thread titled "Trouble with Iterators and Hashtables (Java)". But it looks very much like you're posting homework problems to the "Programming" forum rather than to the "Homework & Coursework Questions" forum. That makes it much less likely that we're going to spend much time trying to understand your code and help you help you complete your assignments.

SilvarHawke · October 25, 2012, 9:57am

Would it be possible if this thread could be moved over to there then at all please? Or would I be better off creating a new thread these since I have more problems with my code now...

Scott · October 25, 2012, 10:47am

Please create a new thread. Thanks.