#1 Null check is needed in Graph.getEdgeList(int node) method.

[Syng Park]

Class: Graph
Method: public LinkedList<graphedge> getEdgeList(int nodeID)</graphedge>

In the provided search implementations, the algorithm relies on a method (getEdgeList) to retrieve a list of edges based on a given node ID. The algorithm assumes the returned list is not null and iterates the list. However, there are instances where getEdgeList() returns null, thus causing a NullPointerException.

We're working around this problem by extending Graph class and checking for null.

public class PatchedUpGraph extends Graph {

/**
 * @see pathfinder.Graph#getEdgeList(pathfinder.GraphNode)
 */
@Override
public LinkedList<GraphEdge> getEdgeList(int nodeID) {
    LinkedList<GraphEdge> lEdgeList = null;

    // null check
    if (edgeLists != null) {
        lEdgeList = edgeLists.get(nodes.get(nodeID));
    }

    // never return null, instead return empty list
    if (lEdgeList == null) {
        lEdgeList = new LinkedList<GraphEdge>();
    }

    return lEdgeList;
}

}

[Syng Park]

We had to create the PatchedUpGraph class to use the #search on GraphSearch_Astar and GraphSearch_Djikstra (instead of the Graph class in the Path Finder library) to avoid a null pointer exception. The NPE was coming from #search because it has a for loop that is not null safe. The Graph#getEdgeList(int) method will return a null if the given node does not have any edges (in an internal map). The key here is that this method will only return edges where the given node is the departure. While we are building our Graph object, we are forced to insert nodes like this. While there are no orphaned nodes (a node that is not used in any edge), we do have some nodes that are only used as a destination. This happens in the case below:

N12C,10,DOVEY,K6,B,F,0408,41.11666667,-67
N12C,20,SAILE,K6,B,,,41.18576944,-67.89571111

F,0408 from DOVEY indicates forward and distance of 408

DOVEY to SAILE is an edge. But this is a forwards-only edge. Since SAILE is the end of a segment (no distance value, and it is the end of the route), it is never used as a departure. So the #getEdgeList returns a null when you give it SAILE as a node. So any time the #search is required to iterate through the SAILE node, it will throw an NPE. The PatchedUpGraph class overrides the #getEdgeList(int) method and returns an empty list when there are no edges in the map for the given node. That way the for loop in #search doesn’t throw the NPE and the processing completes like it should.

[Quarks Processing]

Thanks for reporting this problem, I must admit I never considered dead-end nodes when testing.

Couple of points:

edgeLists is never null because it is created in the Graph constructor. Wouldn't be much of a graph without that ;)

There are 2 getEdgeList methods (method overloading) in the graph class depending on whether you supply a node or a node ID. It is important that these 2 methods have the same behaviour. So until I release a new version I suggest you include these methods in your PatchedUpGraph class and let me know how you got on.

/**
 * Gets a list of GraphEdges from this node. <br>
 * Used by graph search classes.
 * 
 * @param nodeID id of the node where the edges start from
 * @return a list of departing edges (the list will be empty if no departing edges)
 */
public LinkedList<GraphEdge> getEdgeList(int nodeID){
    return getEdgeList(nodes.get(nodeID));
}

/**
 * Gets a list of GraphEdges from this node. <br>
 * Used by graph search classes.
 * @param node the node where the edges start from
 * @return a list of departing edges (the list wil be empty if no departing edges)
 */
public LinkedList<GraphEdge> getEdgeList(GraphNode node){
    LinkedList<GraphEdge> edgeList = null;
    if(node != null)
    edgeList = edgeLists.get(node);
    // Can't find edge list so return empty list
    if (edgeList == null)
        edgeList = new LinkedList<GraphEdge>();
    return edgeList;
}

[Quarks Processing]

Fixed in version 0.1.4