LibID: a Java library containing some iterative deepening algorithms for pathfinding on directed unweighted graphs

Question

Intro

I have this GitHub repository containing some iterative deepening pathfinding algorithms.

Code

io.github.coderodde.libid.impl.BidirectionalIterativeDeepeningDepthFirstSearch.java::

package io.github.coderodde.libid.impl;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import io.github.coderodde.libid.NodeExpander;
public final class BidirectionalIterativeDeepeningDepthFirstSearch<N> {
 private final N source;
 private final Deque<N> backwardSearchStack;
 private final Set<N> frontier;
 private final Set<N> visitedForward;
 private final Set<N> visitedBackward;
 private final NodeExpander<N> forwardExpander;
 private final NodeExpander<N> backwardExpander;
 private int previousVisitedSizeForward;
 private int previousVisitedSizeBackward;
 public BidirectionalIterativeDeepeningDepthFirstSearch() {
 this.source = null;
 this.backwardSearchStack = null;
 this.frontier = null;
 this.visitedForward = null;
 this.visitedBackward = null;
 this.forwardExpander = null;
 this.backwardExpander = null;
 }
 private BidirectionalIterativeDeepeningDepthFirstSearch(
 N source,
 NodeExpander<N> forwardExpander,
 NodeExpander<N> backwardExpander) {
 this.source = source;
 this.backwardSearchStack = new ArrayDeque<>();
 this.frontier = new HashSet<>();
 this.visitedForward = new HashSet<>();
 this.visitedBackward = new HashSet<>();
 this.forwardExpander = forwardExpander;
 this.backwardExpander = backwardExpander;
 this.previousVisitedSizeForward = 0;
 this.previousVisitedSizeBackward = 0;
 }
 public List<N> search(N source, 
 N target, 
 NodeExpander<N> forwardExpander,
 NodeExpander<N> backwardExpander) {
 // Handle the easy case. We need this in order to terminate the 
 // recursion in buildPath.
 if (source.equals(target)) {
 return new ArrayList<>(Arrays.asList(source));
 }
 BidirectionalIterativeDeepeningDepthFirstSearch<N> state = 
 new BidirectionalIterativeDeepeningDepthFirstSearch<>(
 source,
 forwardExpander,
 backwardExpander);
 for (int forwardDepth = 0;; ++forwardDepth) {
 state.visitedForward.clear();
 
 // Do a depth limited search in forward direction. Put all nodes at 
 // depth == 0 to the frontier.
 state.depthLimitedSearchForward(source, forwardDepth);
 
 if (state.visitedForward.size() == 
 state.previousVisitedSizeForward) {
 return null;
 }
 
 state.previousVisitedSizeForward = state.visitedForward.size();
 state.visitedForward.clear();
 
 for (int backwardDepth = forwardDepth;
 backwardDepth < forwardDepth + 2;
 backwardDepth++) {
 
 N meetingNode = state.depthLimitedSearchBackward(target,
 backwardDepth);
 if (meetingNode != null) {
 return state.buildPath(meetingNode);
 }
 if (state.visitedForward.size() == 
 state.previousVisitedSizeForward) {
 return null;
 }
 state.previousVisitedSizeBackward =
 state.visitedBackward.size();
 
 state.visitedBackward.clear();
 }
 
 state.frontier.clear();
 }
 }
 private void depthLimitedSearchForward(N node, int depth) {
 if (visitedForward.contains(node)) {
 return;
 }
 
 visitedForward.add(node);
 
 if (depth == 0) {
 frontier.add(node);
 return;
 }
 for (N child : forwardExpander.expand(node)) {
 depthLimitedSearchForward(child, depth - 1);
 }
 }
 private N depthLimitedSearchBackward(N node, int depth) {
 if (visitedBackward.contains(node)) {
 return null;
 }
 
 visitedBackward.add(node); 
 backwardSearchStack.addFirst(node);
 if (depth == 0) {
 if (frontier.contains(node)) {
 return node;
 }
 backwardSearchStack.removeFirst();
 return null;
 }
 for (N parent : backwardExpander.expand(node)) {
 N meetingNode = depthLimitedSearchBackward(parent, depth - 1);
 if (meetingNode != null) {
 return meetingNode;
 } 
 }
 backwardSearchStack.removeFirst();
 return null;
 }
 private List<N> buildPath(N meetingNode) {
 List<N> path = new ArrayList<>();
 List<N> prefixPath = 
 new BidirectionalIterativeDeepeningDepthFirstSearch<N>()
 .search(source, 
 meetingNode, 
 forwardExpander, 
 backwardExpander);
 path.addAll(prefixPath);
 path.remove(path.size() - 1);
 path.addAll(backwardSearchStack);
 return path;
 }
}

