Shortest path using Breadth First Search

Question

I have sample graphs like the following (un-directed un-weighted cyclic graphs). My goal is to find the shortest path between a given source and destination.

I have found this implementation on web and have made some modifications only. How can the code be improved? Are there any gotchas that I need to take care of?

film--->[language, film_actor, film_category, inventory]
film_actor--->[actor, film]
store--->[customer, inventory, staff, address]
payment--->[customer, rental, staff]
actor--->[film_actor]
rental--->[payment, customer, inventory, staff]
customer--->[address, store, payment, rental]
city--->[address, country]
country--->[city]
staff--->[payment, rental, address, store]
category--->[film_category]
address--->[city, customer, staff, store]
inventory--->[film, store, rental]
film_category--->[category, film]
language--->[film]

Graph and BreadthFirstSearch classes:

Graph.java

package com.bfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Graph {

    /**
     * Stores a list of nodes in this Graph.
     */
    private ArrayList<String> nodes = new ArrayList<String>();

    /**
     * Creates a mapping from a node to its neighbours.
     */
    private Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();

    /**
     * Constructs a graph.
     */
    public Graph() {
    }

    /**
     * Adds an edge between two nodes.
     *
     * @param source      the source node.
     * @param destination the destination node, to be connected from source. Requires:
     *                    source != null, destination != null.
     */
    public void addEdge(String source, String destination) {
        // Adds a new path.
        if (!map.containsKey(source)) {
            /*
            Stores a list of neighbours for a node.
            */
            ArrayList<String> neighbours = new ArrayList<String>();
            neighbours.add(destination);
            map.put(source, neighbours);
        } else {
            // Updates a path.
            ArrayList<String> oldList = map.get(source);

            int index = 0;
            while ((index != oldList.size()) && (!oldList.get(index).equals(destination))) {
                index++;
            }
            // If the destination is not already in the path, then
            // add it to the path.
            if (index == oldList.size()) {
                oldList.add(destination);
                map.put(source, oldList);
            }
        }
        storeNodes(source, destination);
    }

    /**
     * Stores the nodes in this Graph.
     */
    private void storeNodes(String source, String destination) {
        if (!source.equals(destination)) {
            if (!nodes.contains(destination)) {
                nodes.add(destination);
            }
        }
        if (!nodes.contains(source)) {
            nodes.add(source);
        }
    }

    /**
     * Returns the neighboursList for this node.
     *
     * @param node the node where its neighbours will be searched for. Requires:
     *             node must be present in this Graph and not null.
     * @return the neighboursList for this node.
     */
    public ArrayList<String> getNeighbours(String node) {
        ArrayList<String> neighboursList;
        Set<String> keys = map.keySet();
        for (String key : keys) {
            if (key.equals(node)) {
                neighboursList = map.get(key);
                return new ArrayList<String>(neighboursList);
            }
        }
        return new ArrayList<String>();
    }

    /**
     * Checks if the node is in this Graph.
     *
     * @return true if the node is in this Graph.
     */
    public boolean memberOf(String node) {
        return nodes.contains(node);
    }

    /**
     * Returns a string representation of this Graph, in
     * the form: node => [node 1, node 2, ... , node n], which means
     * that there is a path from node to node 1, node 2, ... , node n.
     *
     * @return a string representation of this Graph.
     */
    public String toString() {
        int counter = 0;
        String string = "";
        Set<String> keys = map.keySet();
        for (String key : keys) {
            if (counter == 0) {
                string = string + key + "--->" + map.get(key).toString();
            } else {
                string = string + "\n" + key + "--->" + map.get(key).toString();
            }
            counter++;
        }
        return string;
    }
}

BFS code:

