Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Right so who is a Guru at BreadthFirstSearch ?

  1. #1
    Junior Member
    Join Date
    Apr 2011
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Right so who is a Guru at BreadthFirstSearch ?

    hi there,

    I have just recently finished a project that uses breadthfirst search to find a route along the london underground, for most stations it will find the route ok, but for some, ie./ uxbridge to say acton town I get an exception error

    Exception in thread "main" java.lang.NullPointerException
    at londonundergroundplanner.BreadthFirstSearch.checkI fHaveTraversed(BreadthFirstSearch.java:141)
    at londonundergroundplanner.BreadthFirstSearch.BFS(Br eadthFirstSearch.java:88)
    at londonundergroundplanner.Application.BFS(Applicati on.java:94)
    at londonundergroundplanner.Application.runApplicatio n(Application.java:50)
    at londonundergroundplanner.Main.main(Main.java:25)
    Java Result: 1


    it is at line 141

    heres my class:
     
    /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */
     
    package londonundergroundplanner;
     
    import java.io.FileNotFoundException;
    import java.io.IOException;
    import java.io.PrintStream;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
     
    /**
     *
     * @author jamiewilbraham
     */
    public class BreadthFirstSearch {
     
        // initialize variables
        private  StationGraph graph;
        private  HashMap <String, ArrayList<StationEdge>> adjList;
        private  ArrayList <String> route; // tracks the return to the theStation
        private  StationQueue queue;
        private  HashSet<String> visitedParents;
        private  HashSet<String> visited;
        private  HashMap<String,Integer> levelTracker;
        private  int levelCount;
        private  PrintStream output; // look at removing
        private  String neighbour;
     
     
     
     
     
        //Constructor
        public BreadthFirstSearch(String stationFile, String edgeList) throws FileNotFoundException, IOException {
     
            graph = new StationGraph(stationFile,edgeList);
            graph.setAdjacencyList(output); // pass this through a paramter from application
            adjList = graph.getAdjacencyList();
            route = new ArrayList <String> ();
            queue = new StationQueue();
            visitedParents = new HashSet<String>();
            visited = new HashSet<String>();
            levelTracker = new HashMap<String,Integer>() ;
            levelCount = 0;
     
     
        }
     
        //methods
     
        /*
         * method to return the route in which to get to destiontion
         *
         * @return the route of the route
         */
        public ArrayList<String> getRouteArrayList() {
     
            assert (route !=null): "Problem with the path array";
            return route;
        }
     
     
        /*
         * method that executes the Breadfirst search algorithm
         *
         * @param String currentStation - the station the user is currently at
         * @param String destination - the destination station the user is trying to reach
         */
        public void BFS(String currentStation, String destination)  {
     
    	initialiseGraphWithCurrentStation(currentStation);
    	levelTracker.put(currentStation, 0); // set current station
     
    	while (!queue.isEmpty()) {
                Map<String, ArrayList<StationEdge>> theStation = new HashMap<String, ArrayList<StationEdge>>();
                theStation = queue.dequeEdge();
     
                for (Map.Entry<String, ArrayList<StationEdge>> station : theStation.entrySet()) {
     
                    for (StationEdge edge : station.getValue()) {	 // for each of this stations Edges
                        neighbour = edge.getNeighbour(); // retrieve the name of adjacent neighbour
                        checkIfHaveTraversed(edge );
                        checkIfNotDestination(edge ,destination);
     
                        if(checkIfFoundDestination(edge,destination)) {
                                returnToRoot(neighbour, edge);
                                while (!queue.isEmpty()) {
                                    theStation = queue.dequeEdge(); // empty the queue
                                }
     
     
                        break;// exit the loops
                        }
    		}
                }
            }
        }
     
        /*
         *method that us able to check if the destination has been traversed through
         *
         * @param StationEdge edge - the current station edge
         * @param String destination - the station in which to compare to
         *
         * @return boolean - whether or not the destination station has been found
         */
         private boolean checkIfFoundDestination(StationEdge edge , String destination) {
             return neighbour.equals(destination);
         }
     
        /*
         *method to check whether a not a station has been visited and if its the dest
         * then go to the next station
         *
         * @param StationEdge edge - current edge iterating
         * @param String destination - the detsination station
         */
         private void checkIfNotDestination(StationEdge edge , String destination) {
     
            if (!neighbour.equals(destination) && !visited.contains(neighbour)) { // if it's not the destination
                 traverseNextStations(neighbour, edge);
             }
         }
     
        /*
         *method that if ahve previously traversed a station
         * add a tree level
         *
         * @param StationEdge edge - the current edge
         */
         private void checkIfHaveTraversed(StationEdge edge) {
     
             //assert (levelTracker=null) : "null levelTracker in Check if have Traversed";
             assert (neighbour=null) : "null neighbour in Check if have Traversed";
     
             if (levelTracker.get(neighbour) == -1) {
                levelCount = levelTracker.get(edge.getParent()) + 1; // add tree level
             }
         }
     
        /*
         * method to initisalize the graph with the current station
         *
         * @param String currentStation - the current station
         */
        private void initialiseGraphWithCurrentStation(String currentStation) {
     
            for (String theStation : adjList.keySet()) {
                levelTracker.put(theStation, -1); //Set all the Stations to level -1
                findCurrentStationInGraph(theStation, currentStation); // iterate through the adjList until theStation is found
            }
        }
     
        /*
         * method to get the current statuion from the graph
         *
         * @param String stationName - the name of the station in the graph
         * @param String currentStation - the station to get from graph
         */
        private void findCurrentStationInGraph(String stationName, String currentStation) {
            Map <String, ArrayList<StationEdge>> current;
     
            if (stationName.equals(currentStation)) {
                current = new HashMap<String, ArrayList<StationEdge>>();
                current.put(stationName, adjList.get(stationName));
                queue.enqueue(current); // when found add the theStation to the queue
            }
        }
     
        /*
         * method to traverse back to the root then reverse the collection
         * 
         * @param String destination = the destination station
         * @param StationEdge - the current edge
         */
        private void returnToRoot(String destination, StationEdge edge) {
            ArrayList<StationEdge> nextStationEdges = adjList.get(destination);
            visited.add(edge.getParent());
     
            route.add(edge.getLine() + " to " + destination); // record the destination in the route (reverse order)
            getPathBack(nextStationEdges, levelCount); // startPoint recursive route-back
     
            Collections.reverse(route);
        }
     
        /*
         * method that will traverse the next station
         * 
         * @param String destination - destination Station
         * @param StationEdge edge - the edge
         */
        private void traverseNextStations(String destination, StationEdge edge) {
            HashMap<String, ArrayList<StationEdge>> nextStation = new HashMap<String, ArrayList<StationEdge>>();
            ArrayList<StationEdge> endpointEdges = adjList.get(destination);
            levelTracker.put(destination, levelCount);
            nextStation.put(destination, endpointEdges); // create child station from destinaion
            visited.add(edge.getParent());
     
            queue.enqueue(nextStation); // add to queue
        }
     
     
     
        /**
         * startPoints with edges of destination station.
         * Examines each to see if edge points to parent of this station.
         * Defines parent as bring exactly one tree level less than the theStation level (levelCount).
         *
         * @param parentEdges
         * @param levelCount
         */
        public void getPathBack(ArrayList<StationEdge> parentEdges, int levelCount) {
            for (StationEdge edge : parentEdges) {
                    String potentialParentStation = edge.getNeighbour();
                    String line = edge.getLine();  //
                    int parentLevel = levelTracker.get(potentialParentStation);
                    if (visited.contains(potentialParentStation) && parentLevel == levelCount - 1
                                && !visitedParents.contains(potentialParentStation)) {
     
                            visitedParents.add(potentialParentStation);
                            route.add(line + " to " + potentialParentStation);
                            levelCount = levelCount - 1;
                            getPathBack(adjList.get(potentialParentStation), levelCount); 
                    }
                    else if (levelCount == 0) {
                            break;
                    }
            }
        }
    }

    I dont know if this is much help...if anybody is keen to help me I could email all my class files etc

    THanks
    Last edited by copeg; April 13th, 2011 at 06:14 PM.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Right so who is a Guru at BreadthFirstSearch ?

    For future reference, please use the code tags (see my sig for instructions).

    There seems to be a logic problem with you assertions:
    assert (neighbour=null) : "null neighbour in Check if have Traversed";

    I presume you want to check for null, not assign to null? (eg == rather than =)

  3. #3
    Junior Member
    Join Date
    Apr 2011
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Right so who is a Guru at BreadthFirstSearch ?

    Quote Originally Posted by copeg View Post
    For future reference, please use the code tags (see my sig for instructions).

    There seems to be a logic problem with you assertions:
    assert (neighbour=null) : "null neighbour in Check if have Traversed";

    I presume you want to check for null, not assign to null? (eg == rather than =)
    oh na i had assertions of anyway, mmm, i have no idea why it would work for some and not others. its random too. anyway of chucking up the src and text files for someone to look at?

Similar Threads

  1. J2SE, JSP, Servlets, JavaScprit Guru - London, £60-70K
    By iNeedJavaGurus in forum Paid Java Projects
    Replies: 0
    Last Post: September 18th, 2009, 09:59 AM