NBA*: Very efficient bidirectional heuristic search algorithm in Java

Question

(See also the next iteration.)

I have implemented NBA* (New Bidirectional A*) in Java and compared it against conventional A* and Dijkstra algorithms. The results may be as optimistic as this:

Seed = 8900460676230
Created the graph data structures in 2989 milliseconds.
Source: 80939
Target: 72799

A* in 120 milliseconds.
80939
10081
31889
11052
82854
72799

Dijkstra in 229 milliseconds.
80939
10081
31889
11052
82854
72799

NBA* in 3 milliseconds.
80939
10081
31889
11052
82854
72799

Algorithms agree: true

My code follows:

DirectedGraph.java:

package net.coderodde.graph;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * This class implements a directed graph data structure via adjacency lists. 
 * This implementation represents each graph node as an unique integer.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 6, 2016)
 */
public class DirectedGraph {

    /**
     * This map maps each directed graph node to the list of its child nodes.
     */
    private final Map<Integer, Set<Integer>> childMap  = new HashMap<>();

    /**
     * This map maps each directed graph node to the list of its parent nodes.
     */
    private final Map<Integer, Set<Integer>> parentMap = new HashMap<>();

    /**
     * Adds a new node represented by integer {@code nodeId} to this graph if
     * it is not yet present in it.
     * 
     * @param nodeId the node to add.
     */
    public void addNode(int nodeId) {
        childMap .putIfAbsent(nodeId, new HashSet<>());
        parentMap.putIfAbsent(nodeId, new HashSet<>());
    }

    /**
     * Creates a directed arc <tt>(tailNodeId, headNodeId)</tt> if it is not yet
     * present in the graph.
     * 
     * @param tailNodeId the tail node of the arc.
     * @param headNodeId the head node of the arc.
     */
    public void addArc(int tailNodeId, int headNodeId) {
        childMap .get(tailNodeId).add(headNodeId);
        parentMap.get(headNodeId).add(tailNodeId);
    }

    /**
     * Returns the view of all the nodes in this graph.
     * 
     * @return the set of all nodes.
     */
    public Set<Integer> getNodeList() {
        return childMap.keySet();
    }

    /**
     * Returns the set of all child nodes of the given node {@code nodeId}.
     * 
     * @param nodeId the node whose children to return.
     * @return the set of child nodes of {@code nodeId}.
     */
    public Set<Integer> getChildrenOf(int nodeId) {
        return Collections.<Integer>unmodifiableSet(childMap.get(nodeId));
    }

    /**
     * Returns the set of all parent nodes of the given node {@code nodeId}.
     * 
     * @param nodeId the node whose parents to return.
     * @return the set of parent nodes of {@code nodeId}.
     */
    public Set<Integer> getParentsOf(int nodeId) {
        return Collections.<Integer>unmodifiableSet(parentMap.get(nodeId));
    }
}

DirectedGraphWeightFunction.java:

package net.coderodde.graph;

import java.util.HashMap;
import java.util.Map;

/**
 * This class maps directed arcs to their weights. An arc weight is not allowed
 * to be a <tt>NaN</tt> value, nor negative.
 * 
 * @author Rodion "rodde" Efremov
 * @vesion 1.6 (Oct 6, 2016)
 */
public class DirectedGraphWeightFunction {

    /**
     * Maps the arcs to the arc weights.
     */
    private final Map<Integer, Map<Integer, Double>> map = new HashMap<>();

    /**
     * Associates the weight {@code weight} with the arc 
     * <tt>(tailNodeId, headNodeId)</tt>.
     * 
     * @param tailNodeId the starting node of the arc.
     * @param headNodeId the ending node of the arc.
     * @param weight the arc weight.
     */
    public void put(int tailNodeId, int headNodeId, double weight) {
        checkWeight(weight);
        map.putIfAbsent(tailNodeId, new HashMap<>());
        map.get(tailNodeId).put(headNodeId, weight);
    }

