Thread: 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

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 =)