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.

Given a directed connected graphs, find all paths from source to destination.

Looking for code review, optimizations and best practices. Also need help figuring out complexity, which in my best attempt is O(E!), where E is the number of edges.

class GraphFindAllPaths<T> implements Iterable<T> {

    /* A map from nodes in the graph to sets of outgoing edges.  Each
     * set of edges is represented by a map from edges to doubles.
     */
    private final Map<T, Map<T, Double>> graph = new HashMap<T, Map<T, Double>>();

    /**
     *  Adds a new node to the graph. If the node already exists then its a
     *  no-op.
     * 
     * @param node  Adds to a graph. If node is null then this is a no-op.
     * @return      true if node is added, false otherwise.
     */
    public boolean addNode(T node) {
        if (node == null) {
            throw new NullPointerException("The input node cannot be null.");
        }
        if (graph.containsKey(node)) return false;

        graph.put(node, new HashMap<T, Double>());
        return true;
    }

    /**
     * Given the source and destination node it would add an arc from source 
     * to destination node. If an arc already exists then the value would be 
     * updated the new value.
     *  
     * @param source                    the source node.
     * @param destination               the destination node.
     * @param length                    if length if 
     * @throws NullPointerException     if source or destination is null.
     * @throws NoSuchElementException   if either source of destination does not exists. 
     */
    public void addEdge (T source, T destination, double length) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        /* A node would always be added so no point returning true or false */
        graph.get(source).put(destination, length);
    }

    /**
     * Removes an edge from the graph.
     * 
     * @param source        If the source node.
     * @param destination   If the destination node.
     * @throws NullPointerException     if either source or destination specified is null
     * @throws NoSuchElementException   if graph does not contain either source or destination
     */
    public void removeEdge (T source, T destination) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        graph.get(source).remove(destination);
    }

    /**
     * Given a node, returns the edges going outward that node,
     * as an immutable map.
     * 
     * @param node The node whose edges should be queried.
     * @return An immutable view of the edges leaving that node.
     * @throws NullPointerException   If input node is null.
     * @throws NoSuchElementException If node is not in graph.
     */
    public Map<T, Double> edgesFrom(T node) {
        if (node == null) {
            throw new NullPointerException("The node should not be null.");
        }
        Map<T, Double> edges = graph.get(node);
        if (edges == null) {
            throw new NoSuchElementException("Source node does not exist.");
        }
        return Collections.unmodifiableMap(edges);
    }

    /**
     * Returns the iterator that travels the nodes of a graph.
     * 
     * @return an iterator that travels the nodes of a graph.
     */
    @Override public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }
}

/**
 * Given a connected directed graph, find all paths between any two input points.
 */
public class FindAllPaths<T> {

    private final GraphFindAllPaths<T> graph;

    /**
     * Takes in a graph. This graph should not be changed by the client
     */
    public FindAllPaths(GraphFindAllPaths<T> graph) {
        if (graph == null) {
            throw new NullPointerException("The input graph cannot be null.");
        }
        this.graph = graph;
    }

    private void validate (T source, T destination) {

        if (source == null) {
            throw new NullPointerException("The source: " + source + " cannot be  null.");
        }
        if (destination == null) {
            throw new NullPointerException("The destination: " + destination + " cannot be  null.");
        }
        if (source.equals(destination)) {
            throw new IllegalArgumentException("The source and destination: " + source + " cannot be the same.");
        }
    }

    /**
     * Returns the list of paths, where path itself is a list of nodes.
     * 
     * @param source            the source node
     * @param destination       the destination node
     * @return                  List of all paths
     */
    public List<List<T>> getAllPaths(T source, T destination) {
        validate(source, destination);

        List<List<T>> paths = new ArrayList<List<T>>();
        recursive(source, destination, paths, new LinkedHashSet<T>());
        return paths;
    }

    // so far this dude ignore's cycles.
    private void recursive (T current, T destination, List<List<T>> paths, LinkedHashSet<T> path) {
        path.add(current);

        if (current == destination) {
            paths.add(new ArrayList<T>(path));
            path.remove(current);
            return;
        }

        final Set<T> edges  = graph.edgesFrom(current).keySet();

        for (T t : edges) {
            if (!path.contains(t)) {
                recursive (t, destination, paths, path);
            }
        }

        path.remove(current);
    }    