    /**
     * Returns the weight of the given arc.
     * 
     * @param tailNodeId the starting node (tail node) of the arc.
     * @param headNodeId the ending node (head node) of the arc.
     * @return 
     */
    public double get(int tailNodeId, int headNodeId) {
        return map.get(tailNodeId).get(headNodeId);
    }

    private void checkWeight(double weight) {
        if (Double.isNaN(weight)) {
            throw new IllegalArgumentException("The input weight is NaN.");
        }

        if (weight < 0.0) {
            throw new IllegalArgumentException(
                    "The input weight is negative: " + weight + ".");
        }
    }
}

AbstractPathfinder.java:

package net.coderodde.graph.pathfinding;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.DirectedGraphWeightFunction;

/**
 * This abstract class defines some facilities shared by pathfinding algorithms
 * and API for using them.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 6, 2016)
 */
public abstract class AbstractPathfinder {

    public static final class HeapEntry implements Comparable<HeapEntry> {

        private final int nodeId;
        private final double distance; // The priority key.

        public HeapEntry(int nodeId, double distance) {
            this.nodeId = nodeId;
            this.distance = distance;
        }

        public int getNode() {
            return nodeId;
        }

        public double getDistance() {
            return distance;
        }

        @Override
        public int compareTo(HeapEntry o) {
            return Double.compare(distance, o.distance);
        }
    }

    /**
     * The graph to search in.
     */
    protected final DirectedGraph graph;

    /**
     * The weight function to use.
     */
    protected final DirectedGraphWeightFunction weightFunction;

    protected AbstractPathfinder(DirectedGraph graph,
                                 DirectedGraphWeightFunction weightFunction) {
        this.graph = Objects.requireNonNull(graph, "The input graph is null.");
        this.weightFunction =
                Objects.requireNonNull(weightFunction,
                                       "The input weight function is null.");
    }

    protected AbstractPathfinder() {
        this.graph = null;
        this.weightFunction = null; // Compiler requires this initialization.
    }

    /**
     * Searches and returns a shortest path starting from the node 
     * {@code sourceNodeId} and leading to {@code targetNodeId}.
     * 
     * @param sourceNodeId the source node.
     * @param targetNodeId the target node.
     * @return a shortest path of nodes from source node to target node
     *         (including the terminal nodes) or an empty list if target is not
     *         reachable from source.
     */
    public abstract List<Integer> search(int sourceNodeId, int targetNodeId);

    /**
     * Reconstructs a shortest path from the data structures maintained by a 
     * <b>bidirectional</b> pathfinding algorithm.
     * 
     * @param touchNodeId the node where the two search frontiers agree.
     * @param PARENTSA the parent map in the forward search direction.
     * @param PARENTSB the parent map in the backward search direction.
     * @return the shortest path.
     */
    protected List<Integer> tracebackPath(int touchNodeId, 
                                          Map<Integer, Integer> PARENTSA,
                                          Map<Integer, Integer> PARENTSB) {
        List<Integer> path = new ArrayList<>();
        Integer currentNodeId = touchNodeId;

        while (currentNodeId != null) {
            path.add(currentNodeId);
            currentNodeId = PARENTSA.get(currentNodeId);
        }

        Collections.<Integer>reverse(path);

        if (PARENTSB != null) {
            currentNodeId = PARENTSB.get(touchNodeId);

            while (currentNodeId != null) {
                path.add(currentNodeId);
                currentNodeId = PARENTSB.get(currentNodeId);
            }
        }

        return path;
    }

    /**
     * Reconstructs a shortest path from the data structures maintained by a
     * unidirectional pathfinding algorithm.
     * 
     * @param targetNodeId the target node.
     * @param PARENTS      the parents map.
     * @return the shortest path.
     */
    protected List<Integer> tracebackPath(int targetNodeId, 
                                          Map<Integer, Integer> PARENTS) {
        return tracebackPath(targetNodeId, PARENTS, null);
    }
}

