Sponsored Content
Top Forums Programming Help with Graphs (BFS mostly) Post 302721061 by SilvarHawke on Thursday 25th of October 2012 06:52:36 AM
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.
 

7 More Discussions You Might Find Interesting

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

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

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

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

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

7. 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
All times are GMT -4. The time now is 02:42 PM.
Unix & Linux Forums Content Copyright 1993-2022. All Rights Reserved.
Privacy Policy