‘Begin at the beginning,’ the King said, very gravely,
‘and go on till you come to the end: then stop.’
— Lewis Carroll, Alice in Wonderland
For John McLane , the main protagonist in the 1995 action movie Die Hard with a Vengeance, things aren’t going according to plan. Freshly divorced, freshly fired from his job at the NYPD, and just having survived a
bomb attack on the New York Subway, he now faces another bomb, one that can only be defused by placing exactly four gallons of water on a scale attached to it. There are two empty plastic jugs nearby that can be filled or emptied at a nearby fountain. The large jug holds five gallons and the
small one three, but there are no other markings on the jugs. Is it possible for McLane to measure four gallons? And what is the fastest way of doing so? We will call this problem the die-hard problem.
Let us begin by introducing a notation for the different states of the problem. If \(L\) is the amount of water in the large jug and \(S\) the amount of water in the small one, we can label each possible state of the problem with the pair of numbers \(LS\). We start in the \(00\) state
in which both jugs are empty, and we are looking for a way to reach one of the states \(40\), \(41\), \(42\), or \(43\) in which the large jug contains four gallons of water.
Initially both jugs are empty and we can either fill the large one, which leads to the \(50\) state, or the small one, which leads to the \(03\) state. If we continue from the \(50\) state we have the following options: We can either fill the small jug from the fountain, which leads to the \(53\) state, or we can
empty the large jug, which leads back to the \(00\) state, or we can transfer three gallons from the large to the small jug, which leads to the \(23\) state. Similarly, if we continue from the 03 state we found in the first step, we can either fill the large jug to reach the 53 state, empty the small jug to
reach \(00\), or transfer water to the large jug to reach \(30\). In summary, we have found three new states in the second step — \(50\), \(23\), and \(30\) — which we can use as starting points for further exploration.
By continuing in this manner, we can construct a list of states that are reachable from the \(00\) state in a certain number of steps. In each step, we try to find new states by filling or emptying one of the jugs or by transferring water from one jug to the other. The result is shown in Fig. 7.1: in each row, newly discovered states are shown in bold face, and actions that don’t change the amount of water in either jug are marked with “–”. In step 6 we reach the state \(43\), the first state in which the large jug contains exactly
\(4\) gallons of water; a second possible solution \(40\) is found in step 7. We can stop after step 8 since no new states are discovered in this step. At this point we know that we have found all 16 ways of distributing water between the two jugs.
.
Step
Start
Fill L
Fill S
Empty L
Empty S
L to S
S to L
1
00
50
03
–
–
–
–
2
50
–
53
00
–
23
–
03
53
–
–
00
–
30
3
53
–
–
03
50
–
–
23
53
–
03
20
–
50
30
50
33
00
–
03
–
4
20
50
23
00
–
02
–
33
53
–
03
30
–
51
5
02
52
03
–
00
–
20
51
–
53
01
50
33
–
6
52
–
53
02
50
43\(*\)
–
01
51
03
–
00
–
10
7
43
53
–
03
40
–
52
10
50
13
00
–
01
–
8
40
50
43
00
–
13
–
13
53
–
03
10
–
40
Figure 7.1 The die-hard problem can be solved by repeatedly trying to reach new states by filling, emptying, or transferring water between the large jug L and the small jug S. The first row shows the states that are reachable
from “00”, the state in which both jugs are empty. After eight steps, we have discovered all possible ways of filling the two jugs.
By working our way backwards from the highlighted \(43\) entry in step 6, we can recover the steps that are necessary to solve the die-hard-problem. The \(43\) state was reached from the \(52\) state, which in turn was reached in the previous step from the \(02\) state,
then the \(20\) state, the \(23\) state, the \(50\) state, and the \(00\) state, in this order. Reversing the steps gives us the following solution:
.
Action
–
fill \(L\)
\(L\) to \(S\)
empty \(S\)
\(L\) to \(S\)
fill \(L\)
\(L\) to \(S\)
Result
00
50
23
20
02
52
43
The method by which we have found this solution is closely related to an important algorithm known as breadth-first search, often abbreviated as BFS, a general-purpose algorithm for exploring linked data structures such as trees and graphs. Before we discuss breadth-first search in more detail, let’s first review the basics of graphs and
their implementation.
If we take a step back and ignore the specifics of this puzzle — the jugs, the water, and the rules for transferring it — we see that the die-hard problem is a special case of a much more general problem: Given a set of interconnected objects, is it possible to find a path from one object to another? And, if yes,
how quickly? We can study such questions with the help of graph theory.
Let’s start with the notion of a graph. A graph is a mathematical abstraction for modeling objects that are connected to each other. In general, a graph consists of two parts: a set of nodes (also referred to as vertices), which represent the objects of interest, and a set of edges that tell us which pairs of objects are related to each other.
Let’s call the graph that underlies the die-hard problem the die-hard graph. This graph can be constructed as follows. The nodes of the die-hard graph are the states of the puzzle, and as we have seen in Fig. 7.1, there are such 16 nodes:
These nodes are connected by the graph’s edges. We write \(LS\to L'S'\) if the \(L'S'\) state can be reached from the \(LS\) state in a single step, in this case by filling, emptying, or transferring water between the jugs. The first row in
Fig. 7.1, for example, tells us that 50 and 03 are reachable from the starting state 00, which gives us the first two edges of the graph:
The remaining edges can be read off from the other rows of the table; the die-hard graph contains a total of 58 edges.
Graphs are often visualized by drawing the nodes as circles and the edges as lines or arrows connecting the nodes. A graphical representation of the die-hard graph is shown in Fig. 7.2. Moving right or left in the
diagram corresponds to filling or emptying the large jug, moving up or down to filling or emptying the small jug, and moving diagonally to transferring water from one jug to another. The 17 edges in the interior of the graph are called undirected edges because they don’t have an arrow symbol at either end. Undirected edges can we followed in either direction: The edge \(03\Edge {}53\) that connects the nodes labeled \(03\) and \(53\) indicates that we can move back
and forth between these two states by emptying or filling the large jug. The remaining 24 edges are directed edges and can only be followed in the direction indicated by the arrow symbol. For instance, \(33\to 03\) is a directed edge that corresponds to emptying the large jug; since there is no direct way to refill the large jug with exactly
3 gallons, there is no edge in the opposite direction. (Every undirected edge \(A\Edge {}B\) is obviously equivalent to a pair of directed edges \(A\to B, B\to A\).)
Figure 7.2 The die-hard graph consists of nodes that represent the states of the puzzle and edges that indicate possible transition between states.
A path is a sequence of nodes that are connected by edges, and the number of edges on a path is called its length. The path that leads from the 00 node to the 43 node can be written as follows:
This path has length 6 because it consists of 6 edges.
What is a good data structure for storing the edges of a graph? In most applications, we are primarily interested in the subset of edges that start a particular node. For a given node \(A\), we therefore gather all outgoing edges \(A\to B_1,\dots A\to B_k\) and store them as a list of “neighbors”
\((B_1, \dots , B_k)\). Such a list of neighbors is also called the adjacency list of \(A\) since it contains all nodes that adjacent to \(A\) in the graph. For example, the adjacency list of the node labeled 00 in the die-hard graph consists of its two neighbors \((50, 03)\), and the adjacency list
of 50 consists of the three nodes \((53, 00, 23)\). In fact, each row in Fig. 7.1 corresponds to the adjacency list of one of the nodes in the die-hard graph.
For small graphs, we can keep all nodes and their adjacency lists in memory at once. For example, we can use a hash table to associate each node in the die-hard graph with its adjacency list:
For small graphs, this is a reasonable approach, but many interesting graphs are so complex that it is nearly impossible to list all their nodes and edges — in fact, some of the graphs we will study in the next chapter are so large that they do not even fit into memory.
Instead of storing the adjacency lists of every node in a fixed data structure, we will therefore represent graphs using an interface that lets us compute adjacency lists on demand. The definition of this interface is shown in Listing 7.1. The first method of Graph is neighbors(), which computes the adjacency
list of a particular node and returns it as an Iterable of type N. (See Appendix B.5 for more information about Iterable.) The second method nodes() returns all nodes in the graph. For some of the graphs we will discuss it is not feasible to enumerate all nodes, so this
method is optional and its default implementation simply throws an exception.
Listing 7.1ch7 / Graph
// Basic interface for representing directed graphs with nodes of type N.
public interface Graph<N> {
Iterable<N> neighbors(N node);
default Iterable<N> nodes() {
throw new UnsupportedOperationException();
}
// ...
}
To implement the die-hard graph using this interface, we first we have to choose a type N for the nodes of the graph. Since there are two jugs that both hold less than ten gallons of water, we can describe each node by a String that contains a pair of decimal digits such as "00" or "43"; We can then define a class DieHardGraph that implements the Graph interface, as shown in Listing 7.2. The helper method makeNode() constructs the String label of a node from two integers.
Listing 7.2ch7 / DieHardGraph
public class DieHardGraph implements Graph<String> {
public static String makeNode(int large, int small) {
if (large < 0 || large > 5 || small < 0 || small > 3)
throw new IllegalArgumentException();
return String.format("%d%d", large, small);
}
// ...
}
Both the neighbors() and the nodes() methods must return collections of
Strings. Let’s start with the implementation of nodes(), which returns a list of all nodes in the die-hard graph (Listing 7.3). We use two loops to generate the labels of all possible nodes and then filter out nodes such as 11 or 32, which represent states in which neither jug is completely full or empty; Exercise 7.1 discusses how these nodes are connected to the rest of the graph.
Listing 7.3ch7 / DieHardGraph
@Override
public Iterable<String> nodes() {
var nodes = new ArrayList<String>();
for (int large = 0; large <= 5; large++) {
for (int small = 0; small <= 3; small++)
if (small == 0 || small == 3 || large == 0 || large == 5)
nodes.add(makeNode(large, small));
}
return nodes;
}
The neighbors() method computes all nodes of the die-hard graph that can be reached from a given node. Assume the node in question has the label \(LS\), so the large jug
contains \(L\) gallons of water and the small one \(S\) gallons. From \(LS\) we can reach the following states by filling, emptying, or transferring water between jugs:
• Filling the large jug leads to the \(5S\) state, emptying it to the \(0S\) state.
• Filling the small jug leads to the \(L3\) state, emptying it to the \(L0\) state.
• Transferring water from the large to the small jug leads to the state \(L-m,S+m\), where \(m\) is the amount of water transferred. If the entire contents of the large jug fit into the small jug, we transfer \(m=L\) gallons; otherwise, we only transfer as much as fits the
small jug, namely \(m=3-S\). We can combine these two cases into one expression \(m=\min (L, 3-S)\).
• Similarly, transferring water from the small to the large jug leads to the state \(L+m,S-m\), where \(m=\min (5-L, S)\).
Notice that each of these rules can lead back to the original node \(LS\), for example when filling the large jug in a state of the form \(5S\) or when emptying or transferring water from either jug in the \(00\) state. Since we are only interested in edges that lead to new states, we have to
remove such self-loops when computing the list of neighbors.
Box 7.1: Simple Graphs and Multigraphs Graph theory distinguishes between simple graphs and multigraphs, which both consist of nodes and edges but differ in the kinds of edges they allow. Here is an example:
The left image shows a simple graph and the right image a multigraph. The difference between the two is that only multigraphs are allowed to have self-loops (here, from A back to itself) and multiple edges between the same pair of nodes (here, from A to C).
Simple graphs are easier to model and easier to process algorithmically, but there are many situations where the added flexibility of multigraphs is required. Even though we will be mostly concerned with simple graphs in this book, many of the ideas and algorithms we will discuss readily generalize to
multigraphs.
The neighbors() method shown in in Listing 7.4 computes the neighbors of a given node by trying all the
different ways of filling and emptying the jugs. The method first extracts the two decimal digits from node and stores them in large and small. It then computes the amount of water that can be transferred from the large to the small jug largeToSmall
and from the small to the large jug smallToLarge. Afterwards the neighbors of node can be computed using the rules discussed above. We store the result in a set data structure to get rid of all potential duplicates and remove the current node itself before returning
it to ensure that no node is its own neighbor. (The remove() method does nothing if node isn’t contained in the set, so we can call it unconditionally.)
Listing 7.4ch7 / DieHardGraph
@Override
public Iterable<String> neighbors(String node) {
int large = Integer.parseInt(node.substring(0, 1));
int small = Integer.parseInt(node.substring(1, 2));
int largeToSmall = Math.min(large, 3 - small);
int smallToLarge = Math.min(5 - large, small);
var n = new HashSet<String>();
n.add(makeNode(5, small));
n.add(makeNode(0, small));
n.add(makeNode(large, 3));
n.add(makeNode(large, 0));
n.add(makeNode(large - largeToSmall, small + largeToSmall));
n.add(makeNode(large + smallToLarge, small - smallToLarge));
n.remove(node);
return n;
}
which agrees with the list of neighbors shown in Fig. 7.1. In fact, we can reconstruct the entirety of Fig. 7.1 by repeatedly computing lists of neighbors and exploring newly
found ones; we will study the resulting algorithm in the following section.
Exercises
Exercise 7.1.The diagram of die-hard graph in Fig. 7.2 doesn’t show the eight
interior nodes named 11, 12, …, 42. How are these missing nodes connected to the rest of the graph?
Exercise 7.2.Sketch the die-hard graph that results when the large jug holds 2 gallons and the small jug 1. Can you construct a path through this graph that starts
and ends at the same node and visits every other node exactly once? (Such a path is called a Hamiltonian cycle.)