DirectedGraphNodeCoordinates.java:

package net.coderodde.graph.pathfinding;

import java.awt.geom.Point2D;
import java.util.HashMap;
import java.util.Map;

/**
 * This class allows mapping each graph node to its coordinates on a 
 * two-dimensional plane.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 6, 2016)
 */
public class DirectedGraphNodeCoordinates {

    /**
     * Maps each node to its coordinates.
     */
    private final Map<Integer, Point2D.Double> map = new HashMap<>();

    /**
     * Associates the coordinates {@code point} to the node {@code nodeId}.
     * 
     * @param nodeId the node to map.
     * @param point  the coordinates to associate to the node.
     */
    public void put(int nodeId, Point2D.Double point) {
        map.put(nodeId, point);
    }

    /**
     * Return the point of the input node.
     * 
     * @param nodeId the node whose coordinates to return.
     * @return the coordinates.
     */
    public Point2D.Double get(int nodeId) {
        return map.get(nodeId);
    }
}

HeuristicFunction.java:

package net.coderodde.graph.pathfinding;

/**
 * This interface defines the API for heuristic functions used in pathfinding.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 6, 2016)
 */
public interface HeuristicFunction {

    /**
     * Provides an optimistic (underestimated) distance between {@code nodeId1}
     * and {@code nodeId2} using a specific distance metric.
     * 
     * @param nodeId1 the first node.
     * @param nodeId2 the second node.
     * @return a shortest path estimate between the two input nodes.
     */
    public double estimateDistanceBetween(int nodeId1, int nodeId2);
}

EuclideanHeuristicFunction.java:

package net.coderodde.graph.pathfinding.support;

import java.util.Objects;
import net.coderodde.graph.pathfinding.DirectedGraphNodeCoordinates;
import net.coderodde.graph.pathfinding.HeuristicFunction;

/**
 * This class implements a heuristic function that returns the Euclidean
 * distance between two given nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 6, 2016)
 */
public class EuclideanHeuristicFunction implements HeuristicFunction {

    private final DirectedGraphNodeCoordinates coordinates;

    public EuclideanHeuristicFunction(DirectedGraphNodeCoordinates coordinates) {
        this.coordinates =
                Objects.requireNonNull(coordinates,
                                       "The input coordinate map is null.");
    }

    /**
     * {@inheritDoc }
     */
    @Override
    public double estimateDistanceBetween(int nodeId1, int nodeId2) {
        return coordinates.get(nodeId1).distance(coordinates.get(nodeId2));
    }
}

ZeroHeuristicFunction.java:

package net.coderodde.graph.pathfinding.support;

import net.coderodde.graph.pathfinding.HeuristicFunction;

public class ZeroHeuristicFunction implements HeuristicFunction {

    @Override
    public double estimateDistanceBetween(int nodeId1, int nodeId2) {
        return 0.0;
    }
}

AStarPathfinder.java:

package net.coderodde.graph.pathfinding.support;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Set;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.DirectedGraphWeightFunction;
import net.coderodde.graph.pathfinding.AbstractPathfinder;
import net.coderodde.graph.pathfinding.HeuristicFunction;

public final class AStarPathfinder extends AbstractPathfinder {

    private final HeuristicFunction heuristicFunction;
    private final PriorityQueue<HeapEntry> OPEN = new PriorityQueue<>();
    private final Set<Integer> CLOSED = new HashSet<>();
    private final Map<Integer, Double> DISTANCE = new HashMap<>();
    private final Map<Integer, Integer> PARENTS = new HashMap<>();

    public AStarPathfinder(DirectedGraph graph,
                           DirectedGraphWeightFunction weightFunction,
                           HeuristicFunction heuristicFunction) {
        super(graph, weightFunction);
        this.heuristicFunction = 
                Objects.requireNonNull(heuristicFunction,
                                       "The input heuristic function is null.");
    }

