Dijkstra's algorithm and development through testing

Hello dear readers. Some potential authors with whom we communicate think that there is a shortage of books on TDD in our assortment. We think how to approach it. But we are no less interested in what you think about her. Therefore, we offer translation of the article by the legendary Robert Martin, the author of the chic book “Clean Code”, under the cut. In an article (October 2016), Mr. Martin demonstrates the art of TDD using the example of Dijkstra’s algorithm.

Not so long ago, I was at a SCNA conference, and one of my colleagues turned to me about test development (TDD) and Dijkstra's algorithm. He asked if it would be possible to find a series of tests that would lead us to this algorithm. It seemed to me that this would be an interesting exercise, so I decided to perform it here.

As usual, I started with a degenerate test case.

public class MinPathTest { @Test public void nothing() throws Exception { } } 

Dijkstra's algorithm is a simple technique that allows you to find the shortest path along a graph with edges of arbitrary length. Having initial and final nodes, the algorithm will give you the shortest path and the length of this path.
')
So, from the very beginning, some interesting solutions are seen. How to submit an input graph? And how - the result of the algorithm? Perhaps most of these issues can be solved later. For now, let's focus on the maximally degenerate case: an empty graph.

 public void noGraph_NoPathZeroLength() throws Exception { Assert.assertEquals("{}0", minPath("")); } 

Already at the stage of the very first test I began to look for the output format. I decided to present the final path as a set of nodes in curly brackets. The length of the path is expressed as an integer following the parentheses.

This notation is for my tests only. I called this technique “combined statements” (composed asserts). I like to put statements in readable instructions.

Often, this means that the test requires you to write a simple translator that turns combined statements into a real API of the system under test.

Of course, to pass this test, just write the following:

 private String minPath(String graph) { return "{}0"; } 

Let's take a closer look at this test case. The minPath call is incorrect. Dijkstra's algorithm allows you to find the shortest path between two given nodes. So, if we assume that the nodes are named, the test should actually look like this:

 Assert.assertEquals("{}0", minPath("", "A", "Z")); 

But he is ugly. You can do refactoring to comb it a bit:

 private void assertPath(String graph, String expected) { assertEquals(expected, minPath(graph, "A", "Z")); } @Test public void noGraph_NoPathZeroLength() throws Exception { assertPath("", "{}0"); } 

Note that the assertPath method simply assumes that in all test cases we will use “A” and “Z” as the starting and ending point.

Last change: I think the path and length should be divided.

 private void assertMinPath(String graph, int length, String path) { assertEquals(length, minLength(graph, "A", "Z")); assertEquals(path, minPath(graph, "A", "Z")); } @Test public void noGraph_NoPathZeroLength() throws Exception { assertMinPath("", 0, "{}"); } privateintminLength(String graph, String begin, String end) { return 0; } private String minPath(String graph, String begin, String end) { return "{}"; } 

Since I check the statement with the help of two methods, I think it is logical to assume that these should be methods of a certain class that performs the Dijkstra algorithm. So let's refactor the delegate to get a new class.

 public class MinPathTest { private void assertMinPath(String graph, int length, String path) { PathFinder pf = new PathFinder(graph); assertEquals(length, pf.minLength("A", "Z")); assertEquals(path, pf.minPath("A", "Z")); } @Test public void noGraph_NoPathZeroLength() throws Exception { assertMinPath("", 0, "{}"); } } classPathFinder { publicPathFinder(String graph) { } publicintminLength(String begin, String end) { return 0; } public String minPath(String begin, String end) { return "{}"; } } 

