lojix/search/src/main/com/thesett/aima/search/impl/bidirectional/BaseBiDirectionalQueueSearch.java
public SearchNode<O, T> findGoalPath() throws SearchNotExhaustiveException
    {
        // Keep running until the queue becomes empty or a goal state is found
        while (!forwardQueue.isEmpty() || !reverseQueue.isEmpty())
        {
            // Only run the forward step of the search if the forward queue is not empty
            if (!forwardQueue.isEmpty())
            {
                // Extract the next node from the forward queue
                SearchNode<O, T> currentForwardNode = forwardQueue.remove();

                // Remove this node from the forward fringe map as it will soon be replaced by more fringe members
                forwardFringe.remove(currentForwardNode.getState());

                // Check the reverse fringe against the next forward node for a match.
                if (reverseFringe.containsKey(currentForwardNode.getState()))
                {
                    // A path from start to the goal has been found. Walk backwards along the reverse path adding all
                    // nodes encountered to the forward path until the goal is reached.
                    return joinBothPaths(currentForwardNode, reverseFringe.get(currentForwardNode.getState()));
                }

                // There was no match so a path to the goal has not been found
                else
                {
                    // Get all of the successor states to the current node
                    Queue<SearchNode<O, T>> newStates = new LinkedList<SearchNode<O, T>>();

                    currentForwardNode.expandSuccessors(newStates, false);

                    // Expand all the successors to the current forward node into the buffer to be searched.
                    forwardQueue.addAll(newStates);

                    // Also add all the successors to the current forward fringe map.
                    for (SearchNode<O, T> nextSearchNode : newStates)
                    {
                        forwardFringe.put(nextSearchNode.getState(), nextSearchNode);
                    }
                }
            }

            // Only run the reverse step of the search if the reverse queue is not empty
            if (!reverseQueue.isEmpty())
            {
                // Extract the next node from the reverse queue
                SearchNode<O, T> currentReverseNode = reverseQueue.remove();

                // Remove this node from the reverse fringe set as it will soon be replaced by more fringe members
                reverseFringe.remove(currentReverseNode.getState());

                // Check the forward fringe against the next reverse node for a match.
                if (forwardFringe.containsKey(currentReverseNode.getState()))
                {
                    // A path from start to goal has been found.
                    // Walk backwards along the reverse path adding all nodes encountered to the foward path until the
                    // goal is reached.
                    return joinBothPaths(forwardFringe.get(currentReverseNode.getState()), currentReverseNode);
                }

                // There was no match so a path to the goal has not been found
                else
                {
                    // Get all of the successor states to the current node (really predecessor state)
                    Queue<SearchNode<O, T>> newStates = new LinkedList<SearchNode<O, T>>();

                    currentReverseNode.expandSuccessors(newStates, false);

                    // Expand all the successors to the current reverse node into the reverse buffer to be searched.
                    reverseQueue.addAll(newStates);

                    // Add all the successors to the current reverse fringe set
                    for (SearchNode<O, T> nextSearchNode : newStates)
                    {
                        reverseFringe.put(nextSearchNode.getState(), nextSearchNode);
                    }
                }
            }
        }

        // No goal state was found so return null
        return null;
    }
public SearchNode<O, T> findGoalPath() throws SearchNotExhaustiveException
    {
        // Keep running until the queue becomes empty or a goal state is found
        while (!forwardQueue.isEmpty() || !reverseQueue.isEmpty())
        {
            // Only run the forward step of the search if the forward queue is not empty
            if (!forwardQueue.isEmpty())
            {
                // Extract the next node from the forward queue
                SearchNode<O, T> currentForwardNode = forwardQueue.remove();

                // Remove this node from the forward fringe map as it will soon be replaced by more fringe members
                forwardFringe.remove(currentForwardNode.getState());

                // Check the reverse fringe against the next forward node for a match.
                if (reverseFringe.containsKey(currentForwardNode.getState()))
                {
                    // A path from start to the goal has been found. Walk backwards along the reverse path adding all
                    // nodes encountered to the forward path until the goal is reached.
                    return joinBothPaths(currentForwardNode, reverseFringe.get(currentForwardNode.getState()));
                }

                // There was no match so a path to the goal has not been found
                else
                {
                    // Get all of the successor states to the current node
                    Queue<SearchNode<O, T>> newStates = new LinkedList<SearchNode<O, T>>();

                    currentForwardNode.expandSuccessors(newStates, false);

                    // Expand all the successors to the current forward node into the buffer to be searched.
                    forwardQueue.addAll(newStates);

                    // Also add all the successors to the current forward fringe map.
                    for (SearchNode<O, T> nextSearchNode : newStates)
                    {
                        forwardFringe.put(nextSearchNode.getState(), nextSearchNode);
                    }
                }
            }

            // Only run the reverse step of the search if the reverse queue is not empty
            if (!reverseQueue.isEmpty())
            {
                // Extract the next node from the reverse queue
                SearchNode<O, T> currentReverseNode = reverseQueue.remove();

                // Remove this node from the reverse fringe set as it will soon be replaced by more fringe members
                reverseFringe.remove(currentReverseNode.getState());

                // Check the forward fringe against the next reverse node for a match.
                if (forwardFringe.containsKey(currentReverseNode.getState()))
                {
                    // A path from start to goal has been found.
                    // Walk backwards along the reverse path adding all nodes encountered to the foward path until the
                    // goal is reached.
                    return joinBothPaths(forwardFringe.get(currentReverseNode.getState()), currentReverseNode);
                }

                // There was no match so a path to the goal has not been found
                else
                {
                    // Get all of the successor states to the current node (really predecessor state)
                    Queue<SearchNode<O, T>> newStates = new LinkedList<SearchNode<O, T>>();

                    currentReverseNode.expandSuccessors(newStates, false);

                    // Expand all the successors to the current reverse node into the reverse buffer to be searched.
                    reverseQueue.addAll(newStates);

                    // Add all the successors to the current reverse fringe set
                    for (SearchNode<O, T> nextSearchNode : newStates)
                    {
                        reverseFringe.put(nextSearchNode.getState(), nextSearchNode);
                    }
                }
            }
        }

        // No goal state was found so return null
        return null;
    }
public SearchNode < O , T > findGoalPath ( ) throws SearchNotExhaustiveException { // Keep running until the queue becomes empty or a goal state is found while ( ! forwardQueue . isEmpty ( ) || ! reverseQueue . isEmpty ( ) ) { // Only run the forward step of the search if the forward queue is not empty if ( ! forwardQueue . isEmpty ( ) ) { // Extract the next node from the forward queue SearchNode < O , T > currentForwardNode = forwardQueue . remove ( ) ; // Remove this node from the forward fringe map as it will soon be replaced by more fringe members forwardFringe . remove ( currentForwardNode . getState ( ) ) ; // Check the reverse fringe against the next forward node for a match. if ( reverseFringe . containsKey ( currentForwardNode . getState ( ) ) ) { // A path from start to the goal has been found. Walk backwards along the reverse path adding all // nodes encountered to the forward path until the goal is reached. return joinBothPaths ( currentForwardNode , reverseFringe . get ( currentForwardNode . getState ( ) ) ) ; } // There was no match so a path to the goal has not been found else { // Get all of the successor states to the current node Queue < SearchNode < O , T > > newStates = new LinkedList < SearchNode < O , T > > ( ) ; currentForwardNode . expandSuccessors ( newStates , false ) ; // Expand all the successors to the current forward node into the buffer to be searched. forwardQueue . addAll ( newStates ) ; // Also add all the successors to the current forward fringe map. for ( SearchNode < O , T > nextSearchNode : newStates ) { forwardFringe . put ( nextSearchNode . getState ( ) , nextSearchNode ) ; } } } // Only run the reverse step of the search if the reverse queue is not empty if ( ! reverseQueue . isEmpty ( ) ) { // Extract the next node from the reverse queue SearchNode < O , T > currentReverseNode = reverseQueue . remove ( ) ; // Remove this node from the reverse fringe set as it will soon be replaced by more fringe members reverseFringe . remove ( currentReverseNode . getState ( ) ) ; // Check the forward fringe against the next reverse node for a match. if ( forwardFringe . containsKey ( currentReverseNode . getState ( ) ) ) { // A path from start to goal has been found. // Walk backwards along the reverse path adding all nodes encountered to the foward path until the // goal is reached. return joinBothPaths ( forwardFringe . get ( currentReverseNode . getState ( ) ) , currentReverseNode ) ; } // There was no match so a path to the goal has not been found else { // Get all of the successor states to the current node (really predecessor state) Queue < SearchNode < O , T > > newStates = new LinkedList < SearchNode < O , T > > ( ) ; currentReverseNode . expandSuccessors ( newStates , false ) ; // Expand all the successors to the current reverse node into the reverse buffer to be searched. reverseQueue . addAll ( newStates ) ; // Add all the successors to the current reverse fringe set for ( SearchNode < O , T > nextSearchNode : newStates ) { reverseFringe . put ( nextSearchNode . getState ( ) , nextSearchNode ) ; } } } } // No goal state was found so return null return null ; }
Implementation of the general bi-dircetional search. The search alternated between taking a forward and a reverse
step.

@return The first {@link SearchNode} corresponding to a goal state that is found or null if none can be found
after exhaustive searching.

@throws SearchNotExhaustiveException If the search stops before finding a solution or exhausting the search
space. Different search algorithms may fail for different reasons but in
particular it it is worth noting that if the maximum number of steps is
reached without exhausting the search space this will cause an exception to
be thrown rather than for this method to return null.
Implementation of the general bi - dircetional search . The search alternated between taking a forward and a reverse step .