    @Override
    public List<Integer> search(int sourceNodeId, int targetNodeId) {
        init(sourceNodeId);

        while (!OPEN.isEmpty()) {
            Integer currentNodeId = OPEN.remove().getNode();

            if (currentNodeId.equals(targetNodeId)) {
                return tracebackPath(currentNodeId, PARENTS);
            }

            if (CLOSED.contains(currentNodeId)) {
                continue;
            }

            CLOSED.add(currentNodeId);

            for (Integer childNodeId : graph.getChildrenOf(currentNodeId)) {
                if (CLOSED.contains(childNodeId)) {
                    continue;
                }

                double tentativeDistance = 
                        DISTANCE.get(currentNodeId) +
                        weightFunction.get(currentNodeId, childNodeId);

                if (!DISTANCE.containsKey(childNodeId)
                        || DISTANCE.get(childNodeId) > tentativeDistance) {
                    DISTANCE.put(childNodeId, tentativeDistance);
                    PARENTS.put(childNodeId, currentNodeId);
                    OPEN.add(
                        new HeapEntry(
                            childNodeId, 
                            tentativeDistance +
                            heuristicFunction
                                    .estimateDistanceBetween(childNodeId, 
                                                             targetNodeId)));
                }
            }
        }

        return new ArrayList<>();
    }

    private void init(int sourceNodeId) {
        OPEN.clear();
        CLOSED.clear();
        PARENTS.clear();
        DISTANCE.clear();

        OPEN.add(new HeapEntry(sourceNodeId, 0.0));
        PARENTS.put(sourceNodeId, null);
        DISTANCE.put(sourceNodeId, 0.0);
    }
}

DijkstraPathfinder.java:

package net.coderodde.graph.pathfinding.support;

import java.util.List;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.DirectedGraphWeightFunction;
import net.coderodde.graph.pathfinding.AbstractPathfinder;

public final class DijkstraPathfinder extends AbstractPathfinder {

    private final AStarPathfinder finderImplementation;

    public DijkstraPathfinder(DirectedGraph graph,
                              DirectedGraphWeightFunction weightFunction) {
        this.finderImplementation = 
                new AStarPathfinder(graph, 
                                    weightFunction,
                                    new ZeroHeuristicFunction());
    }

    @Override
    public List<Integer> search(int sourceNodeId, int targetNodeId) {
        return finderImplementation.search(sourceNodeId, targetNodeId);
    }
}

NBAStarPathfinder.java:

package net.coderodde.graph.pathfinding.support;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Set;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.DirectedGraphWeightFunction;
import net.coderodde.graph.pathfinding.AbstractPathfinder;
import net.coderodde.graph.pathfinding.HeuristicFunction;

/**
 * This pathfinding algorithm is due to Wim Pijls and Henk Post in "Yet another
 * bidirectional algorithm for shortest paths." 15 June 2009.
 * <p>
 * <b>This class is not thread-safe.</b> If you need it in different threads,
 * make sure each thread has its own object of this class.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 6, 2016)
 */
public final class NBAStarPathfinder extends AbstractPathfinder {

    private final HeuristicFunction heuristicFunction;
    private final PriorityQueue<HeapEntry> OPENA = new PriorityQueue<>();
    private final PriorityQueue<HeapEntry> OPENB = new PriorityQueue<>();
    private final Map<Integer, Integer> PARENTSA = new HashMap<>();
    private final Map<Integer, Integer> PARENTSB = new HashMap<>();
    private final Map<Integer, Double> DISTANCEA = new HashMap<>();
    private final Map<Integer, Double> DISTANCEB = new HashMap<>();
    private final Set<Integer> CLOSED = new HashSet<>();

    private double fA;
    private double fB;
    private double bestPathLength;
    private Integer touchNode;
    private Integer sourceNodeId;
    private Integer targetNodeId;

    public NBAStarPathfinder(DirectedGraph graph,
            DirectedGraphWeightFunction weightFunction,
            HeuristicFunction heuristicFunction) {
        super(graph, weightFunction);
        this.heuristicFunction
                = Objects.requireNonNull(heuristicFunction,
                        "The input heuristic function is null.");
    }

