When we discussed the die-hard problem at the beginning of this chapter, we manually constructed a solution by first tabulating the reachable states of the problem (Fig. 7.1) and then retracing our steps back from the final state 43 to
the start 00. This gave us a list of all the intermediate steps that must be taken to solve the problem:
The same idea can be used to construct paths through any graph using breadth-first search.
The key insight is the following: When breadth-first search discovers a new node \(v\) while inspecting the neighbors of another node \(u\), we know that the every shortest path from the start that goes through \(v\) must include the edge \(u\to v\) —
otherwise, we would have discovered a shorter route to \(v\) earlier. We say that \(u\) is the predecessor of \(v\) in any shortest path through \(v\), and if we know the predecessor of every node, we can determine the shortest paths from the start to every other node.
Figure 7.3 illustrates the data structure we obtain by recording the predecessor of each node as we traverse the die-hard graph. The data structure is constructed from left to right, starting with the 00 node, which is visited first
and doesn’t have any predecessors. Breadth-first search then advances to the two direct neighbors of 00, the nodes labeled 03 and 50, so we add two links \(00\leftarrow 03\) and \(00\leftarrow 50\) to indicate that 03 and 50 were discovered through 00.
Similarly, every other node in Fig. 7.3 links to the node through which it was discovered during breadth-first search. After constructing this tree of predecessors, we can revert all arrows to find the shortest paths from the start to every
reachable node in the graph. For example, the shortest path from 00 to 51 is \(00\to 03\to 30\to 33\to 51\).
Figure 7.3 Traversing the die-hard graph using breadth-first search and recording the predecessors of each node produces a tree-like structure. The path from any node to the root corresponds to the shortest path between the two nodes in the graph, in reverse
order.
We can represent this tree of paths through the graph using a linked data structure in which each path segment points to its predecessor. For example, if we define a record with two fields node and predecessor
record Path<N>(N node, Path<N> predecessor) {
}
the tree of paths shown in Fig. 7.3 can be constructed by starting with an empty path for the root 00 and then successively extending it to additional nodes in the graph:
var p00 = new Path<>("00", null);
var p03 = new Path<>("03", p00);
var p50 = new Path<>("50", p00);
var p30 = new Path<>("30", p03);
var p23 = new Path<>("23", p50);
var p53 = new Path<>("53", p50);
...
All nodes that were discovered while scanning the neighbors of a particular node share the same predecessor.
We will use a slightly different definition of Path. First, we define an interface called BasicPath that collects a few methods for working with paths stored in reverse order, which will prove helpful when we implement weighted paths in
Section 8.5. The definition of BasicPath is shown in Listing 7.12. It defines two methods that must be provided by classes
implementing this interface: node() and predecessor().
Listing 7.12ch7 / BasicPath
// A linked list of nodes in reverse order.
public interface BasicPath<N> {
N node();
BasicPath<N> predecessor();
// ...
}
We then provide a concrete implementation of BasicPath as a record with two fields predecessor and node (Listing 7.13). Since Java
automatically generates accessor methods for all fields of a record — in this case node() and predecessor() — this definition of Path automatically satisfies the BasicPath interface.
Listing 7.13ch7 / Path
// A simple implementation of the Path interface.
public record Path<N>(N node, Path<N> predecessor)
implements BasicPath<N> {
}
The main advantage of this definition is that any functionality we add to BasicPath becomes available in Path and in every other data structure that implements BasicPath.
Two examples of such methods are shown in Listing 7.14. The first is length(), which computes the length of a path by following the predecessors from the current segment back to the start of the path. Similarly, toNodeList() computes the list of
nodes on a path in forward order, from the start to the current path segment. The method first gathers all nodes in reverse order as it moves from the current path segment to the start, and then reverses the resulting list before returning it. Another simple method that an be added to BasicPath is discussed in Exercise 7.5.
Listing 7.14ch7 / Path
// Compute the number of edges along this path.
default int length() {
int length = 0;
for (Path<N> p = backlink(); p != null; p = p.backlink())
length++;
return length;
}
// Return a list of nodes on this path in forward order.
default List<N> toNodeList() {
var list = new ArrayList<N>();
for (Path<N> p = this; p != null; p = p.backlink())
list.add(p.node());
Collections.reverse(list);
return list;
}
We can now implement an extended version of breadth-first search that constructs the shortest paths to all reachable nodes while traversing a graph. The resulting scanPaths() method is shown in Listing 7.15. The main change is to replace the queue of unexplored nodes with a queue of unexplored Paths. In each
step, we remove one Path from the queue and examine all neighbors of its endpoint. For each neighbor we haven’t encountered before, we extend the current path to this node and add it to unexplored for later examination. The
algorithm stops when a path has been found that matches the specified condition or when all reachable nodes have been scanned.
Listing 7.15ch7 / Graph
// Find the shortest path that matches 'condition'.
default Path<N> scanPaths(N start, Predicate<Path<N>> condition) {
var seen = new HashSet<>(List.of(start));
var unexplored = new ArrayDeque<Path<N>>();
unexplored.add(new Path<>(start, null));
while (!unexplored.isEmpty()) {
var path = unexplored.removeFirst();
if (condition.test(path))
return path;
for (N neighbor : neighbors(path.node())) {
if (seen.add(neighbor))
unexplored.addLast(new Path<>(neighbor, path));
}
}
return null;
}
For situations where we are primarily interested in finding a node (and not a path) that matches a certain condition, we add a method called findPathTo() that takes an argument of type
Predicate and returns the shortest path to the nearest node that satisfies this predicate (Listing 7.16). The implementation of this method is a
simple wrapper around the more general scanPaths().
Listing 7.16ch7 / Graph
// Find the shortest path to a node that matches 'condition'.
default List<N> findPathTo(N start, Predicate<N> condition) {
var p = scanPaths(
start, path -> condition.test(path.node()));
return p == null ? List.of() : p.toNodeList();
}
Using findPathTo(), we can solve the die-hard problem by searching for a path from the 00 node to the nearest node whose label starts with the
letter “4”:
This is the solution we manually constructed at the beginning of this chapter.
Exercises
Exercise 7.5.Extend the BasicPath interface with a method printNodes() that prints the nodes along the path in sequential order, from the start to the end, similar to the following example:
var path = new Path<>("50",
new Path<>("03", new Path<>("00", null)));
System.out.println(path.printNodes());
// Output: 00 -> 03 -> 50