I think it is interesting to note how much thought and effort was put into structuring this problem; this is just the first degenerate test. And now add a few more degenerate cases:

 @Test public void degenerateCases() throws Exception { assertMinPath("", 0, "{}"); //  assertMinPath("A", 0, "{}"); //  assertMinPath("B1C", 0, "{}");//     assertMinPath("A1C", 0, "{}");//   assertMinPath("B1Z", 0, "{}");//   } 

These tests forced me to solve the situation with a combined statement differently. In our tests, the edge of the graph will have the structure length. So, B1C is an edge of unit length connecting node B with node C.

I think this is all with degenerate cases. So let's give a little heat and discuss the first test case, for which it would take at least a symbolic brains movement.

 @Test public void oneEdge() throws Exception { assertMinPath("A1Z", 1, "{AZ}"); } 

The test, of course, fails. I am also uncomfortable with the fact that here I check two things at once - the path and the length, although they could be checked separately. It's a shame because I killed so much time, making up this combined statement, and now I want to make out again.

But I think this situation can be “tricky” to get around.

 private static String ANY = null; private void assertMinPath(String graph, Integer length, String path) { PathFinder pf = new PathFinder(graph); if (length != null) assertEquals((int)length, pf.minLength("A", "Z")); if (path != null) assertEquals(path, pf.minPath("A", "Z")); } ... @Test public void oneEdge() throws Exception { assertMinPath("A1Z", 1, ANY); } 

So the combined statement remains intact, and I can, if desired, ignore either of the two components. Now let's get to the test.

Obviously, now I have to do something like this:

 public int minLength (String begin, String end) { if (graph.equals("A1Z")) return 1; return 0; } 

But here I am breaking a few rules. First, the rule of universality, which says: the more specific the tests, the more generalized the code. In other words, the combat code should become more universal - only this way it will pass the falling test. Expressions that are specific to a falling test cannot be added to the combat code (in more detail about this I tell in Episode 19: Advanced TDD , on cleancoders.com).

The second rule violated is the connectedness of tests. We can not allow a strong connection between the tests in the combat code. The stronger the binding, the more fragile the tests. I do not want to promote solutions in which the only change in the combat code will break dozens or hundreds of tests. In this particular case, the combined statement should not be allowed to leak into the combat code API.

Thus, you should not pass a String graph into the PathFinder constructor. This also means that the minPath function minPath not return the String used by the combined statement.

So, we start to unleash the tests. The makePathFinder function below shows how this is done.

 public class MinPathTest { private static String ANY = null; private void assertMinPath(String graph, Integer length, String path) { PathFinder pf = makePathFinder(graph); if (length != null) assertEquals((int) length, pf.minLength("A", "Z")); if (path != null) assertEquals(path, pf.minPath("A", "Z")); } privatePathFindermakePathFinder(String graph) { PathFinder pf = new PathFinder(); Pattern edgePattern = Pattern.compile("(\\D+)(\\d+)(\\D+)"); Matcher matcher = edgePattern.matcher(graph); if (matcher.matches()) { String start = matcher.group(1); int length = Integer.parseInt(matcher.group(2)); String end = matcher.group(3); pf.addEdge(start, end, length); } return pf; } @Test public void degenerateCases() throws Exception { assertMinPath("", 0, "{}"); //   assertMinPath("A", 0, "{}"); //   assertMinPath("B1C", 0, "{}");//     assertMinPath("A1C", 0, "{}");//   assertMinPath("B1Z", 0, "{}");//   } @Test public void oneEdge() throws Exception { assertMinPath("A1Z", 1, ANY); } } classPathFinder { private List<Edge> edges = new ArrayList<>(); publicPathFinder() { } publicintminLength(String begin, String end) { int length = 0; for (Edge edge : edges) { if (edge.begin.equals(begin) &&edge.end.equals(end)) length += edge.length; } return length; } public String minPath(String begin, String end) { return "{}"; } public void addEdge(String start, String end, int length) { edges.add(new Edge(start, end, length)); } private static class Edge { public final String begin; public final String end; public final int length; public Edge(String begin, String end, int length) { this.begin = begin; this.end = end; this.length = length; } } } 

Note: parsing of the combined assertion remains in the test class. The PathFinder class is not aware of the amusing syntax of my tests. Also, I emphasize that in order for tests to be performed, the combat code must assume that the graph has only one edge. I mean, we have to get rid of this ANY .

 assertMinPath("A1Z", 1, "{AZ}"); 

So, let's compile a list of nodes available on the way. List? Oh yes, there is syntax
toString for lists. This test, as well as all subsequent ones will have to be changed as follows:

 @Test public void degenerateCases() throws Exception { assertMinPath("", 0, "[]"); //   assertMinPath("A", 0, "[]"); //   assertMinPath("B1C", 0, "[]"); //     assertMinPath("A1C", 0, "[]"); //   assertMinPath("B1Z", 0, "[]"); //   } @Test public void oneEdge() throws Exception { assertMinPath("A1Z", 1, "[A, Z]"); } 

Now, in order to pass this test, you need to change the auxiliary test function assertMinPath , by adding the toString call.

...

 if (path != null) assertEquals(path, pf.minPath("A", "Z").toString()); ... 

Add the path list to the PathFinder and simply load it into the minLength function.

 classPathFinder { private List<Edge> edges = new ArrayList<>(); ... publicintminLength(String begin, String end) { int length = 0; for (Edge edge : edges) { if (edge.begin.equals(begin) &&edge.end.equals(end)) { length += edge.length; path.add(edge.begin); path.add(edge.end); } } return length; } public List<String>minPath(String begin, String end) { return path; } ... 

Works. But I do not like that minLength also calculates the path. I think calculations and reporting should be divided.

 private void assertMinPath(String graph, Integer length, String path) { PathFinder pf = makePathFinder(graph); if (length != null) assertEquals((int) length, pf.getLength()); if (path != null) assertEquals(path, pf.getPath().toString()); } privatePathFindermakePathFinder(String graph) { PathFinder pf = new PathFinder(); ... pf.findPath("A", "Z"); return pf; } classPathFinder { private List<Edge> edges = new ArrayList<>(); private List<String> path = new ArrayList<>(); privateint length; ... publicintgetLength() { return length; } public List<String>getPath() { return path; } ... 

Already better. Now make sure that we get the correct length.

 assertMinPath("A2Z", 2, "[A, Z]"); 

Yeah, everything works fine. Let's try with two consecutive edges

 @Test public void twoEdges() throws Exception { assertMinPath("A1B,B1Z", 2, ANY); } 

As expected, the test failed, we get a zero length. To go through it, you need to parse the set of edges in the auxiliary function makePathFinder. It is quite simple. Just cut the graph in comma and set the regular expression matcher in a loop.

 privatePathFinder makePathFinder(String graph) { PathFinder pf = new PathFinder(); Pattern edgePattern = Pattern.compile("(\\D+)(\\d+)(\\D+)"); String[] edges = graph.split(","); for (String edge : edges) { Matcher matcher = edgePattern.matcher(edge); if (matcher.matches()) { String start = matcher.group(1); int length = Integer.parseInt(matcher.group(2)); String end = matcher.group(3); pf.addEdge(start, end, length); } } pf.findPath("A", "Z"); return pf; } 

Of course, the test still falls, so now we need to connect two edges. Suppose that the edges are specified in a certain order, so that the first edge begins with node A, and the second ends with node Z. In this case, we will provide the entire connection by replacing && with || in the findPath function:

 public void findPath(String begin, String end) { length = 0; for (Edge edge : edges) { if (edge.begin.equals(begin) || edge.end.equals(end)) { length += edge.length; path.add(edge.begin); path.add(edge.end); } } } 

Like this replacement? && to || . Yes, stupid. This solution will work only with two consecutive edges. We are already building Napoleonic plans. But, after all, it is not suitable.

Oh, we cope with the twoEdges test, and with the oneEdge tests, but we fail the degenerateCases tests.

To pass all these tests, I need an implementation that gives zero length and an empty path if the path from A to Z does not exist. Now, since I don't know how many edges there are (there can be zero, one, or two), I can't just take two. Instead, I separately analyze all three cases: if there are no edges, there is one edge or two edges. It turns out the following code:

 public void findPath(String begin, String end) { if (edges.size() == 0) return; else if (edges.size() == 1) { Edge edge = edges.get(0); if (edge.begin.equals(begin) &&edge.end.equals(end)) { path.add(edge.begin); path.add(edge.end); length += edge.length; } } else { for (Edge edge : edges) { if (edge.begin.equals(begin) || edge.end.equals(end)) { path.add(edge.begin); path.add(edge.end); length += edge.length; } } } } 

Yeah, it works, but it looks awful. The decision not only violates the rule of universality; it is simply disgusting. Moreover, the code incorrectly collects the path. For example, assertMinPath ("A1B, B1Z", 2, "[A, B, Z]"); fails because it gives [A, B, B, Z] . This could be fixed by adding another horrible if ; but there is a better idea. Let's go through the graph again from beginning to end.

 public void findPath(String begin, String end) { List<String> p = new ArrayList<>(); int l = 0; p.add(begin); for (Edge e = findEdge(begin); e != null; e = findEdge(e.end)) { p.add(e.end); l += e.length; if (e.end.equals(end)) { length = l; path = p; return; } } } private Edge findEdge(String begin) { for (Edge e : edges) { if (e.begin.equals(begin)) return e; } return null; } 

OK, it works. It is strange that one has to use temporary variable lengths and paths; but I see no other way to ignore nonexistent paths. I also believe that this solution eliminates the dependence on the order of nodes.

 @Test public void twoEdges() throws Exception { assertMinPath ("A1B,B1Z", 2, "[A, B, Z]"); assertMinPath ("B1Z,A1B", 2, "[A, B, Z]"); assertMinPath ("A1X,Y1Z", 0, "[]"); } 

Yes. Everything passes. I think it will work with three, and with a large number of edges. The same applies to graphs, in which there is only one complete path, and the remaining paths are hanging.

 @Test public void threeEdges() throws Exception { assertMinPath ("A2B,B3C,C4Z", 9, "[A, B, C, Z]"); assertMinPath ("B3C,C4Z,A2B", 9, "[A, B, C, Z]"); } @Test public void OnlyOnePath() throws Exception { assertMinPath ("A1B,B2C,C3Z,B4D,D6E", 6, "[A, B, C, Z]"); } 

But this one fails because we do not find the edges of C3Z when traversing the graph.

 assertMinPath ("A1B,B2C,C3D,C3Z", 6, "[A, B, C, Z]"); 

Okay. So, we can not just go around the graph in order. Instead, we will have to check all possible paths from the starting node; in the process, temporary variables will have to be written, and so on until we get to the end.

Then you can make sure that this requires pretty tricky: track all nodes, as well as the paths associated with these nodes, and the length of the paths. But the rest of the algorithm has not changed.

The iteration of the cycle is different. The cycle starts from the starting node, and then bypasses all unvisited neighboring nodes, and stores the total lengths and paths on these neighboring nodes.

Note: I use Integer.MAX_VALUE as a signal value: "unreachable from the visited node". The search is limited to only those nodes that have been achieved, since we are still going from beginning to end. Any node that could not be reached, obviously, is not the next on the way.

 classPathFinder { private List<Edge> edges = new ArrayList<>(); private Set<String>nodeNames = new HashSet<>(); private Map<String, Node> nodes = new HashMap<>(); private Node endNode; public void findPath(String begin, String end) { List<String> unvisited = initializeSearch(begin, end); for (String node = begin; node != null; node = getNext(unvisited)) { unvisited.remove(node); visit(node); } setupEndNode(end); } private List<String>initializeSearch(String begin, String end) { nodeNames.add(begin); nodeNames.add(end); List<String> unvisited = new ArrayList<>(nodeNames); for (String node : unvisited) nodes.put(node, new Node(Integer.MAX_VALUE)); nodes.get(begin).length = 0; return unvisited; } private void visit(String node) { List<Edge> neighbors = findEdges(node); Node curNode = nodes.get(node); for (Edge e : neighbors) { Node nbr = nodes.get(e.end); nbr.length = curNode.length + e.length; nbr.path = new ArrayList<String>(); nbr.path.addAll(curNode.path); nbr.path.add(node); } } private void setupEndNode(String end) { endNode = nodes.get(end); if (endNode.length != Integer.MAX_VALUE) endNode.path.add(end); else endNode.length = 0; } private String getNext(List<String> unvisited) { for (String name : unvisited) { Node candidate = nodes.get(name); if (candidate.length != Integer.MAX_VALUE) return name; } return null; } private List<Edge>findEdges(String begin) { List<Edge> found = new ArrayList<>(); for (Edge e : edges) { if (e.begin.equals(begin)) found.add(e); } return found; } publicintgetLength() { returnendNode.length; } public List<String>getPath() { returnendNode.path; } public void addEdge(String start, String end, int length) { edges.add(new Edge(start, end, length)); nodeNames.add(start); nodeNames.add(end); } private static class Edge { public final String begin; public final String end; public final int length; public Edge(String begin, String end, int length) { this.begin = begin; this.end = end; this.length = length; } } private static class Node { publicint length; public List<String> path; public Node(int l) { this.length = l; this.path = new ArrayList<>(); } } } 

Passes by Now we need to add a test in which there are parallel paths. Here is a simple, clearly failed test:

 assertMinPath ("A1B,B2Z,A1Z", 1, "[A, Z]"); 

Indeed, falls.

To pass this test, it is necessary to determine when the two paths converge. It's simple. If the length to the target node is not Integer.MAX_VALUE , then this node is reached via a different path. Since we are interested in the minimum, you can simply set the length value on this node as the minimum for converging paths. It turns out that the Integer.MAX_VALUE value Integer.MAX_VALUE very convenient as a signal label, since it replaces the “infinite” length.

 private void visit(String node) { List<Edge> neighbors = findEdges(node); Node curNode = nodes.get(node); for (Edge e : neighbors) { Node nbr = nodes.get(e.end); intnewLength = curNode.length + e.length; if (nbr.length>newLength) { nbr.length = newLength; nbr.path = new ArrayList<String>(); nbr.path.addAll(curNode.path); nbr.path.add(node); } } } 

Perhaps, you can speed up the algorithm a bit if you stop the search immediately after the end node is visited.

 for (String node = begin; node != null && !node.equals(end); node = getNext(unvisited)) { unvisited.remove(node); visit(node); } 

And in order to accelerate it even more, one can give priority to the search for unvisited nodes that can be reached via the shortest paths.

 private String getNext(List<String> unvisited) { String minNodeName = null; intminLength = Integer.MAX_VALUE; for (String name : unvisited) { Node candidate = nodes.get(name); if (candidate.length<minLength) { minLength = candidate.length; minNodeName = name; } } return minNodeName; } 

By all measures, this algorithm is a Dijkstra algorithm. The implementation is not very fast, since I used lists and sets, as well as a bunch of inefficient structures. To further overclock it, you will need to work hard. Moreover, some assumptions are woven into the algorithm, which should be eliminated. In particular, it is assumed that the input graph is directed, whereas in the universal algorithm such an assumption is not made. In the end, all the code needs some refactoring.

But I was keen to check whether TDD allows a step-by-step check of the Dijkstra algorithm. I think so, but I must say that this approach turned out to be rather awkward. Performing these first few tests, I had to resort to several hypothetical algorithms, between which there are no smooth transitions. However, each subsequent test revealed flaws of the previous solution, which could be corrected without much difficulty.

Will there be a higher-quality test sequence that will allow us to come to the Dijkstra algorithm in a not so roundabout way? Perhaps, but if so, then I did not find it.

In any case, it was interesting. Thanks to the listener who suggested this task to me.
Here is the ready code, which still needs to be brushed a little (dear reader, I leave this task to you as homework;))

 package dijkstrasAlg; import org.junit.Test; import java.util.*; import java.util.regex.Matcher; import java.util.regex.Pattern; import static org.junit.Assert.assertEquals; public class MinPathTest { private static String ANY = null; private void assertMinPath(String graph, Integer length, String path) { PathFinder pf = makePathFinder(graph); if (length != null) assertEquals((int) length, pf.getLength()); if (path != null) assertEquals(path, pf.getPath().toString()); } private PathFinder makePathFinder(String graph) { PathFinder pf = new PathFinder(); Pattern edgePattern = Pattern.compile("(\\D+)(\\d+)(\\D+)"); String[] edges = graph.split(","); for (String edge : edges) { Matcher matcher = edgePattern.matcher(edge); if (matcher.matches()) { String start = matcher.group(1); int length = Integer.parseInt(matcher.group(2)); String end = matcher.group(3); pf.addEdge(start, end, length); } } pf.findPath("A", "Z"); return pf; } @Test public void degenerateCases() throws Exception { assertMinPath("", 0, "[]"); //   assertMinPath("A", 0, "[]"); //   assertMinPath("B1C", 0, "[]");//     assertMinPath("A1C", 0, "[]");//   assertMinPath("B1Z", 0, "[]");//   } @Test public void oneEdge() throws Exception { assertMinPath("A1Z", 1, "[A, Z]"); assertMinPath("A2Z", 2, "[A, Z]"); } @Test public void twoEdges() throws Exception { assertMinPath("A1B,B1Z", 2, "[A, B, Z]"); assertMinPath("B1Z,A1B", 2, "[A, B, Z]"); assertMinPath("A1X,Y1Z", 0, "[]"); } @Test public void threeEdges() throws Exception { assertMinPath("A2B,B3C,C4Z", 9, "[A, B, C, Z]"); assertMinPath("B3C,C4Z,A2B", 9, "[A, B, C, Z]"); } @Test public void OnlyOnePath() throws Exception { assertMinPath("A1B,B2C,C3Z,B4D,D6E", 6, "[A, B, C, Z]"); assertMinPath("A1B,B2C,C3D,C3Z", 6, "[A, B, C, Z]"); } @Test public void parallelPaths() throws Exception { assertMinPath("A1B,B2Z,A1Z", 1, "[A, Z]"); assertMinPath("A1B,A1C,A2D,C5E,B8E,C1F,D3F,F2G,G3Z,E2G", 7,"[A, C, F, G, Z]"); } } class PathFinder { private List<Edge> edges = new ArrayList<>(); private Set<String> nodeNames = new HashSet<>(); private Map<String, Node> nodes = new HashMap<>(); private Node endNode; public void findPath(String begin, String end) { List<String> unvisited = initializeSearch(begin, end); for (String node = begin; node != null && !node.equals(end); node = getNext(unvisited)) { unvisited.remove(node); visit(node); } setupEndNode(end); } private List<String> initializeSearch(String begin, String end) { nodeNames.add(begin); nodeNames.add(end); List<String> unvisited = new ArrayList<>(nodeNames); for (String node : unvisited) nodes.put(node, new Node(Integer.MAX_VALUE)); nodes.get(begin).length = 0; return unvisited; } private void visit(String node) { List<Edge> neighbors = findEdges(node); Node curNode = nodes.get(node); for (Edge e : neighbors) { Node nbr = nodes.get(e.end); int newLength = curNode.length + e.length; if (nbr.length > newLength) { nbr.length = newLength; nbr.path = new ArrayList<String>(); nbr.path.addAll(curNode.path); nbr.path.add(node); } } } private void setupEndNode(String end) { endNode = nodes.get(end); if (endNode.length != Integer.MAX_VALUE) endNode.path.add(end); else endNode.length = 0; } private String getNext(List<String> unvisited) { String minNodeName = null; int minLength = Integer.MAX_VALUE; for (String name : unvisited) { Node candidate = nodes.get(name); if (candidate.length < minLength) { minLength = candidate.length; minNodeName = name; } } return minNodeName; } private List<Edge> findEdges(String begin) { List<Edge> found = new ArrayList<>(); for (Edge e : edges) { if (e.begin.equals(begin)) found.add(e); } return found; } public int getLength() { return endNode.length; } public List<String> getPath() { return endNode.path; } public void addEdge(String start, String end, int length) { edges.add(new Edge(start, end, length)); nodeNames.add(start); nodeNames.add(end); } private static class Edge { public final String begin; public final String end; public final int length; public Edge(String begin, String end, int length) { this.begin = begin; this.end = end; this.length = length; } } private static class Node { public int length; public List<String> path; public Node(int l) { this.length = l; this.path = new ArrayList<>(); } } }