package com.bfs;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class BreadthFirstSearch {

    /**
     * The shortest path between two nodes in a graph.
     */
    private static ArrayList<String> shortestPath = new ArrayList<String>();

    /**
     * Finds the shortest path between two nodes (source and destination) in a graph.
     *
     * @param graph       The graph to be searched for the shortest path.
     * @param source      The source node of the graph specified by user.
     * @param destination The destination node of the graph specified by user.
     *
     * @return the shortest path stored as a list of nodes.
     * or null if a path is not found.
     * Requires: source != null, destination != null and must have a name (e.g.
     * cannot be an empty string).
     */
    public static ArrayList<String> breadthFirstSearch(Graph graph, String source,
                                                       String destination) {
        shortestPath.clear();

        // A list that stores the path.
        ArrayList<String> path = new ArrayList<String>();

        // If the source is the same as destination, I'm done.
        if (source.equals(destination) && graph.memberOf(source)) {
            path.add(source);
            return path;
        }

        // A queue to store the visited nodes.
        ArrayDeque<String> queue = new ArrayDeque<String>();

        // A queue to store the visited nodes.
        ArrayDeque<String> visited = new ArrayDeque<String>();

        queue.offer(source);
        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            visited.offer(vertex);

            ArrayList<String> neighboursList = graph.getNeighbours(vertex);
            int index = 0;
            int neighboursSize = neighboursList.size();
            while (index != neighboursSize) {
                String neighbour = neighboursList.get(index);

                path.add(neighbour);
                path.add(vertex);

                if (neighbour.equals(destination)) {
                    return processPath(source, destination, path);
                } else {
                    if (!visited.contains(neighbour)) {
                        queue.offer(neighbour);
                    }
                }
                index++;
            }
        }
        return null;
    }

    /**
     * Adds the nodes involved in the shortest path.
     *
     * @param src         The source node.
     * @param destination The destination node.
     * @param path        The path that has nodes and their neighbours.
     * @return The shortest path.
     */
    private static ArrayList<String> processPath(String src, String destination,
                                                 ArrayList<String> path) {

        // Finds out where the destination node directly comes from.
        int index = path.indexOf(destination);
        String source = path.get(index + 1);

        // Adds the destination node to the shortestPath.
        shortestPath.add(0, destination);

        if (source.equals(src)) {
            // The original source node is found.
            shortestPath.add(0, src);
            return shortestPath;
        } else {
            // We find where the source node of the destination node
            // comes from.
            // We then set the source node to be the destination node.
            return processPath(src, source, path);
        }
    }
}

Answer 1

1. There are several places in this code where a loop is redundant(or at least can be simplified). For instance, this for loop:

   int index = 0;
   while ((index != oldList.size()) && (!oldList.get(index).equals(destination))) {
       index++;
   }
   

   can be substituted with a call to the contains method(the index of the element is not used, anyway. It just checks that whether an element is in the list).

   This method is also way too long and complicated:

   public ArrayList<String> getNeighbours(String node) {
       ArrayList<String> neighboursList;
       Set<String> keys = map.keySet();
       for (String key : keys) {
           if (key.equals(node)) {
               neighboursList = map.get(key);
               return new ArrayList<String>(neighboursList);
           }
       }
       return new ArrayList<String>();
   }
   

   Taking into account that it requires that an element is present in the graph, we could simply write it as new ArrayList<String>(map.get(node)).

   And here:

   while (index != neighboursSize) {
       String neighbour = neighboursList.get(index);
   
       path.add(neighbour);
       path.add(vertex);
   
       if (neighbour.equals(destination)) {
           return processPath(source, destination, path);
       } else {
           if (!visited.contains(neighbour)) {
               queue.offer(neighbour);
            }
       }
       index++;
   }
   

   Using a while loop to simply iterate over all elements of a collection looks strange. I'd rather use for each loop:

   for (String neighbour : neighboursList) {
       // Do the same stuff.
   }
   

   In general, avoid using loops when there is a standard method for doing what you need.

2. If you are using Java 8, you can simplify the code even more by using the getOrDefault method of the Map to avoid things like:

   if (map.containsKey(someKey)) {
       something = map.get(someKey);
   } else {
       something = defaultValue;
   }
   

   You can also use diamond operator if you have Java 7 or later:

   ArrayList<String> list = new ArrayList<>();
   

   to make your code more concise.

3. Prefer interfaces to concrete implementations. That is, use List instead of ArrayList unless you need some specific features of the latter.

4. Passing strings around as node identifiers make the code less understandable. I'd recommend creating a separate Node class.

Answer 2

I believe eb80's code will NOT work to create the correct path. Take phoenix's example above. Consider the case when the source node is film_actorand the destination node is actor.

