current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite
3

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

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 are..

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;
    }
}

The 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);
        }
    }
}

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

share|improve this question

1 Answer 1

up vote 5 down vote accepted

  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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.