    public static void main(String[] args) {
        GraphFindAllPaths<String> graphFindAllPaths = new GraphFindAllPaths<String>();
        graphFindAllPaths.addNode("A");
        graphFindAllPaths.addNode("B");
        graphFindAllPaths.addNode("C");
        graphFindAllPaths.addNode("D");

        graphFindAllPaths.addEdge("A", "B", 10);
        graphFindAllPaths.addEdge("A", "C", 10);
        graphFindAllPaths.addEdge("B", "D", 10);
        graphFindAllPaths.addEdge("C", "D", 10);

        graphFindAllPaths.addEdge("B", "C", 10);
        graphFindAllPaths.addEdge("C", "B", 10);

        FindAllPaths<String> findAllPaths = new FindAllPaths<String>(graphFindAllPaths);
        List<List<String>> paths = new ArrayList<List<String>>();

        // ABD
        List<String> path1 = new ArrayList<String>();
        path1.add("A"); path1.add("B"); path1.add("D");

        // ABCD
        List<String> path2 = new ArrayList<String>();
        path2.add("A"); path2.add("B"); path2.add("C"); path2.add("D");

        //ACD 
        List<String> path3 = new ArrayList<String>();
        path3.add("A"); path3.add("C"); path3.add("D");

        //ABCD
        List<String> path4 = new ArrayList<String>();
        path4.add("A"); path4.add("C"); path4.add("B"); path4.add("D");

        paths.add(path1);
        paths.add(path2);
        paths.add(path3);
        paths.add(path4);

        findAllPaths.getAllPaths("A", "D");

        assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
    }
}
share|improve this question
2  
You should probably specify if it is assumed that there are no cycles. It is not a small detail. –  toto2 Mar 29 at 15:46
1  
It deals with cycles –  JavaDeveloper Mar 29 at 18:31

3 Answers 3

up vote 11 down vote accepted

This is beautiful, easy to read, and well-documented code. It is a joy reading this code, and there is very little to improve on the Java side.

The greatest weakness that shows in this code is not your skill with Java (which surpasses mine by far), but your knowledge of the English language.

  • In the addEdge JavaDoc you talk about arcs not edges.
  • The grammer in the error messages of that same method could be improved: “Source and Destination, both should be non-null.” could be “Both source and destination should be non-null” or “Source and destination should both be non-null”.
  • That method also sports the very confusing JavaDoc “@param length if length if” – I am not sure what that is supposed to mean.