else {
    for (Node nextNode : currentNode.getSiblingNodes()) {
      if (!visitedNodes.contains(nextNode)) {
        queue.add(nextNode);
        visitedNodes.add(nextNode);

        // Look up of next node instead of previous.
        nextNodeMap.put(currentNode, nextNode);
        previousNode = currentNode;
      }
    }

will select the siblings of film_actor as actor and film. Both will be added to the queue. However, after this block, the nextNodeMap will have key film_actor mapped to film as it is the last sibling. The code will then see the first item in the queue as "actor", which IS the destination code, and break.

The resulting "reconstruct path" code will find film when it hashes for film_actor, the root node, and NOT create the correct path.

Answer 3

The following code fixes the above corner cases and will work straight out:

/**
 *
 *        1             -> 5
 * 0 ->           -> 4
 *        2 -> 3        -> 6    -> 7
 *
 */

In the answer from @phoenix, in addition to the code not working straight out of the box (not a big deal), the case where the end destination is reached through a node with multiple siblings does not work.

As I note in my comments:

Handle case where the node leading to the destination node itself pointed to multiple nodes. In this case, nextNodeMap is incorrect and we need to rely on the previously seen node.

import java.util.*;

public class Node {
  private final int value;
  private final Set<Node> siblingNodes;

  public Node(int value) {
    this.value = value;
    siblingNodes = new HashSet<Node>();
  }

  public Set<Node> getSiblingNodes() {
    return siblingNodes;
  }

  public boolean equals(Node compareTo) {
    return (compareTo.getValue() == value);
  }

  public int getValue() {
    return value;
  }

  public void addSiblingNode(Node node) {
    siblingNodes.add(node); 
  }
}

public class BfsShortestPath {  

  public static void main(String[] args) {
/**
 *
 *        1             -> 5
 * 0 ->           -> 4
 *        2 -> 3        -> 6    -> 7
 *
 */
    Node node0 = new Node(0);

    Node node1 = new Node(1);
    Node node2 = new Node(2);
    node0.addSiblingNode(node1);
    node0.addSiblingNode(node2);    

    Node node3 = new Node(3);
   node2.addSiblingNode(node3);

    Node node4 = new Node(4);
    node3.addSiblingNode(node4);

    Node node5 = new Node(5);
    Node node6 = new Node(6);
    node4.addSiblingNode(node5);
    node4.addSiblingNode(node6);

    List<Node> shortestPath = getDirections(node0, node6);
    for(Node node : shortestPath) {
      System.out.println(node.getValue());
    }
  }

  public static List<Node> getDirections(Node sourceNode, Node destinationNode) {
    // Initialization.
    Map<Node, Node> nextNodeMap = new HashMap<Node, Node>();
    Node currentNode = sourceNode;
    Node previousNode = sourceNode;

    // Queue
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(currentNode);

/*
 * The set of visited nodes doesn't have to be a Map, and, since order
 * is not important, an ordered collection is not needed. HashSet is 
 * fast for add and lookup, if configured properly.
 */
    Set<Node> visitedNodes = new HashSet<Node>();
    visitedNodes.add(currentNode);

    //Search.
    while (!queue.isEmpty()) {
      currentNode = queue.remove();
      if (currentNode.equals(destinationNode)) {
        // Handle case where the node leading to the destinatino node
        // itself pointed to multiple nodes. In this case,
        // nextNodeMap is incorrect and we need to rely on the previously
        // seen node.
        // Also need to check for edge-case of start node == end node.
        if (!previousNode.equals(currentNode)) {
          nextNodeMap.put(previousNode, currentNode);
        }
        break;
      } else {
        for (Node nextNode : currentNode.getSiblingNodes()) {
          if (!visitedNodes.contains(nextNode)) {
            queue.add(nextNode);
            visitedNodes.add(nextNode);

            // Look up of next node instead of previous.
            nextNodeMap.put(currentNode, nextNode);
            previousNode = currentNode;
          }
        }
      }
    }

    // If all nodes are explored and the destination node hasn't been found.
    if (!currentNode.equals(destinationNode)) {
        throw new RuntimeException("No feasible path.");
    }

    // Reconstruct path. No need to reverse.
    List<Node> directions = new LinkedList<Node>();
    for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) {
        directions.add(node);
    }

    return directions;
  }
}