Krdytkyu

Introduction

I have this iterative deepening search algorithm. The main "research" attempt was to find out a bidirectional version of that search, and it turned out to be superior compared to two other ID algorithms. The code I would like to get reviewed is as follows:

package net.coderodde.libid.support;



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 net.coderodde.libid.NodeExpander;



public final class BidirectionalIterativeDeepeningDepthFirstSearch<N> {



    private final N source;

    private final Deque<N> backwardSearchStack;

    private final Set<N> frontier;

    private final NodeExpander<N> forwardExpander;

    private final NodeExpander<N> backwardExpander;



    public BidirectionalIterativeDeepeningDepthFirstSearch() {

        this.source              = null;

        this.backwardSearchStack = null;

        this.frontier            = 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.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<>(

                        source,

                        forwardExpander,

                        backwardExpander);



        for (int depth = 0;; ++depth) {

            // Do a depth limited search in forward direction. Put all nodes at 

            // depth == 0 to the frontier.

            state.depthLimitedSearchForward(source, depth);



            // Perform a reversed search starting from the target node and 

            // recurring to the depth 'depth'.

            N meetingNode = state.depthLimitedSearchBackward(target, depth);



            if (meetingNode != null) {

                return state.buildPath(meetingNode);

            }



            state.backwardSearchStack.clear();



            // Perform a reversed search once again with depth = 'depth + 1'.

            // We need this in case the shortest path has odd number of arcs.

            meetingNode = state.depthLimitedSearchBackward(target, depth + 1);



            if (meetingNode != null) {

                return state.buildPath(meetingNode);

            }



            state.backwardSearchStack.clear();

            // Wipe out the frontier.

            state.frontier.clear();

        }

    }



    private void depthLimitedSearchForward(N node, int depth) {

        if (depth == 0) {

            frontier.add(node);

            return;

        }



        for (N child : forwardExpander.expand(node)) {

            depthLimitedSearchForward(child, depth - 1);

        }

    }



    private N depthLimitedSearchBackward(N node, int depth) {

        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;

    }

}

Performance figures
You can see something like this:

*** 8-puzzle graph benchmark ***

Seed = 1542379748450

BreadthFirstSearch in 7 milliseconds. Path length: 14

IterativeDeepeningDepthFirstSearch in 162 milliseconds. Path length: 14

BidirectionalIterativeDeepeningDepthFirstSearch in 1 milliseconds. Path length: 14

IterativeDeepeningAStar in 1 milliseconds. Path length: 14

Algorithms agree: true



*** General graph benchmark ***

Seed = 1542379748655

Warming up...

Warming up done!

BidirectionalIterativeDeepeningDepthFirstSearch in 0 milliseconds. Path length: 4

IterativeDeepeningDepthFirstSearch in 26 milliseconds. Path length: 4

BreadthFirstSearch in 4484 milliseconds. Path length: 4

The entire project lives here.