Fixed BIDDFS (bidirectional iterative deepening depth first search) in Java

Question

Intro

I have this GitHub repository for doing pathfinding in directed unweighted graphs. This post is about BIDDFS proposed by Richard Korf in his paper.

---

Code

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 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.backwardSearchStack = null;
 this.frontier = null;
 this.visitedForward = null;
 this.visitedBackward = null;
 this.forwardExpander = null;
 this.backwardExpander = null;
 }
 private BidirectionalIterativeDeepeningDepthFirstSearch(
 NodeExpander<N> forwardExpander,
 NodeExpander<N> backwardExpander) {
 
 this.backwardSearchStack = new ArrayDeque<>();
 this.frontier = new HashSet<>();
 this.visitedForward = new HashSet<>();
 this.visitedBackward = new HashSet<>();
 this.forwardExpander = forwardExpander;
 this.backwardExpander = backwardExpander;
 }
 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<>(
 forwardExpander,
 backwardExpander);
 // The actual search routine:
 for (int forwardDepth = 0;; ++forwardDepth) {
 state.frontier.clear();
 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) {
 // No improvement since the last run of forward search. Return
 // 'null' indicating that there is no path from source to 
 // target:
 return null;
 }
 
 state.previousVisitedSizeForward = state.visitedForward.size();
 state.visitedBackward.clear();
 
 N meetingNode = 
 state.depthLimitedSearchBackward(
 target,
 forwardDepth,
 state.visitedBackward);
 
 if (meetingNode != null) {
 return state.buildPath(source, 
 meetingNode);
 }
 
 state.visitedBackward.clear();
 
 meetingNode = 
 state.depthLimitedSearchBackward(
 target, 
 forwardDepth + 1, 
 state.visitedBackward);
 
 if (meetingNode != null) {
 return state.buildPath(source,
 meetingNode);
 }
 
 if (state.visitedBackward.size() == 
 state.previousVisitedSizeBackward) {
 return null;
 }
 
 state.previousVisitedSizeBackward = 
 state.visitedBackward.size();
 }
 }
 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,
 Set<N> visited) {
 if (visited.contains(node)) {
 return null;
 }
 
 backwardSearchStack.addFirst(node);
 if (depth == 0) {
 if (frontier.contains(node)) {
 return node;
 }
 backwardSearchStack.removeFirst();
 return null;
 }
 
 visited.add(node); 
 for (N parent : backwardExpander.expand(node)) {
 N meetingNode = depthLimitedSearchBackward(parent,
 depth - 1, 
 visited);
 if (meetingNode != null) {
 return meetingNode;
 } 
 }
 backwardSearchStack.removeFirst();
 return null;
 }
 private List<N> buildPath(N source, 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;
 }
}

---

Typical output

I usually see something like this:

<<< runGridBenchmark() >>>
IterativeDeepeningAStar in 2 milliseconds. Path length: 20
BIDDFS in 11 milliseconds. Path length: 20
Seed = 1750572292356
Source node: io.github.coderodde.libid.demo.RubiksCubeNode@489f1f6a
Target node: io.github.coderodde.libid.demo.RubiksCubeNode@f1e35bea
BIDDFS path (24 ms):
 io.github.coderodde.libid.demo.RubiksCubeNode@489f1f6a
 io.github.coderodde.libid.demo.RubiksCubeNode@3d6106ea
 io.github.coderodde.libid.demo.RubiksCubeNode@3d3b8e6a
 io.github.coderodde.libid.demo.RubiksCubeNode@f5864bea
 io.github.coderodde.libid.demo.RubiksCubeNode@f569346a
 io.github.coderodde.libid.demo.RubiksCubeNode@f1e35bea
IDDFS path (856 ms):
 io.github.coderodde.libid.demo.RubiksCubeNode@489f1f6a
 io.github.coderodde.libid.demo.RubiksCubeNode@3d6106ea
 io.github.coderodde.libid.demo.RubiksCubeNode@3d3b8e6a
 io.github.coderodde.libid.demo.RubiksCubeNode@f5864bea
 io.github.coderodde.libid.demo.RubiksCubeNode@f569346a
 io.github.coderodde.libid.demo.RubiksCubeNode@f1e35bea
Bidirectional BFS path (45 ms):
 io.github.coderodde.libid.demo.RubiksCubeNode@489f1f6a
 io.github.coderodde.libid.demo.RubiksCubeNode@3d6106ea
 io.github.coderodde.libid.demo.RubiksCubeNode@3d3b8e6a
 io.github.coderodde.libid.demo.RubiksCubeNode@f5864bea
 io.github.coderodde.libid.demo.RubiksCubeNode@f569346a
 io.github.coderodde.libid.demo.RubiksCubeNode@f1e35bea
Algorithms returns correct paths: true
<<< runGeneralGraphBenchmark() >>>
Nodes are ready.
Actual edge count: 13999938
Seed = 1751615254340
BidirectionalIterativeDeepeningDepthFirstSearch in 6 millseconds. . Path length: 7
IterativeDeepeningDepthFirstSearch in 727 millseconds. Path length: 7
io.github.coderodde.libid.impl.BreadthFirstSearch in 5132 millseconds. Path length: 7
BidirectionalBreadthFirstSearch in 22 millseconds. Path length: 7
Algorithms agree: true
-----
.
.
.
<<< run15PuzzleGraphBenchmark() >>>
Seed = 1751615314783
BreadthFirstSearch in 1996 milliseconds. Path length: 19
BidirectionalIterativeDeepeningDepthFirstSearch in 3 milliseconds. Path length: 19
IterativeDeepeningAStar in 2 milliseconds. Path length: 19
BidirectionalBreadthFirstSearch in 8 milliseconds. Path length: 19
Algorithms agree: true

---

Critique request

What do you think? Is my implementation correct?