Implementation of the bidirectional graph search

Question

I am trying to implement a bi-directional graph search. As I understand, I should somehow merge two breadth-first searches, one which starts at the starting (or root) node and one which starts at the goal (or end) node. The bi-directional search terminates when both breadth-first searches "meet" at the same vertex.

Could you provide me with a code example (in Java, if possible) or link with code for the bidirectional graph search?

Answer 1

Assuming you have Nodes like this (in the file Node.java):

import java.util.HashSet;
import java.util.Set;

public class Node<T> {
    private final T data; // The data that you want to store in this node.
    private final Set<Node> adjacentNodes = new HashSet<>();

    // Constructor
    public Node(T data) {
        this.data = data;
    }

    // Getters

    /*
     * Returns the data stored in this node.
     * */
    public T getData() {
        return data;
    }

    /*
     * Returns a set of the adjacent nodes of this node.
     * */
    public Set<Node> getAdjacentNodes() {
        return adjacentNodes;
    }

    // Setters

    /*
     * Attempts to add node to the set of adjacent nodes of this node. If it was not previously added, it is added, and
     * true is returned. If it was previously added, it returns false.
     * */
    public boolean addAdjacent(Node node) {
        return adjacentNodes.add(node);
    }
}

Then the bidirectional search algorithm (defined in the file BidirectionalSearch.java) would look something like this:

import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
import java.util.LinkedList;


public class BidirectionalSearch {

    /*
     * Returns true if a path exists between Node a and b, false otherwise.
     * */
    public static boolean pathExists(Node a, Node b) {
        // LinkedList implements the Queue interface, FIFO queue operations (e.g., add and poll).

        // Queue to hold the paths from Node a.
        Queue<Node> queueA = new LinkedList<>();

        // Queue to hold the paths from Node a.
        Queue<Node> queueB = new LinkedList<>();

        // A set of visited nodes starting from Node a.
        Set<Node> visitedA = new HashSet<>();

        // A set of visited nodes starting from Node b.
        Set<Node> visitedB = new HashSet<>();

        visitedA.add(a);
        visitedB.add(b);

        queueA.add(a);
        queueB.add(b);

        // Both queues need to be empty to exit the while loop.
        while (!queueA.isEmpty() || !queueB.isEmpty()) {
            if (pathExistsHelper(queueA, visitedA, visitedB)) {
                return true;
            }
            if (pathExistsHelper(queueB, visitedB, visitedA)) {
                return true;
            }
        }

        return false;
    }

    private static boolean pathExistsHelper(Queue<Node> queue,
                                            Set<Node> visitedFromThisSide,
                                            Set<Node> visitedFromThatSide) {
        if (!queue.isEmpty()) {
            Node next = queue.remove();

            Set<Node> adjacentNodes = next.getAdjacentNodes();

            for (Node adjacent : adjacentNodes) {

                // If the visited nodes, starting from the other direction,
                // contain the "adjacent" node of "next", then we can terminate the search
                if (visitedFromThatSide.contains(adjacent)) {
                    return true;
                } else if (visitedFromThisSide.add(adjacent)) {
                    queue.add(adjacent);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Test here the implementation above.
    }
}