Find all paths from source to destination

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 implements Iterable {

/* 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> graph = new HashMap>();

/**
* 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());
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

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> 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>(paths), new HashSet>(result));

StackExchange Code Review Q#45678, answer score: 17