io.github.coderodde.libid.impl.IterativeDeepeningAStar.java::

package io.github.coderodde.libid.impl;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import io.github.coderodde.libid.IntHeuristicFunction;
import io.github.coderodde.libid.NodeExpander;
public final class IterativeDeepeningAStar<N> {
 private static final int RUNNING = 0;
 private static final int FOUND = 1;
 
 private final N target;
 private final IntHeuristicFunction<N> heuristicFunction;
 private final NodeExpander<N> expander;
 private final List<N> path;
 
 private int status = RUNNING;
 
 public IterativeDeepeningAStar() {
 this.target = null;
 this.heuristicFunction = null;
 this.expander = null;
 this.path = null;
 }
 
 private IterativeDeepeningAStar(
 N target,
 IntHeuristicFunction<N> heuristicFunction,
 NodeExpander<N> expander) {
 this.target = target;
 this.heuristicFunction = heuristicFunction;
 this.expander = expander;
 this.path = new ArrayList<>();
 }
 
 public List<N> search(N source, 
 N target, 
 NodeExpander<N> expander, 
 IntHeuristicFunction<N> heuristicFunction) {
 IterativeDeepeningAStar<N> state = 
 new IterativeDeepeningAStar<>(target,
 heuristicFunction, 
 expander);
 
 int bound = heuristicFunction.estimate(source, target);
 
 while (true) {
 int t = state.search(source, 0, bound);
 
 if (state.status == FOUND) {
 Collections.<N>reverse(state.path);
 return state.path;
 }
 
 if (t == Integer.MAX_VALUE) {
 throw new IllegalStateException("Target not reachable");
 }
 
 bound = t;
 }
 }
 
 private int search(N node, int g, int bound) {
 int f = g + heuristicFunction.estimate(node, target);
 
 if (f > bound) {
 return f;
 }
 
 if (node.equals(target)) {
 path.add(target);
 status = FOUND;
 return 0;
 }
 
 int min = Integer.MAX_VALUE;
 
 for (N child : expander.expand(node)) {
 int t = search(child, g + 1, bound);
 
 if (status == FOUND) {
 path.add(node);
 return 0;
 }
 
 min = Math.min(min, t);
 }
 
 return min;
 }
}

io.github.coderodde.libid.impl.IterativeDeepeningDepthFirstSearch.java::

package io.github.coderodde.libid.impl;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import io.github.coderodde.libid.NodeExpander;
import io.github.coderodde.libid.demo.SlidingTilePuzzleNode;
public final class IterativeDeepeningDepthFirstSearch<N> {
 private final N target;
 private final List<N> path;
 private final NodeExpander<N> expander;
 private boolean found = false;
 
 public IterativeDeepeningDepthFirstSearch() {
 this.target = null;
 this.path = null;
 this.expander = null;
 }
 
 private IterativeDeepeningDepthFirstSearch(N target, 
 NodeExpander<N> expander) {
 this.target = Objects.requireNonNull(target, "target is null");
 this.path = new ArrayList<>();
 this.expander = expander;
 }
 
 public List<N> search(N source, N target, NodeExpander<N> expander) {
 IterativeDeepeningDepthFirstSearch state = 
 new IterativeDeepeningDepthFirstSearch(target, expander);
 
 for (int depth = 0;; ++depth) {
 state.depthLimitedSearch(source, depth);
 
 if (state.found) {
 Collections.<SlidingTilePuzzleNode>reverse(state.path);
 return state.path;
 }
 }
 }
 
 private void depthLimitedSearch(N node, int depth) {
 if (depth == 0 && node.equals(target)) {
 found = true;
 path.add(node);
 return;
 }
 
 if (depth > 0) {
 for (N child : expander.expand(node)) {
 depthLimitedSearch(child, depth - 1);
 
 if (found) {
 path.add(node);
 return;
 }
 }
 }
 }
}

Outro

BidirectionalIterativeDeepeningDepthFirstSearch performs best on most benchmark batteries.

Critique request

As always, I am eager to hear any constructive commentary on my work.

• Adversing: buildPath() method creates a new instance with null fields and calls search() on it, which will cause infinite recursion or null pointer exceptions. I suggest you to fix that.