Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

How to search through a graph?

Posted on 2011-05-04
10
Medium Priority
?
295 Views
Last Modified: 2012-06-27
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!
0
Comment
Question by:errang
  • 7
  • 3
10 Comments
 
LVL 47

Expert Comment

by:for_yan
ID: 35695381
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
 
LVL 47

Expert Comment

by:for_yan
ID: 35695385
And this array you can modify from any place so the threads can communicate with each other through
instance variables.
0
 
LVL 47

Expert Comment

by:for_yan
ID: 35695402
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 47

Expert Comment

by:for_yan
ID: 35695416
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
 

Author Comment

by:errang
ID: 35695424
>>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
 
LVL 47

Expert Comment

by:for_yan
ID: 35695430
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
 
LVL 47

Accepted Solution

by:
for_yan earned 2000 total points
ID: 35695470

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
 

Author Comment

by:errang
ID: 35695492
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
 

Author Closing Comment

by:errang
ID: 35695504
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
 
LVL 47

Expert Comment

by:for_yan
ID: 35695511
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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
What do responsible coders do? They don't take detrimental shortcuts. They do take reasonable security precautions, create important automation, implement sufficient logging, fix things they break, and care about users.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
In a recent question (https://www.experts-exchange.com/questions/29004105/Run-AutoHotkey-script-directly-from-Notepad.html) here at Experts Exchange, a member asked how to run an AutoHotkey script (.AHK) directly from Notepad++ (aka NPP). This video…
Suggested Courses

572 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question