Page 1 of 2 12 LastLast
Results 1 to 20 of 22
  1. #1
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default BFS Help with implementing Breadth First Search

    I have always wanted to program A*, Breath First Search and Depth First Search ever since I took AI. However it is completely kicking my booty.

    I will only post BFS at the moment but it is only searching the row. I am really really trying over here but I was hoping to find someone who has already programed this algorithm to give me some advice.

    Java Code:
    //Breath First Search. The first node passed to it is the start button
    	void bfs(Mybuttons button){
    		Queue<Mybuttons> q = new LinkedList<Mybuttons>();
    		q.add(button);
    		button.setIcon(button.setButtonToBlueWhileSearched());
    		button.model.visted=true;
    
    		while(!q.isEmpty() && targetFound(button)==false){
    			System.out.println("In while loop");
    			Mybuttons b = (Mybuttons)q.remove();
    			Mybuttons child = null;	
    		
    			while((child=getUnvisitedChildNode(b))!=null){
    				child.model.visted=true;
    				//turn child to a color here or print a value
    				q.add(child);
    				System.out.println("In second while loop");
    				
    				if(child.model.getTargetNode()==true){
    						System.out.println("Found it");
    						break;
    				}
    				
    			}
    		}
    		
    	}
    Java Code:
    private Mybuttons getUnvisitedChildNode(Mybuttons b){
    		
    		int x= b.getxCoordinate();
    		int y= b.getyCoordinate();
    		
    		while(y<model.arraySize()){
    			
    			if(view.matrixBtn[x][y].model.getVisted()==false && 
    			   view.matrixBtn[x][y].model.getBarrier()==false &&
    			   view.matrixBtn[x][y].model.getTargetNode()==false){
    				
    				view.matrixBtn[x][y].model.setVisted(true);
    				view.matrixBtn[x][y].setIcon(view.matrixBtn[x][y].setButtonToBlueWhileSearched());
    				
    				return view.matrixBtn[x][y];
    			}
    			
    			y++;
    			System.out.println("In get Child Node");
    		}
    		if(y==model.arraySize()-1){
    			y=0;
    		}
    		
    		
    		return null;
    	}
    Output:
    output:
    Java Code:
    			In while loop
    			In get Child Node
    			In get Child Node
    			In get Child Node
    			In get Child Node
    			In while loop
    			In get Child Node
    			In get Child Node
    			In get Child Node
    			In while loop
    			In get Child Node
    			In get Child Node
    			In while loop
    			In get Child Node

  2. #2
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    Trying to upload a picture of the guy but it is not working

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: BFS Help with implementing Breadth First Search

    Well, it didn't take me long to find this:

    A* search algorithm - Wikipedia, the free encyclopedia

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  4. #4
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    No I am trying to implement Breadth First Search at the moment not A*. I will cross that road later.

    This is what I am trying to do and what I think I am doing.
    Java Code:
    procedure BFS(G,v) is
    2      create a queue Q
    3      create a set V
    4      add v to V
    5      enqueue v onto Q
    6      while Q is not empty loop
    7         t ← Q.dequeue()
    8         if t is what we are looking for then
    9            return t
    10        end if
    11        for all edges e in G.adjacentEdges(t) loop
    12           u ← G.adjacentVertex(t,e)
    13           if u is not in V then
    14               add u to V
    15               enqueue u onto Q
    16           end if
    17        end loop
    18     end loop
    19     return none
    20 end BFS
    However I am not sending in a vertics just the button which has a x and y value sent to each one. It is a matrix of buttons so actually none are connected other then being in a matrix. Am I approaching it wrong?
    Last edited by jocdrew21; 12-13-2014 at 06:13 PM.

  5. #5
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: BFS Help with implementing Breadth First Search

    What is it you want to actually accomplish? To traverse a connected graph one usually hopes to find some optimum result (e.g. travel time from source to destination) based on some metric(s) (e.g. speed and/or distance). This is fundamental to network routing algorithms. But I don't know what you are trying to do.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  6. #6
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    I have a few pictures that I wish I could post on here to give you a clear picture of what my end statement should look like.

    I have a matrix of buttons it simply have to search the matrix line by line. I have the algorithm written it is the:
    Java Code:
    getUnvisitedChildNode(Mybuttons b)
    That is the issue. See the matrix is not a graph, meaning not really connected other than being in a matrix.
    Java Code:
    //Breath First Search. The first node passed to it is the start button
    	void bfs(Mybuttons button){
    		Queue<Mybuttons> q = new LinkedList<Mybuttons>();
    		q.add(button);
    		button.setIcon(button.setButtonToBlueWhileSearched());
    		button.model.visited=true;
    		Mybuttons child = null;
    
    		while(!q.isEmpty()){
    			System.out.println("In while loop");
    			Mybuttons b = (Mybuttons)q.remove();
    			
    			if(b.model.getTargetNode()==true){
    				System.out.println("Found it");
    				break;
    			}	
    			b.setIcon(button.setButtonToBlueWhileSearched());
    			
    			while((child=getUnvisitedChildNode(b))!=null){
    				child.model.visited=true;
    				//turn child to a color here or print a value
    				q.add(child);
    				System.out.println("In second while loop");
    				
    				}
    			
    		}
    		
    	}
    Java Code:
    private Mybuttons getUnvisitedChildNode(Mybuttons b){
    		
    		int x= b.getxCoordinate();
    		int y= b.getyCoordinate();
    		int j=0;
    		
    		while(j<model.arraySize()){
    			System.out.println("In get Child Node");
    			
    			if(view.matrixBtn[x][j].model.getVisited()==false && 
    			   view.matrixBtn[x][j].model.getBarrier()==false &&
    			   view.matrixBtn[x][j].model.getTargetNode()==false){
    				
    				view.matrixBtn[x][j].model.setVisited(true);
    				view.matrixBtn[x][j].setIcon(view.matrixBtn[x][y].setButtonToBlueWhileSearched());
    				
    				System.out.println("leaving Child Node");
    				return view.matrixBtn[x][j];
    			}
    			
    			j++;
    		}
    It searches only the row of the start button at the moment and hangs in the getUnvisitedChildNode(Mybuttons b) when that row is searched.

    Output:

    Java Code:
    In while loop
    In get Child Node
    leaving Child Node
    In second while loop
    In get Child Node
    In get Child Node
    leaving Child Node
    In second while loop
    In get Child Node
    In get Child Node
    In get Child Node
    leaving Child Node
    In second while loop
    In get Child Node
    In get Child Node
    In get Child Node
    In get Child Node
    leaving Child Node
    In second while loop
    In get Child Node
    In get Child Node
    In get Child Node
    In get Child Node
    In get Child Node
    leaving Child Node
    In second while loop
    In get Child Node
    In get Child Node
    In get Child Node
    In get Child Node
    In get Child Node
    I am so close yet so far away...

  7. #7
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS Help with implementing Breadth First Search

    Some comments:
    The while statement on line 7 looks like it should be a for statement.
    Create an interface for the methods the search needs access to vs using Mybuttons objects.
    This statement binds the whole program into one structure vs some separate objects:
    view.matrixBtn[x][j].model.getVisited()
    There are too many .s

    Why not put the setIcon() call inside of the method and use:
    Java Code:
    	view.matrixBtn[x][j].setButtonToBlueWhileSearched();
    // instead of
           view.matrixBtn[x][j].setIcon(view.matrixBtn[x][y].setButtonToBlueWhileSearched());
    Last edited by Norm; 12-14-2014 at 07:14 PM.
    If you don't understand my response, don't ignore it, ask a question.

  8. #8
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    Create an interface for the methods the search needs access to vs using Mybuttons objects.
    By this you mean something along theres lines?

    Java Code:
    interface findChildButton extends Mybuttons{
        boolean getVisited(Mybuttons);
        boolean getBarrier(Mybuttons);
    }
    Then use this in the controller class. I know I am looking silly for asking this but I rarely use interface. However I would really like to understand what you are saying. I get the idea behind it just not completely

    I will try your for loop suggestion once I get home. Once I get that method to work I will be able to wrap up this project. :)

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS Help with implementing Breadth First Search

    Not like that.
    The interface defines the methods that need to be called by bfs() and getUnvisitedChildNode().
    Define Mybuttons to implement that interface.
    Then an instance of that interface is passed to bfs() and getUnvisitedChildNode()
    If you don't understand my response, don't ignore it, ask a question.

  10. #10
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    So something on the lines of
    Java Code:
     interface searchGraph{
       boolean getTarget();
       boolean isVisited();
    }
    Java Code:
    Class Mybuttons() implements seachGraph{
       boolean target;
       boolean visited;
    
       boolean getTarget(){
            return true;  //just for an example
       }
       boolean isVisited(){
         return true;  //just for an example
       }
    
    }
    in the controller I would need to do something like this right?
    Java Code:
    seachGraph search = new Mybuttons(); //perhaps in the constructor

  11. #11
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS Help with implementing Breadth First Search

    Not quite. The code would not create an instance of SearchGraph. The instance of Mybuttons is an instance of SearchGraph because of the implements clause.
    The data type: SearchGraph would be passed in the call to bfs() instead of Mybuttons:
    Java Code:
       void bfs(SearchGraph aSearchGraph){
    If you don't understand my response, don't ignore it, ask a question.

  12. #12
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    Ahhh got it like... Like this:

    Java Code:
    interface searchGraph{
       boolean getTarget();
       boolean isVisited();
    }
    Java Code:
    Class Mybuttons() //do not implement searchGraph{
       boolean target;
       boolean visited;
     
       boolean getTarget(){
            return true;  //just for an example
       }
       boolean isVisited(){
         return true;  //just for an example
       }
     
    }
    Java Code:
    void bfs(SearchGraph aSearchGraph){
    Now my IDE would give me an error because bfs has not implemented the methods, then I could just add the methods and mission accomplished... Right

  13. #13
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS Help with implementing Breadth First Search

    //do not implement searchGraph{
    What does that mean???
    Mybuttons needs to implement SearchGraph (as in post#10) so an instance can be passed to bfs() etc
    If you don't understand my response, don't ignore it, ask a question.

  14. #14
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    I can feel your frustration from over here. Thank you for your patience, I understand now...

    I just need to do this, really only thing I need from Mybuttons is the x and y coordinates and if it has been visited and its state. Therefore the interface will be full of a bunch of getter and setters, similar to a bean.
    Last edited by jocdrew21; 12-15-2014 at 02:50 PM.

  15. #15
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    @ norm I finally had time to do what you were referring to. This is what I have, I wanted to get your opinion:

    Java Code:
    private Mybuttons getUnvisitedChildNode(GraphMethods g){
    		
    		int x= g.getxCoordinate();
    		int y= g.getyCoordinate();
    		int j=0;
    		
    		while(j<model.arraySize()){
    			System.out.println("In get Child Node");
    			
    			if(view.matrixBtn[x][j].model.getVisited()==false && 
    			   view.matrixBtn[x][j].model.getBarrier()==false &&
    			   view.matrixBtn[x][j].model.getTargetNode()==false){
    				
    				view.matrixBtn[x][j].model.setVisited(true);
    				view.matrixBtn[x][j].setIcon(view.matrixBtn[x][y].setButtonToBlueWhileSearched());
    				
    				System.out.println("leaving Child Node");
    				return view.matrixBtn[x][j];
    			}
    			
    			j++;
    		}
    Java Code:
    class Mybuttons extends JButton implements GraphMethods{
    I am still extending JButton because this class is a JButton in retrospect. A few comments were made in the past on why I was doing that.

    [/code]
    Java Code:
    package path.finding;
    
    import javax.swing.ImageIcon;
    
    public interface GraphMethods {
    	public int getNumber();
    	public int setNumber();
    	public ImageIcon setImage(int count);
    	public ImageIcon resetButton();
    	public void setState(ImageIcon state);
    	public ImageIcon getState();
    	public int getxCoordinate();
    	public void setxCoordinate(int xCoordinate);
    	public int getyCoordinate();
    	public void setyCoordinate(int yCoordinate);
    	public ImageIcon setButtonToBlueWhileSearched();
    	
    }
    I have not worked on the for loop yet but I am about to. Just wanted to make sure I was on the right track with the interface suggestion you mentioned.

    For those whom stumble across the thread I found a great explaination of why it is very useful to pass interfaces as parameters.

    This is in fact one of the most common and useful ways to use an interface. The interface defines a contract, and your code can work with any class that implements the interface, without having to know the concrete class - it can even work with classes that didn't exist yet when the code was written.

    There are many examples in the Java standard API, especially in the collections framework. For example, Collections.sort() can sort anything that implements the List interface (not just ArrayList or LinkedList, though implementing your own List is uncommon) and whose contents implement the Comparable interface (not just String or the numerical wrapper classes - and having your own class implement Comparable for that purpose is quite common).
    It can be found at: oop - interface as a method parameter in Java - Stack Overflow
    Last edited by jocdrew21; 12-16-2014 at 09:08 PM.

  16. #16
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS Help with implementing Breadth First Search

    This line still shows a needed change
    Java Code:
    	view.matrixBtn[x][j].setIcon(view.matrixBtn[x][y].setButtonToBlueWhileSearched());
    // should be:  (move setIcon() into setButtonToBlueWhileSearched())
    	view.matrixBtn[x][j].setButtonToBlueWhileSearched();
    If you don't understand my response, don't ignore it, ask a question.

  17. #17
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS Help with implementing Breadth First Search

    Are all the methods in the interface absolutely needed by the search methods? My idea was to isolate the Mybuttons stuff from what was needed for a search. This ties it all together too much making it sort of in the way.
    Last edited by Norm; 12-16-2014 at 09:20 PM.
    If you don't understand my response, don't ignore it, ask a question.

  18. #18
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    Got it..

    Java Code:
    public interface GraphMethods {
    	
    	public int getxCoordinate();
    	public int getyCoordinate();
    	public ImageIcon setButtonToBlueWhileSearched();
    	
    }
    Java Code:
    private Mybuttons getUnvisitedChildNode(GraphMethods g){
    		
    		int x= g.getxCoordinate();
    		//int y= g.getyCoordinate();
    		int j=0;
    		
    		while(j<model.arraySize()){
    			System.out.println("In get Child Node");
    			
    			if(view.matrixBtn[x][j].model.getVisited()==false && 
    			   view.matrixBtn[x][j].model.getBarrier()==false &&
    			   view.matrixBtn[x][j].model.getTargetNode()==false){
    				
    				view.matrixBtn[x][j].model.setVisited(true);
    				view.matrixBtn[x][j].setButtonToBlueWhileSearched();
    				
    				System.out.println("leaving Child Node");
    				return view.matrixBtn[x][j];
    			}
    			
    			j++;
    		}
    Last edited by jocdrew21; 12-16-2014 at 10:04 PM.

  19. #19
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: BFS Help with implementing Breadth First Search

    Why does the set method return anything? Normally set methods are void. get methods are the ones that return a value.

    The method only requires the row to search, why pass it anything else?
    Java Code:
     Mybuttons getUnvisitedChildNode(int theRowIdx){
    or pass the second dim (an array):
    Java Code:
     Mybuttons getUnvisitedChildNode(Mybuttons[] thisRow){
    // Used as follows:
       thisRow[theColumn].model.getVisited() ==
    Last edited by Norm; 12-16-2014 at 10:20 PM.
    If you don't understand my response, don't ignore it, ask a question.

  20. #20
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Re: BFS Help with implementing Breadth First Search

    Yes I suppose that methods name is confusing.
    Java Code:
    view.matrixBtn[x][j].setButtonToBlueWhileSearched();
    Java Code:
    	public ImageIcon setButtonToBlueWhileSearched(){
    		return blueIcon;
    	}
    I meant by that is it is being set to blue while it is being searched.

    The method only requires the row to search, why pass it anything else?
    My goal is to search around the entire button, much like a box method and increasing the box until the target button is found.

Page 1 of 2 12 LastLast

Similar Threads

  1. Breadth First Search
    By Blacky777 in forum New To Java
    Replies: 4
    Last Post: 04-20-2012, 02:24 PM
  2. Implementing a binary search tree?
    By computerbum in forum New To Java
    Replies: 1
    Last Post: 04-03-2012, 10:39 PM
  3. Question with a Tree and Breadth First Search
    By Ing. Balderas in forum New To Java
    Replies: 1
    Last Post: 05-17-2010, 06:46 AM
  4. Graph - Breadth First search for searching a node ?
    By JavaInLove in forum Advanced Java
    Replies: 1
    Last Post: 10-06-2008, 11:17 PM
  5. Breadth First Search and Friends!
    By nokomis in forum New To Java
    Replies: 0
    Last Post: 11-09-2007, 09:16 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •