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 .