But let's move on to technical aspects.

  • There is a nice bug in the recursive method: You are comparing T instances via ==:

    if (current == destination) {
    

    However, this defaults to comparing pointers. It only works here because the constant strings "A", "B", etc. are pooled by your Java implementation. Unless comparing for identity is what you actually want, please compare for equivalence: current.equals(destination).

  • The comment that recursive would be ignoring cycles is wrong – it will only construct paths where each node is visited at most once. This is the only correct way to handle cycles, otherwise there would be an infinite number of paths in a cyclic graph.

  • The error messages from validate make no sense.

    if (source == null) {
        throw new NullPointerException("The source: " + source + " cannot be  null.");
    

    So we'd get “The source: null cannot be null” as an error message. This is not helpful, and I'd suggest instead:

    if (source == null) {
        throw new NullPointerException("The \"source\" parameter cannot be  null.");
    
  • In your testing code, you go through too much hassle generating the expected paths. I am very fond of Arrays.asList(…):

    List<List<String>> paths = Arrays.asList(
        Arrays.asList("A", "B", "D"),
        Arrays.asList("A", "B", "C", "D"),
        Arrays.asList("A", "C", "D"),
        Arrays.asList("A", "C", "B", "D")
    );
    

    This code is terse and self-documenting. You put the paths into comments in addition to specifying them as code, which went wrong when the comment said ABCD above the ACBD path ;-)

    Furthermore, you test that the order of the returned paths is identical. The order of the paths should be considered irrelevant (you're actually interested in the set of paths), and unspecified as the usage of HashMap makes no guarantees about the order in which keys are kept. Indeed, you are iterating over the keySet(), which will determine the order of paths! A better test for equality might be:

    assertEquals(new HashSet<List<String>>(paths), new HashSet<List<String>>(result));
    
share|improve this answer
    
path is a LinkedHashSet –  JavaDeveloper Mar 29 at 18:40
    
@JavaDeveloper sorry for that, I've deleted that paragraph now. Don't know what I was thinking –  amon Mar 29 at 18:50
    
I am glad I coded as you would have given me a feedback, further asserts my confidence –  JavaDeveloper Mar 30 at 5:53
1  
Referenced in Graphic Design Review Proposal FYI. –  rolfl Jun 16 at 16:46

Just a few minor things:

  1. The comment is not correct here, it should be ACBD:

    //ABCD
    List<String> path4 = new ArrayList<String>();
    path4.add("A"); path4.add("C"); path4.add("B"); path4.add("D");
    

    You could use Guava's newArrayList (or write a similar method) to remove some duplication from the testcode:

    List<String> path4 = newArrayList("A", "C", "B", "D");
    
  2. The first call is unnecessary here:

    findAllPaths.getAllPaths("A", "D");
    
    assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
    
  3. For this:

    if (graph.containsKey(node)) return false;
    

    According to the Code Conventions for the Java Programming Language,

    if statements always use braces {}.

    Omitting them is error-prone. I've found the one-liner above hard to read because if you scan the code line by line it's easy to miss that at the end of the line there is a return statement.

  4. I'd rename

    • validate to validateNotSame,
    • paths to expectedPaths,

    for better clarity.

  5. GraphFindAllPaths could be simply Graph.

  6. From Clean Code, page 25:

    Classes and objects should have noun or noun phrase names like Customer, WikiPage, Account, and AddressParser. [...] A class name should not be a verb.

    Consider AllPathFinder instead of FindAllPaths, for example.

  7. You might want to create a defensive copy here:

    public FindAllPaths(GraphFindAllPaths<T> graph) {
        if (graph == null) {
            throw new NullPointerException("The input graph cannot be null.");
        }
        this.graph = graph;
    }
    

    It would prohibit malicious clients to modify the internal data of the class and might save you a couple of hours of debugging. (Effective Java, 2nd Edition, Item 39: Make defensive copies when needed)

  8. The Iterable functionality and the removeEdge method are not used nor tested. You might be able to remove them.

  9. Test methods are usually in a Test file (FindAllPathsTest, for example) and run by JUnit. They are usually in a separated source folder which enables to not package junit.jar (and other test dependencies) with production code. Maven's directory structure is a well-known project structure, consider using it (as well as Maven, Gradle, or any other build tool).

share|improve this answer
1  
I do agree with your naming conventions(eg: Graph), and seperate file for unit tests, but its just personally more convenient for me to club them all in a file. Although I agree with them –  JavaDeveloper Mar 29 at 18:41
    
You might want to create a defensive copy here - I agree with this too however creating deep copy of graph isnt trivial. –  JavaDeveloper Mar 30 at 5:55

This is really an interesting problem. First of all I want to mention that IMHO there is no polynomial solution to this task, because it is not an optimization problem. The required result is not max/min of something but an enumeration of all possible paths. I think that all possible paths may result in n! different paths in a complete graph, where n is the number of nodes. So finding a solution depends on the size of the input. If a big graph is on the input, then using this algorithm will take a lot of time and memory and probably won't finish. I don't know the exact usage of this solution, but I guess it is kind of a map/navigation app. If you don't mind I will mark some useful points and share my considerations:

  1. I don't see where you use the double value, which is held for every edge. I guess it will be used to compute the cost of a path and return the paths sorted by this criteria. If so consider finding only small set of the paths, one by one, every time using some popular algorithm for shortest path problem
  2. If you have a sparse graph on the input, then using Map per node will result in a lot of heavy objects, holding just a couple of values. This will increase the memory consumption unnecessarily. I don't know the use case, what type of nodes will be used (T), but I will suggest using single map from int to T and using the integers as node numbers. Then you can use double[][] matrix to hold the edge values and use the integers as indexes in the matrix. An example:
    • 0 -> "A"
    • 1 -> "B"
    • 2 -> "C"

Then an edge "A" --4.2--> "C" will be presented like this: matrix[0][2] = 4.2. Again this will result in a lot of unused cells of the matrix. Even a better solution will be to have a single array/list holding arrays/lists of neighbours for each node. Actually you are iterating over the neighbours so you do not need a HashMap, simply holding an list of key-value pairs is enough.What i mean is: List<List<Double>> nodes which represents the graph, and nodes.get(i) is another list holding pairs like (nodeNumber, edgeCost). Using the previous example:

List<Double> aNeighbours = nodes.get(0);
aNeighbours.set(2, 4.2);

If you use ArrayList consider providing small initial capacity, because the default is 16 I think.

I hope you find a working solution for this problem :).

share|improve this answer
2  
I strongly disagree about your second point. Using a Map<Node, Map<Node, Value>> is the objectively best way to represent a sparse graph in this context. If the graph is not sparse, then of course using a matrix representation is preferable memory-wise. Your List<List<Value>> idea seems like a specialization of using Maps, but has the drawback that it's not really sparse either (it's actually the exact same as your matrix representation). Using Maps has the advantage over matrix representations that fetching the set of outgoing edges doesn't have to be an O(n) operation. –  amon Mar 29 at 10:29
    
The List<List<Value>> won't have empty cells if you use LinkedList, but not the self-expanding ArrayList. I agree with you that using map will bring O(1) access to an edge, but as I saw the algorithm iterates over all neighbours and does not access them by key. And my concern about using a HashMap is that it has default load factor of 0.75 and in its best you will only use 0.75% of the allocated memory. It will resize itself (possibly double) when the load factor is reached. Actually you have a good point about using a Map. Here the productivity depends on the implementations of Map and List. –  egelev Mar 29 at 11:05
2  
If you use List<List<Double>>, then the only thing encoding which double belongs to which edge is the double's position in the list. Every possible edge must be represented, whether or not such an edge is present. –  user2357112 Mar 29 at 11:36

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.