    @Override
    public List<Integer> search(int sourceNodeId, int targetNodeId) {
        if (sourceNodeId == targetNodeId) {
            return new ArrayList<>(Arrays.asList(sourceNodeId));
        }

        init(sourceNodeId, targetNodeId);

        while (!OPENA.isEmpty() && !OPENB.isEmpty()) {
            if (OPENA.size() < OPENB.size()) {
                expandInForwardDirection();
            } else {
                expandInBackwardDirection();
            }
        }

        if (touchNode == null) {
            return new ArrayList<>();
        }

        return tracebackPath(touchNode, PARENTSA, PARENTSB);
    }

    private void expandInForwardDirection() {
        Integer currentNode = OPENA.remove().getNode();

        if (CLOSED.contains(currentNode)) {
            return;
        }

        CLOSED.add(currentNode);

        if (DISTANCEA.get(currentNode) +
                heuristicFunction.estimateDistanceBetween(currentNode,
                                                          targetNodeId)
                >= bestPathLength
                ||
                DISTANCEA.get(currentNode) +
                fB - 
                heuristicFunction.estimateDistanceBetween(currentNode,
                                                          sourceNodeId)
                >= bestPathLength) {
            // Reject the 'currentNode'.
        } else {
            // Stabilize the 'currentNode'.
            for (Integer childNode : graph.getChildrenOf(currentNode)) {
                if (CLOSED.contains(childNode)) {
                    continue;
                }

                double tentativeDistance
                        = DISTANCEA.get(currentNode)
                        + weightFunction.get(currentNode, childNode);

                if (!DISTANCEA.containsKey(childNode)
                        || 
                        DISTANCEA.get(childNode) > tentativeDistance) {
                    DISTANCEA.put(childNode, tentativeDistance);
                    PARENTSA.put(childNode, currentNode);
                    HeapEntry e
                            = new HeapEntry(
                                    childNode,
                                    tentativeDistance
                                    + heuristicFunction
                                    .estimateDistanceBetween(childNode,
                                                             targetNodeId));
                    OPENA.add(e);

                    if (DISTANCEB.containsKey(childNode)) {
                        double pathLength = tentativeDistance
                                + DISTANCEB.get(childNode);

                        if (bestPathLength > pathLength) {
                            bestPathLength = pathLength;
                            touchNode = childNode;
                        }
                    }
                }
            }
        }

        if (!OPENA.isEmpty()) {
            fA = OPENA.peek().getDistance();
        }
    }

    private void expandInBackwardDirection() {
        Integer currentNode = OPENB.remove().getNode();

        if (CLOSED.contains(currentNode)) {
            return;
        }

        CLOSED.add(currentNode);

        if (DISTANCEB.get(currentNode) +
                heuristicFunction
                .estimateDistanceBetween(currentNode,
                                         sourceNodeId)
                >= bestPathLength
                || 
                DISTANCEB.get(currentNode) +
                fA -
                heuristicFunction
                .estimateDistanceBetween(currentNode, targetNodeId)
                >= bestPathLength) {
            // Reject the node 'currentNode'.
        } else {
            for (Integer parentNode : graph.getParentsOf(currentNode)) {
                if (CLOSED.contains(parentNode)) {
                    continue;
                }

                double tentativeDistance
                        = DISTANCEB.get(currentNode)
                        + weightFunction.get(parentNode, currentNode);

                if (!DISTANCEB.containsKey(parentNode)
                        || DISTANCEB.get(parentNode)
                        > tentativeDistance) {
                    DISTANCEB.put(parentNode, tentativeDistance);
                    PARENTSB.put(parentNode, currentNode);
                    HeapEntry e
                            = new HeapEntry(parentNode,
                                    tentativeDistance
                                    + heuristicFunction
                                    .estimateDistanceBetween(parentNode,
                                                             targetNodeId));
                    OPENB.add(e);

                    if (DISTANCEA.containsKey(parentNode)) {
                        double pathLength = tentativeDistance
                                + DISTANCEA.get(parentNode);

                        if (bestPathLength > pathLength) {
                            bestPathLength = pathLength;
                            touchNode = parentNode;
                        }
                    }
                }
            }
        }

        if (!OPENB.isEmpty()) {
            fB = OPENB.peek().getDistance();
        }
    }

    private void init(Integer sourceNodeId, Integer targetNodeId) {
        OPENA.clear();
        OPENB.clear();
        PARENTSA.clear();
        PARENTSB.clear();
        DISTANCEA.clear();
        DISTANCEB.clear();
        CLOSED.clear();

        double totalDistance
                = heuristicFunction.estimateDistanceBetween(sourceNodeId,
                        targetNodeId);

        fA = totalDistance;
        fB = totalDistance;
        bestPathLength = Double.MAX_VALUE;
        touchNode = null;
        this.sourceNodeId = sourceNodeId;
        this.targetNodeId = targetNodeId;

        OPENA.add(new HeapEntry(sourceNodeId, fA));
        OPENB.add(new HeapEntry(targetNodeId, fB));
        PARENTSA.put(sourceNodeId, null);
        PARENTSB.put(targetNodeId, null);
        DISTANCEA.put(sourceNodeId, 0.0);
        DISTANCEB.put(targetNodeId, 0.0);
    }
}

Demo.java:

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.DirectedGraphWeightFunction;
import net.coderodde.graph.pathfinding.AbstractPathfinder;
import net.coderodde.graph.pathfinding.DirectedGraphNodeCoordinates;
import net.coderodde.graph.pathfinding.HeuristicFunction;
import net.coderodde.graph.pathfinding.support.AStarPathfinder;
import net.coderodde.graph.pathfinding.support.DijkstraPathfinder;
import net.coderodde.graph.pathfinding.support.EuclideanHeuristicFunction;
import net.coderodde.graph.pathfinding.support.NBAStarPathfinder;

public class Demo {

    private static final int NODES = 100_000;
    private static final int ARCS = 500_000;

    public static void main(String[] args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        System.out.println("Seed = " + seed);

        long start = System.currentTimeMillis();
        DirectedGraph graph = getRandomGraph(NODES, ARCS, random);
        DirectedGraphNodeCoordinates coordinates = getCoordinates(graph, 
                                                                  random);
        DirectedGraphWeightFunction weightFunction = 
                getWeightFunction(graph, coordinates);

        List<Integer> graphNodeList = new ArrayList<>(graph.getNodeList());

        Integer sourceNodeId = choose(graphNodeList, random);
        Integer targetNodeId = choose(graphNodeList, random);
        long end = System.currentTimeMillis();

        System.out.println("Created the graph data structures in " +
                           (end - start) + " milliseconds.");

        System.out.println("Source: " + sourceNodeId);
        System.out.println("Target: " + targetNodeId);

        System.out.println();

        HeuristicFunction hf = new EuclideanHeuristicFunction(coordinates);

        AbstractPathfinder finder1 = new AStarPathfinder(graph,
                                                         weightFunction,
                                                         hf);

        AbstractPathfinder finder2 = new DijkstraPathfinder(graph,
                                                            weightFunction);

        AbstractPathfinder finder3 = new NBAStarPathfinder(graph, 
                                                           weightFunction,
                                                           hf);
        start = System.currentTimeMillis();
        List<Integer> path1 = finder1.search(sourceNodeId, targetNodeId);
        end = System.currentTimeMillis();

        System.out.println("A* in " + (end - start) + " milliseconds.");

        path1.forEach(System.out::println);
        System.out.println();

        start = System.currentTimeMillis();
        List<Integer> path2 = finder2.search(sourceNodeId, targetNodeId);
        end = System.currentTimeMillis();

        System.out.println("Dijkstra in " + (end - start) + " milliseconds.");
        path2.forEach(System.out::println);
        System.out.println();

        start = System.currentTimeMillis();
        List<Integer> path3 = finder3.search(sourceNodeId, targetNodeId);
        end = System.currentTimeMillis();

        System.out.println("NBA* in " + (end - start) + " milliseconds.");
        path3.forEach(System.out::println);
        System.out.println();

        System.out.println("Algorithms agree: " +
                (path1.equals(path2) && path1.equals(path3)));
    }

