Return to Answer

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.

However, I notice you are doing path.contains(t) where path is a List. This lookup takes linear time! It may be better to use a LinkedHashSet, which has a constant time membership test. You can copy the set to a list once the path is completed.

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

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