How to search through a graph?

Hey,

       I'm trying to search through a graph and trying to store the nodes I visited in a set, I'm reading in the graph in the form of a text file, and I call my searchGraph() function.

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


public class Search extends Thread{
	static Set<Integer> visited = new HashSet<Integer>();
	static ArrayList<Node> graph = new ArrayList<Node>();
	public static void main(String[] args){
		ArrayList<String> fileContents = readFile("graph.txt");
		Node n = new Node();
		//System.out.println(fileContents);
		
		for(int i = 0; i < fileContents.size(); i++){
			n = new Node();
			String delims = "[ ]";
			String[] src = fileContents.get(i).split(delims);
			
			System.out.println(src[0] + " " + src[1]);
			
			n.setSource(Integer.parseInt(src[0]));
			delims = "[,]";
			String[] dests = src[1].split(delims);
			for(int a = 0; a < dests.length; a++){
				System.out.println("dests = " + dests[a]);
			}
			
			for(int x = 0; x < dests.length; x++){
				System.out.println("destinations = " + dests[x]);
				n.addDestinations(Integer.parseInt(dests[x]));
			}
			graph.add(n);
		}
		
		for(int i = 0; i < graph.size(); i++){
			System.out.println("Source of " + i + " is: " + graph.get(i).getSource());
			System.out.println("Destinations of " + i + " is: " + graph.get(i).getDestinations());
		}
		
		searchGraph(graph);
		
		System.out.println(visited);
		
	}
	
	public static void searchGraph(ArrayList<Node> g){
		ArrayList<Node> call = new ArrayList<Node>();
		Node temp = new Node();
		Integer src = g.get(0).getSource();
		
		for(int i = 0; i < g.get(0).getDestinations().size(); i++){
			if(!visited.contains(g.get(0).getDestinations(i))){
				visited.add(g.get(0).getDestinations(i));
				for(int x = 0; x < g.get(0).getDestinations().size(); x++){
					//System.out.println("graph.get(0) = " + g.get(0).getDestinations(x));
					temp.setSource(g.get(i).getDestinations(x));
					for(int y = 0; y < g.get(i).getDestinations().size(); y++){
						call.add(graph.get(temp.getSource()));
					}
					
				}
			}
			searchGraph(call);
		}
		
		if(visited.size() == 5){
			return;
		}
	}
	
	public static ArrayList<String> readFile(String file){
		ArrayList<String> contents = new ArrayList<String>();
		
		try{
		    // Open the file that is the first 
		    // command line parameter
		    FileInputStream fstream = new FileInputStream(file);
		    // Get the object of DataInputStream
		    DataInputStream in = new DataInputStream(fstream);
		        BufferedReader br = new BufferedReader(new InputStreamReader(in));
		    String strLine;
		    //Read File Line By Line
		    while ((strLine = br.readLine()) != null)   {
		      contents.add(strLine);
		    }
		   
		    in.close();
		    }catch (Exception e){//Catch exception if any
		      System.err.println("Error: " + e.getMessage());
		    }
		
		return contents;
	}
}

Open in new window


Node.java

graph.txt

The basic logic behind my program is that searchThread() would call itself with the array list indexes of the destinations of the starting node.  I mean... if graph.get(0)'s destinations is 4 and 5, searchGraph() is supposed to call itself with an ArrayList containing graph.get(4) and graph.get(5).

I tried printing out what its supposed to pass through, and everything checks out... so I don't know what's wrong...

Could anyone help me out with this?

Appreciate any help!
errangAsked:
Who is Participating?
 
for_yanCommented:

So you can't figure out why at line 62:

temp.getSource() at certain moment becomes 5
and the total szie of arrylist graph is only 5 -    so array out of bounds condiition
0
 
for_yanCommented:
The start(0 method does not take any parameters but you may communicate parameters through instance
variables. You can set an instance arry and eacvh thread say would know to read its own element - acn't you do something like that?
0
 
for_yanCommented:
And this array you can modify from any place so the threads can communicate with each other through
instance variables.
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

 
for_yanCommented:
Did I see in your initial question the text that start() method does niot take parameters?
Where is this text now?
I could not have inveneted it, I read in your question about start() and run() methods.
0
 
for_yanCommented:
Ok, no , I'm happy I'm not crazy - that is waht I was answering:
(You probably modified the text of the question later)

---------------------------
The basic logic behind my program is that searchThread() would call itself with the array list indexes of the destinations of the starting node.  I mean... if graph.get(0)'s destinations is 4 and 5, searchGraph() is supposed to call itself with an ArrayList containing graph.get(4) and graph.get(5).

But for some reason, its crashing, and I can't figure out why...

Also, I tried running this function using threads, and I tried putting the function in a public void run() function, but how would I send it different values?  Because the start() function for threads doesn't take any parameters... right?

Could anyone help me out with this?
---------------------------------------------------------------

0
 
errangAuthor Commented:
>>Ok, no , I'm happy I'm not crazy - that is waht I was answering:

Yea, I'm sorry, I just figured I'd get a regular version of the code working before I put work into parallelizing it.

I just can't figure out why it won't call the nodes its supposed to call...
0
 
for_yanCommented:
OK. This sequence makes sense.
In this kind of applications logic is the most difficult part.
Therdas will make it even much more difficult - makes sens to do it stepwise.
0
 
errangAuthor Commented:
ahh... my logic takes the destination node, and asks the ArrayList to get that particular index... hm, I'm not sure how else I can explore the graph... using a loop wouldn't really accomplish anything, and if I can't reference it with the source nodes... that's gonna make things a bit difficult...
0
 
errangAuthor Commented:
I just kept removing the starting index of the graph...

public static void searchGraph(ArrayList<Node> g){            
            for(int i = 0; i < g.get(0).getDestinations().size(); i++){
                  if(visited.contains(g.get(0).getDestinations(i))){
                        System.out.println("i got " + g.get(0).getDestinations(i));
                  }
                  else{
                        visited.add(g.get(0).getDestinations(i));
                        System.out.println("visited is now " + visited);
                  }
            }
            
            g.remove(0);
            
            if(visited.size() >= 5){
                  return;
            }else
                  searchGraph(g);
      }

Seems to work for the moment... not sure if I can use the same logic for the parallelized version though...
0
 
for_yanCommented:
Good! Even though I didn't do much, other than compiled and executed  your code; but maybe urged you to think more,
which is after all also useful.
Good luck!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.