    private static DirectedGraph getRandomGraph(int nodes, 
                                                int arcs, 
                                                Random random) {
        DirectedGraph graph = new DirectedGraph();

        for (int id = 0; id < nodes; ++id) {
            graph.addNode(id);
        }

        List<Integer> graphNodeList = new ArrayList<>(graph.getNodeList());

        while (arcs-- > 0) {
            Integer tailNodeId = choose(graphNodeList, random);
            Integer headNodeId = choose(graphNodeList, random);
            graph.addArc(tailNodeId, headNodeId);
        }

        return graph;
    }

    private static DirectedGraphNodeCoordinates 
        getCoordinates(DirectedGraph graph, Random random) {
        DirectedGraphNodeCoordinates coordinates =
                new DirectedGraphNodeCoordinates();

        for (Integer nodeId : graph.getNodeList()) {
            coordinates.put(nodeId, randomPoint(1000.0, 1000.0, random));
        }

        return coordinates;
    }

    private static DirectedGraphWeightFunction 
        getWeightFunction(DirectedGraph graph,
                          DirectedGraphNodeCoordinates coordinates) {
        DirectedGraphWeightFunction weightFunction = 
                new DirectedGraphWeightFunction();

        for (Integer nodeId : graph.getNodeList()) {
            Point2D.Double p1 = coordinates.get(nodeId);

            for (Integer childNodeId : graph.getChildrenOf(nodeId)) {
                Point2D.Double p2 = coordinates.get(childNodeId);
                double distance = p1.distance(p2);
                weightFunction.put(nodeId, childNodeId, 1.2 * distance);
            }
        }

        return weightFunction;
    }

    private static Point2D.Double randomPoint(double width,
                                              double height,
                                              Random random) {
        return new Point2D.Double(width * random.nextDouble(),
                                  height * random.nextDouble());
    }

    private static <T> T choose(List<T> list, Random random) {
        return list.get(random.nextInt(list.size()));
    }
}

Critique request

I wish to hear how can I improve the following:

• API design,
• naming conventions,
• coding conventions,
• commenting,
• modularity.

Answer 1

(Personal note: Good work, this is an excellent resource. Can I bookmark/reuse?)

What is this for?

protected AbstractPathfinder() {
    this.graph = null;
    this.weightFunction = null; // Compiler requires this initialization.
}

This allows someone to declare a pathinder that has no idea on which graph it is acting. This does not strike me as useful, but it does look dangerous (final values are set to null). We should kill it with fire! Let's see how:

It is required by another part in DijkstraPathfinder. Basically, you've made it extends AbstractPathfinder, and delegate its search method to a purpose-build AStarPathfinder. Why not make Dijkstra be that AStarPathfinder instance? Like so:

public final class DijkstraPathfinder extends AStarPathfinder {

    public DijkstraPathfinder(DirectedGraph graph,
                              DirectedGraphWeightFunction weightFunction) {
        super(graph, weightFunction, new ZeroHeuristicFunction());
    }
}

Job done, and you can destroy that annoying Constructor in AbstractPathfinder.

Richer return values

Right now your Pathfinders produce a List<Integer> as a path. If there is no path, the list is empty.

Consider using a dedicated Path object to allow the user to poll the result status:

