Help with Graphs (BFS mostly)


 
Thread Tools Search this Thread
Top Forums Programming Help with Graphs (BFS mostly)
# 1  
Old 10-25-2012
Help with Graphs (BFS mostly)

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...

Quote:
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.
# 2  
Old 10-25-2012
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.
This User Gave Thanks to Don Cragun For This Post:
# 3  
Old 10-25-2012
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...
This User Gave Thanks to SilvarHawke For This Post:
# 4  
Old 10-25-2012
Please create a new thread. Thanks.
Login or Register to Ask a Question

Previous Thread | Next Thread

7 More Discussions You Might Find Interesting

1. Red Hat

Do not show graphs cacti

hi installed caci and Snmp connection is established 10.10 (192.168.10.10) SNMP Information System:Hardware: Intel64 Family 6 Model 23 Stepping 6 AT/AT COMPATIBLE - Software: Windows Version 6.1 (Build 7601 Multiprocessor Free) Uptime: 7550665 (0 days,... (2 Replies)
Discussion started by: mnnn
2 Replies

2. Shell Programming and Scripting

Monitoring Graphs using GNUPLOT

Need assistance in getting a monitoring script to create Grpahs Using GNUPLOT using below data. Graph for CPU, MEMORY , NETWORK in png. For memory can we convert the GB TO MB ----system---- ----total-cpu-usage---- ------memory-usage----- -net/total- time |usr sys idl wai hiq... (5 Replies)
Discussion started by: ajayram_arya
5 Replies

3. Shell Programming and Scripting

Generating graphs for many number of files

Hi, I have a series of data files for which I wish to plot using "splot". Say, the files names are like: 950_data,951_data,952_data,......1000_data. For one file , say to plot 950_data, i write following lines into a single file and load it in the gnuplot as : gnuplot> load 'plot' ... (6 Replies)
Discussion started by: begin_shell
6 Replies

4. Post Here to Contact Site Administrators and Moderators

Suggestion: visitor graphs

Perhaps we could think of visitor graphs that would give a sense of both the popularity of the forum and - more importantly - the popularity of Linux and the Open Source operating systems movement. Something similar to what sourceforge has done for their projects: SourceForge.net: Project... (2 Replies)
Discussion started by: figaro
2 Replies

5. UNIX for Dummies Questions & Answers

multiple graphs on same window

Hi All, I have written a script to get live data after 5 minutes from a remote system and then plot the graph using gnuplot.All this has been working correctly with only one problem where i need to pull all these graphs into one page.I am not able to get this working.I tried reading about... (1 Reply)
Discussion started by: pistachio
1 Replies

6. UNIX for Dummies Questions & Answers

CPU graphs in unix

Hi, How to get the CPU graphs to see the performance? I use Linux version. I got some commands in the net. xload and xosview. It's mentioned like below: To start xload, simply open an xterminal on the system and type the following: $ xload &Couple of doubts here .. what is... (0 Replies)
Discussion started by: venkatesht
0 Replies

7. Shell Programming and Scripting

Creating graphs

Platform: solaris 9 x86 I want to be able to create excel like line graphs with basic input data and use it on a webpage or worst case so I can use it to insert to a document type of input file I would have, example below datainput.txt: date,requests,failures,success 20100501,80,10,70... (5 Replies)
Discussion started by: frustrated1
5 Replies
Login or Register to Ask a Question