A* search algorithm

NodeData stores all information of the node needed by the AStar
algorithm. This information includes the value of g, h, and f.
However, the value of all 3 variables are dependent on source and
destination, thus obtains at runtime.

@param 

I'm looking for reviews on optimization, accuracy and best practices.

```
final class NodeData {

private final T nodeId;
private final Map heuristic;

private double g; // g is distance from the source
private double h; // h is the heuristic of destination.
private double f; // f = g + h

public NodeData (T nodeId, Map heuristic) {
this.nodeId = nodeId;
this.g = Double.MAX_VALUE;
this.heuristic = heuristic;
}

public T getNodeId() {
return nodeId;
}

public double getG() {
return g;
}

public void setG(double g) {
this.g = g;
}

public void calcF(T destination) {
this.h = heuristic.get(destination);
this.f = g + h;
}

public double getH() {
return h;
}

public double getF() {
return f;
}
}

/**
* The graph represents an undirected graph.
*
* @author SERVICE-NOW\ameya.patil
*
* @param
*/
final class GraphAStar implements Iterable {
/*
* A map from the nodeId to outgoing edge.
* An outgoing edge is represented as a tuple of NodeData and the edge length
*/
private final Map, Double>> graph;
/*
* A map of heuristic from a node to each other node in the graph.
*/
private final Map> heuristicMap;
/*
* A map between nodeId and nodedata.
*/
private final Map> nodeIdNodeData;

public GraphAStar(Map> heuristicMap) {
if (heuristicMap == null) throw new NullPointerException("The huerisic map should not be null");
graph = new HashMap, Double>>();
nodeIdNodeData = new HashMap>();
this.heuristicMap = heuristicMap;
}

/**
* Adds a new node t

This is quite good and professional-looking code. There are many small aspects which I really like:

• Using Collections.unmodifiableMap instead of a shallow copy is brilliant.

• The use of a generic nodeId is clever and makes for elegant code.

• There are input checks in all public methods (well, there are some exceptions: only the AStar and NodeData constructors, NodeComparator#compare, and AStar#astar are not checked).

• You make perfect use of empty lines to separate unrelated blocks.

But there were some aspects that made your code sometimes a bit harder to follow:

-
Lack of encapsulation of some parts like heuristic: What is this Map>? Can't I have nice self-documenting accessors for a Heuristic instance?

-
Sequential coupling in NodeData: whenever I setG I also have to call calcF. You could have made this easier by slapping a return this in there instead of void methods, but the real solution is to get rid of public calcF and make it private instead. The NodeData class is responsible on its own to maintain its invariants, so any call to setG should update dependent fields.

-
Bad naming. The letters g, f and h have a specific meaning in the context of A* and are OK here. Of course it would have been better to include a link to this algorithm's Wikipedia page so that a future maintainer can understand why you used g instead of distance.

But nodes don't have a distance, nodes or edges have weights. In the context of optimization problems it is also common to talk about a cost – a term which does not occur once in your code.

It's called heuristic, not hueristic. Typos are easy to correct, and should be corrected while they're still young (The origin of the referer field in a HTTP request should be edutaining here).

-
There are some formatting “errors” that can be easily rectified by an automatic formatter. E.g. don't use braces when a conditional is on a single line like if (cond) { single_statement; } – removing the braces reduces line noise. Otherwise, you could also put the statement on its own line.

Some of your lines are excessively long and should be broken up (see also the next tip).

-
As laudable as your input checks are, they do add visual clutter. Consider hiding them behind helper methods, e.g. heuristic.assertContains(nodeId) or preferably Assert.nonNull(nodeId, "node") (which assumes a whole class dedicated to input checking). Arguments against this are less useful stack traces and reduced performance (method call overhead, compiler optimizations are more difficult), but pro-arguments include more self-documenting, concise code.

Other notes:

-
Your documentation does not state what happens when there is no path from the start to the destination (e.g. if the nodes are in unconnected subgraphs). The implementation is rather clear here: A null is returned instead of a list.

-
The Pseudocode given on the A* Wikipedia page uses a slightly different condition for updating the path and possibly adding neighbours to the openQueue:

if (!openQueue.contains(neighbor) || tentativeG < neighbor.getG())`

whereas you use if (tentativeG

-
You could translate between T instances and a continuous range of ints at your component's boundaries (in other words: internally, every nodeId would be an integer). Using integers allows for more efficient data structures like arrays. This would remove most Map lookups, but also the NodeData` class. The disadvantage is that your code would look like C afterwards… I would just try out the transformation and see (a) whether there is a noticeable increase in performance and (b) whether the increased ugliness is really worth it.

StackExchange Code Review Q#38376, answer score: 21