public interface Path {
    public static enum PathState {
         SUCCESS, ERROR, NO_PATH, UNFINISHED
    }
    PathStatus getStatus();
    List<Integer> getPath();
    List<Point2D.Double> get2dPath(DirectedGraphNodeCoordinates coords); // Maybe?
    double getPathCost(); // This is severely lacking
}

Why expose a Stateful Pathfinder?

The Pathfinder instances have a state, that they keep from one search call to the next. Is that useful? Is the remainder state re-used for subsequent calls to search?

• It could be reused for Dijkstra, keeping the same start cell but aiming for another end cell. But it's not possible, because you've made Dijkstra a special case of AStar...
• It might be used for AStar, but if the goal has changed, so has the heuristic, and the whole computation might become obsolete, I'm nto too sure.
• It's probably very hard to reuse the NBAStarPathfinder for the above reasons.

So, why expose a stateful Pathfinder instance? I would rather limit the Pathfinder to having a DirectedGraph and DirectedGraphWeightFunction like it does (so that it can be used for several paths on the same graph), but not have computation-related states, like each implementation has (CLOSED and OPEN lists etc).

In summary, the pathfinder's search method should not have side-effects. This is not a design problem, but an implementation problem in AStarPathfinder, DijkstraPathfinder, and NBAStarPathfinder.

Why not provide a more useful stateful Object?

It may still be useful to expose a stateful pathfinder for an other feature: computation control. You rightly decided to leave Multithreading out, but haven't given your users the tools to make it happen themselves.

We all know pathfinding quickly become a resource-hungry beast. Why not provide hooks to control your method's execution?

public abstract class AbstractPathfinder {
    [blah, blah, blah, everything was fine here]
    // Replace the search: provide a controller instead of straigh execution
    public abstract PathfinderController search(int sourceNodeId, int targetNodeId);
    [Blah, blah]
}

public interface PathfinderController {
    boolean iterateOnce(); // Explores just ONE cell. Return true if succeeded
    boolean iterate(long timeout);  // Explores until the timeout. Return true if succeeded
    Path finish();  // Finish the computation (blocking). Return the Path Object
    PathStatus hasFinished(); // Return the current status
}

This way your user can pace the computation as they want. The Pathfinder is unchanged , but the PathfinderController holds the computation state and can deliver the final Path.

The Trace back methods

Pathfinder's tracebackPath methods feels awkward.

Hint N°1: make it static, it still works. This marks it as a helper function.

Hint N°2: You have two versions, one for each pathfinder implementation. It might not help a RandomPathfinder, or a RightHandWallFollowerPathfinder. So take it out of there, and move it to the right class, as it is an implementation detail.

Naming conventions

I would rename EuclideanHeuristicFunction as EuclidianDistance because that is more accurate.

I would rename DirectedGraphNodeCoordinates as NodeCoordinates because you don't need to know those coordinates apply to nodes from a graph, or that the graph has directed edges. All around, the DirectedGraph prefix is often superfluous.

DirecteGraph.addArc(tailNodeId, headNodeId) should be DirecteGraph.addArc(headNodeId, tailNodeId), I think

Commenting is good

All is said. Although I did not follow NBAStar entirely, I must admit ;) There are very tricky end conditions to bi directional AStar, I'll trust your implementation on this.

Careful though, is the HeuristicFunction estimation supposed to be symmetric : estimateDistanceBetween(nodeId1, nodeId2) == estimateDistanceBetween(node2Id, node1Id) ?
Because it is not specified, and in expandInBackwardDirection() you might obtain invalid heuristic values. But this is really tortured thinking anyway...

Modularity

Is very good, you provide good interfaces.

However, when faced with i.e. implicit problems, that can have infinite states (most of which should never be explored), the user will have to instantiate most states and arcs, and hope all the required ones are there...

It might be good to provide a:

public interface Node{
    public List<Node> neighbours();
}

But this will go against the use of Integer as node Ids, because you cannot force the user to think with IDs...

This is a (minor) limitation of the current design.

Overall

Good job, I've tried to be very mean, and I can see myself using this quite easily!