Chapter 7 Traversing Graphs

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.

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:

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.

7.1 The Die-Hard Graph¶

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:

\begin{equation*} 00, 01, 02, 03, 10, 13, 20, 23, 30, 33, 40, 43, 50, 51, 52, 53. \end{equation*}

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:

\begin{equation*} 00\to 50,\qquad 00\to 03 \end{equation*}

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\).)

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:

\begin{equation*} 00\to 50\to 23\to 20\to 02\to 52\to 43 \end{equation*}

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:

var dieHard = new HashMap<>();
dieHard.put("00", List.of("50", "03"));
dieHard.put("01", List.of("00", "03", "10", "51"));
dieHard.put("02", List.of("00", "03", "20", "52"));
dieHard.put("03", List.of("00", "30", "52"));
...

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.

// 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.

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 of the Graph interface return a collection 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.

@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.

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

@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;
}

If we want to compute the neighbors of node \(30\), for example, we first create an instance of DieHardGraph, and then call its neighbors() method:

var graph = new DieHardGraph();
System.out.println(graph.neighbors("30"));

The output is

[00, 33, 03, 50]

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

[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?

[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.)

7.2 Breadth-First Search¶

One of the simplest — and most useful — algorithms for exploring graphs and other graph-like data structures is known as breadth-first search (BFS). It works similar to the way we explored the die-hard graph at the beginning of this chapter: Starting at a particular node \(n\), the algorithm radially moves outward, first visiting \(n\) itself, then the neighbors of \(n\), then the neighbors of neighbors of \(n\), and so on, until all the nodes that are reachable from \(n\) have been explored. Breadth-first search visits every reachable node exactly once, even if there are multiple ways to reach it.

A more formal description of breadth-first search is shown in Algorithm 7.1. To keep track of nodes that still need to be explored, breadth-first search maintains a queue of nodes \(Q\), which is declared in line 3. A queue is a linear data structure similar to a list that allows adding and removing elements in “first-in, first-out” (FIFO) order: New elements are added to the end of the queue, after all existing elements, using the \(\text {append}()\) function, and the oldest element in the queue can be removed from the data structure using \(\text {removeFirst}()\). In breadth-first search, the use of a queue ensures that nodes are visited in the order in which they were discovered. We assume that every node has a field seen that we can use to keep track of which nodes have been encountered before; we use this field to ensure that no node is visited more than once. At the beginning of the algorithm, all seen fields are set to False.

The algorithm then processes the starting node start by adding it to the queue and marking it as seen. Most of the work is done by the outer while loop, which continues as long as there are unexplored nodes in \(Q\). In each iteration, the node at the front of the queue is removed and explored. The first iteration always explores start, since this is the only element in \(Q\); in subsequent iterations, the queue contains the neighbors of start, then the neighbors of the neighbors, and so on. A particular node \(u\) is explored by inspecting its neighbors in the graph. Each neighbor \(v\) that hasn’t been encountered before is added to \(Q\) for later exploration and then marked as seen. The algorithm continues until \(Q\) is empty and all nodes in the graph that are reachable from start have been visited.

The scan() method in Listing 7.5 illustrates one possible implementation of breadth-first search. The method traverses a Graph starting at node start until it finds a node that satisfies a certain condition. This condition is provided as an argument of type Predicate and can be specified by the caller of scan(); we will discuss predicates in more detail below.

// Scan all nodes that are reachable from 'start'. Stop when
// 'condition' is satisfied.
default N scan(N start, Predicate<N> condition) {
    var seen = new HashSet<>(List.of(start));
    var unexplored = new ArrayDeque<>(List.of(start));
    while (!unexplored.isEmpty()) {
        N node = unexplored.removeFirst();
        if (condition.test(node))
            return node;
        for (N neighbor : neighbors(node)) {
            if (seen.add(neighbor))
                unexplored.addLast(neighbor);
        }
    }
    return null;
}

The code uses two main data structures. The first is unexplored, implemented using Java’s ArrayDeque class, which corresponds to the \(Q\) variable in Algorithm 7.1 and holds all nodes that still need to be explored in first-in first-out order. The second is the HashSet seen, which keeps track of all nodes that have been encountered by the algorithm so far; this set replaces the seen field used in Algorithm 7.1.

In each iteration of the main loop, scan() removes one node from the start of the queue. If it satisfies the search condition, the traversal is stopped immediately and node is returned as the search result. Otherwise, all neighbors of node that haven’t been seen before are added to the unexplored queue. The return statement at the end of the function is only reached if none of the reachable nodes satisfy the search condition; in this case, the search fails and scan() returns null.

The second argument to scan() is the search condition. The type Predicate is a so-called functional interface that describes functions that take a single argument of type N and return a boolean value. (See Appendix B.6 for an overview of functional interfaces and predefined function types such as Predicate.) The use of a predicate argument makes it possible to customize the behavior of scan() from the outside. Effectively, the method implements a generalized version of breadth-first search that delegates part of the algorithm — the decisions when to stop the traversal and what action to perform when a new node is visited — to the function condition.

If we call scan() with a predicate that always returns false, breadth-first search runs until all nodes that are reachable from the start have been visited. This is such a common and useful operation that we provide it as a dedicated function visitNodes() in Listing 7.6. The second argument of visitNodes() is a Consumer, a type of function that accepts a single value of type N but (unlike Predicate) doesn’t return a value. The implementation of visitNodes() delegates the actual traversal to scan(), using a predicate that always returns false to ensure that every reachable node is visited. In addition, the predicate hands over every node to consumer by calling its accept() method.

// Visit all nodes that are reachable from 'start'.
default void visitNodes(N start, Consumer<N> consumer) {
    scan(start, node -> {
        consumer.accept(node);
        return false;
    });
}

Let’s take a look at a few examples to see how scan() and visitNodes() can be used in practice. We can find out whether the 43 node is reachable from the 00 node by calling scan() as follows:

if (new DieHardGraph().scan("00", "43"::equals) != null) {
    System.out.println("solution found");
}

The predicate passed to scan() is the expression "43"::equals, which is a reference to equals() method of the string "43". With this predicate, scan() traverses the graph until it finds a node that matches "43".

We can print the nodes of the die-hard graph in the order they are encountered by breadth-first search by calling visitNodes() and passing a reference to println() as the last argument:

new DieHardGraph().visitNodes("00", System.out::println);
// Output: 00 03 50 30 53 23 33 20 51 02 01 52 10 43 13 40

Alternatively, we can collect the reachable nodes in a list by specifying a function that appends each node to a given data structure:

var nodes = new ArrayList<>();
new DieHardGraph().visitNodes("00", nodes::add);

Every time visitNodes() reaches a new node, it calls the add() method associated with nodes.

The Anatomy of Graphs

There is a useful variation of breadth-first search that groups reachable nodes by their distance from the start. Instead of processing nodes and their neighbors one by one, this variation first determines all nodes at distance 1 from the start, then all nodes at distance 2, then all nodes at distance 3, and so on. We refer to the set of all nodes at a fixed distance from a certain node as a layer and represent it using the GraphLayer type defined in Listing 7.7.

// The set of nodes at a certain distance from 'start'.
public record GraphLayer<N>(
        N start,
        int distance,
        List<N> nodes) {
}

The scanLayers() method in Listing 7.8 traverses a graph layer by layer until a certain condition is met. The traversal starts at the specified node start. The implementation of scanLayers() is similar to that of Graph.scan(), except that the outer loop now processes one layer at a time. In each iteration, we examine all neighbors of the current layer and add every newly discovered node to next; after processing the current layer, this becomes the next layer of nodes. The loop stops when a layer that matches condition has been found or after the final layer has been processed. Notice that this version of breadth-first search doesn’t require the use of a queue to maintain the list of unexplored nodes. We also define an an additional method visitLayers() that unconditionally visits every layer that is reachable from start.

// Scan all layers reachable from 'start' and stop at the first one
// that satisfies 'condition'.
default GraphLayer<N> scanLayers(N start,
        Predicate<GraphLayer<N>> condition) {
    var seen = new HashSet<>(List.of(start));
    var next = new ArrayList<N>();
    next.add(start);
    for (int distance = 0; !next.isEmpty(); distance++) {
        var layer = new GraphLayer<>(start, distance, next);
        if (condition.test(layer))
            return layer;
        next = new ArrayList<>();
        for (var node : layer.nodes()) {
            for (N neighbor : neighbors(node)) {
                if (seen.add(neighbor))
                    next.add(neighbor);
            }
        }
    }
    return null;
}

// Visit all layers reachable from 'start'.
default void visitLayers(N start, Consumer<GraphLayer<N>> consumer) {
    scanLayers(start, layer -> {
        consumer.accept(layer);
        return false;
    });
}

Let’s use these two functions to explore the die-hard graph further. Maybe the simplest application of visitLayers() is to print all layers that are reachable from node 00:

var graph = new DieHardGraph();
graph.visitLayers("00", System.out::println);

The output agrees with the table in Fig. 7.1: all 16 nodes can be reached in seven steps or less, and the first node in which one of the jugs contains four gallons is found in the layer at distance 6.

GraphLayer[distance=0, start=00, nodes=[00]]
GraphLayer[distance=1, start=00, nodes=[03, 50]]
GraphLayer[distance=2, start=00, nodes=[30, 53, 23]]
GraphLayer[distance=3, start=00, nodes=[33, 20]]
GraphLayer[distance=4, start=00, nodes=[51, 02]]
GraphLayer[distance=5, start=00, nodes=[01, 52]]
GraphLayer[distance=6, start=00, nodes=[10, 43]]
GraphLayer[distance=7, start=00, nodes=[13, 40]]

What happens if we start at another node, for example node 10?

graph.visitLayers("10", System.out::println);

In this case, we can still reach all 16 nodes, but now we need four steps at most, and the original problem of measuring four gallons becomes almost trivial, requiring only two steps:

GraphLayer[distance=0, start=10, nodes=[10]]
GraphLayer[distance=1, start=10, nodes=[00, 01, 13, 50]]
GraphLayer[distance=2, start=10, nodes=[03, 51, 40, 53, 23]]
GraphLayer[distance=3, start=10, nodes=[30, 33, 43, 20]]
GraphLayer[distance=4, start=10, nodes=[52, 02]]

For a given node \(n\), the maximum number of steps it takes to reach any other node of the graph is known as that node’s eccentricity \(\epsilon (n)\). (We just saw that the nodes 00 and 10 in the die-hard graph have the eccentricities 7 and 4, respectively.) In general, the eccentricity tells us how a node is positioned relative to all other nodes in the graph. A small value of \(\epsilon (n)\) indicates that \(n\) close to every reachable node, whereas a large value means that \(n\) is far away from (at least) one node. The eccentricity therefore allows us to distinguish between the center of the graph (small \(\epsilon \)) and its periphery (large \(\epsilon \)). Several important graph quantities are defined in terms of the eccentricity:

• • The radius of a graph is the smallest eccentricity of any of its nodes.

• • The center of a graph is the set of nodes whose eccentricity equals the graph’s radius.

• • The diameter of a graph is the largest eccentricity of any of its nodes. This is the length of the “longest shortest path” between any pair of nodes.

A small radius indicates that all nodes are close to its center, and a small diameter indicates that all nodes close to each other.

To compute the eccentricity of a node \(n\), we can use breadth-first search to traverse the graph starting at \(n\) and continue until no new nodes are discovered; the eccentricity is the distance from \(n\) to the last node that was found. Alternatively, we can traverse the layers of the graph to find the one that is farthest from \(n\). The farthestLayer() method defined in Listing 7.9 computes this farthest layer by iterating over all layers using Graph.visitLayers() and keeping only the last one. (The farthest variable must be defined inside an anonymous object result to work around the unfortunate limitation that lambda expressions in Java cannot modify local variables defined in the surrounding scope; for more details about this technique, see the discussion in Appendix B.6.)

// Find the set of nodes with the maximum distance from 'node'.
public static <N> GraphLayer<N> farthestLayer(
        Graph<N> graph, N node) {
    var result = new Object() {
        GraphLayer<N> farthest;
    };
    graph.visitLayers(node, layer -> result.farthest = layer);
    return result.farthest;
}

Using farthestLayer(), we can now define functions that compute a node’s eccentricity as well as a graph’s radius and diameter (Listing 7.10). The implementation of eccentricity() simply determines the layer farthest from n and returns its distance, and the functions radius() and diameter() compute the radius and diameter by iterating over all nodes and returning the smallest or largest eccentricity encountered.

// Compute the eccentricity of the node n.
public static <N> int eccentricity(Graph<N> graph, N n) {
    return farthestLayer(graph, n).distance();
}

// Compute the radius of 'graph'.
public static <N> int radius(Graph<N> graph) {
    int min = Integer.MAX_VALUE;
    for (N node : graph.nodes()) {
        min = Math.min(min, eccentricity(graph, node));
    }
    return min;
}

// Compute the diameter of 'graph'.
public static <N> int diameter(Graph<N> graph) {
    int max = 0;
    for (N node : graph.nodes()) {
        max = Math.max(max, eccentricity(graph, node));
    }
    return max;
}

In the case of the die-hard graph, the smallest eccentricity, and therefore the graph’s radius, is 4. There are four nodes with this eccentricity: 10, 13, 40, and 43. They form the center of the graph, and from them every other node can be reached in at most four steps. The diameter of the die-hard graph is 7, which means that the hardest measuring problems require seven steps. There are eight such problems:

A slightly harder version of the die-hard problem is therefore: Given an empty 5 gallon jug and a full 3 gallon jug, find a way to measure exactly four gallons of water. This is the hardest measuring problem for these two jugs.

Exercises

[7.3]True or false: The farthestLayer() method defined in Listing 7.9 never returns null.

[7.4]Compute the eccentricities of all nodes in the die-hard graph (Fig. 7.2).

7.3 Retracing Paths¶

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:

\begin{equation*} 00\to 50\to 23\to 20\to 02\to 52\to 43. \end{equation*}

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\).

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.11. It defines two methods that must be provided by classes implementing this interface: node() and predecessor().

// 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.12). 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.

// 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.13. 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.

// Compute the number of edges along this path.
default int length() {
    int length = 0;
    for (BasicPath<N> p = predecessor(); p != null;
            p = p.predecessor())
        length++;
    return length;
}

// Return a list of nodes on this path in forward order.
default List<N> toNodeList() {
    var list = new ArrayList<N>();
    for (BasicPath<N> p = this; p != null; p = p.predecessor())
        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.14. 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.

// 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.15). The implementation of this method is a simple wrapper around the more general scanPaths().

// 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”:

DieHardGraph graph = new DieHardGraph();
var path = graph.findPathTo("00", node -> node.charAt(0) == '4');
System.out.println(path);
// output: [00, 50, 23, 20, 02, 52, 43]

This is the solution we manually constructed at the beginning of this chapter.

Exercises

[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

7.4 Problems¶

River-Crossing Problems

[7.6]One of the oldest known mathematical puzzles is the wolf-goat-cabbage problem. At the break of dawn, a farmer sets out for the market in a nearby village. She is accompanied by a small goat and a domesticated wolf, and she is carrying a large cabbage she hopes to sell at the market. To reach the village, the unconventional party has to cross a river using a small boat that is just large enough to carry the farmer and either the wolf, the goat, or the cabbage. For obvious reasons, the farmer cannot leave the goat alone with the cabbage or the wolf alone with the goat.

• a) Is there still a way for the whole party to cross the river unharmed?

Although it’s fairly easy to solve the wolf-goat-cabbage problem by hand, it’s even easier when modeling it using graphs. The idea, again, is to enumerate the possible states of the problem and study how they are connected by valid moves.

• b) How many different states are there? Propose a way to label them.

• c) Construct the graph that underlies the wolf-goat-cabbage problem and explain why it is symmetric. How many different solutions are there?

• d) Implement the resulting graph using the Graph interface.

[7.7]Here is another river-crossing puzzle that is similar to the wolf-goat-cabbage problem but uses different constraints on who may use the boat at a given time. It is called the jealous couples problem.

Two married couples need to cross a river. There is a small rowing boat that holds a maximum of two people. To group agrees on the following rule so that no one is getting jealous: No wife should ever be left in the presence of another man unless her husband is present as well.

• a) Is it possible for both couples to get across the river without anyone getting jealous? How many trips are necessary?

The puzzle can be extended to an arbitrary number of couples. With three jealous couples, it is still possible to cross the river, but when there are four or more couples, the problem has no solution. A popular variation of the puzzle is therefore to add an island in the middle of the stream that can be used to drop off passengers, should the need arise.

• b) Write a program that solves the jealous couples problem with an island. Your program should be able to handle at least ten couples.

• c) Use your program to study the \(n\)-couple problem with an island for \(2\le n\le 10\). For which values of \(n\) is there a solution, and how many trips are required in each case?

Measuring with Three Jugs

[7.8]Consider the following variation of the die-hard problem. There are now three jugs: two empty jugs that can hold three and five gallons, respectively, and an additional jug that is filled with eight gallons of water. (This third jug replaces the fountain in the original description of the problem.) The goal is to evenly divide the contents of the eight-gallon jug.

• a) What’s the relationship between this problem and the original die-hard problem?

• b) Assume you start with only six gallons of water in the additional jug. Sketch the graph that corresponds to this problem. How does it differ from the die-hard graph in Fig. 7.2? Is it still possible to measure four gallons in this case? Is it possible to divide the six gallons evenly? If yes, what is the most efficient way of doing so?

• c) Write a program that computes the graphs that model the three-jug problem. The structure of each graph is determined by four numbers: the capacities of the three jugs and the total amount of water distributed among the jugs. Explain how to compute the set of all nodes and the neighbors of each node.

• d) Consider the three-jug problem with 6 units of water discussed in part (b). What is the diameter of the corresponding graph? What are the most difficult water-measuring problems of this puzzle?

Hanoi Graphs

[7.9]In Exercise 3.8 we discussed the Towers of Hanoi and how to solve this puzzle using recursion. In this exercise, we translate the puzzle into a graph problem and study the resulting Hanoi graph.

The Hanoi graph \(\text {Hanoi}(n)\) is defined as the graph that corresponds to the Towers of Hanoi puzzle with \(n\) disks. There is one node for each valid configuration of the \(n\) disks, and two nodes are connected by an edge if there is a legal move that connects the corresponding disk configurations. The edges are undirected because all moves are reversible.

As we discussed in Exercise 3.8, every configuration of \(n\) disks (and therefore every node) can be described by a sequence of \(n\) letters that specifies the order in which disks are placed on the pegs A, B, and C. The node ABB corresponds to the configuration in which the largest disk is placed on peg A and the next two disks on peg B; peg C remains empty.

The first two Hanoi graphs are shown in Fig. 7.4. For \(n=1\) the graph consists of three nodes A, B, and C, and since the disk can be moved freely, there is an edge between each pair of nodes. For \(n=2\) there are nine nodes AA, AB, AC, BA, BB, BC, CA, CB, CC and a total of 12 edges between them. Nine of these 12 edges, including BA — BB, BB — BC, BC — BA, correspond to moving the small disk; the nodes that are connected by these edges differ in their last letter only. The remaining three edges AC — BC, AB — CB, and BA — CA correspond to moving the large disk, which is only possible if the small disk is out of the way.

In general, every Hanoi graph \(\text {Hanoi}(n)\) consists of three smaller Hanoi graphs \(\text {Hanoi}(n-1)\) in which only the \(n-1\) smallest disks can move while the largest disk stays fixed on one of the pegs. These three subgraphs are then joined by three edges that corresponds to moving the largest disk to a different peg. It’s easy to see that moving from one corner of the Hanoi graph to another corresponds to transferring the whole tower of disks from one peg to another.

• a) Sketch \(\text {Hanoi}(3)\). How many nodes and edges does the graph \(\text {Hanoi}(n)\) have?

• b) Write a program that computes the Hanoi graph of order \(n\).

Using Hanoi graphs, we can solve the Towers of Hanoi by using breadth-first search to find a path from a starting node such as AAA to a target node such as CCC.

• c) How efficient is breadth-first search compared to a tailor-made algorithm for solving the Towers of Hanoi such as the one we discussed in Exercise 3.8? Hint: Consider the number of nodes that are visited by both algorithms.

A path visits every node of a graph is called a Hamiltonian path, and a path that visits every node and returns to the start is a Hamiltonian cycle. It’s obvious that \(\text {A}\to {}\text {B}\to {}\text {C}\to {}\text {A}\) is a Hamiltonian cycle of \(\text {Hanoi}(1)\): the path is cyclic and contains all three nodes.

• d) Find Hamiltonian cycles in \(\text {Hanoi}(2)\) and \(\text {Hanoi}(3)\).

• e) Use induction to show that for every Hanoi graph it is possible to construct a Hamiltonian path between any two of its corners. Does every Hanoi graph also contain a Hamiltonian cycle?

Flood Fill

[7.10]Most paint programs come with a tool for filling regions of an image: The user clicks on a pixel inside the image, and the entire region connected to that pixel is filled with a new color. This operation is usually referred to as flood fill because its effect is reminiscent of color streaming out of the selected pixel and into neighboring pixels in all four directions until it is stopped by a different color. The two images in Fig. 7.5 illustrate how flood fill works. When the user clicks on one of the white pixels in the center of the maze, all white pixels that are directly or indirectly connected to it are set to a new color. Two pixels are only considered connected if they are horizontally or vertically adjacent, but not if they are diagonally adjacent.

The simplest algorithm for flood fill uses an approach similar to breadth-first search. The main data structure is a queue of pixels in the image that is initialized to the pixel clicked by the user. Each step of the algorithm removes one pixel from this queue and inspect its four direct neighbors: Every neighbor that has the same color as the current pixel (or, by extension, the starting pixel), it added to the back of the queue. We then set the current pixel to its new color and repeat the process until the queue is empty. The pixels in the queue are always on the boundary of the flooded area, which expands outwards from the initial pixel.

• a) Implement the flood fill algorithm. What happens in your implementation if the starting pixel already matches the new color?

This simple flood fill algorithm is fairly slow and consumes a lot of memory when working with large images because it has to process every pixel individually. More efficient algorithms can be obtained by processing multiple pixels at once. One such approach is based on the idea of a span, a contiguous row of pixels with the same color. Two spans are considered adjacent if any of their pixels are adjacent and have the same color.

• b) Consider the three rows of pixels shown in the following image:

  

  How many spans are there and which spans are adjacent to each other?

• c) Modify your implementation of flood fill to work with spans instead of individual pixels. Each entry in the queue represents a single span, and each step of the algorithm fills an entire span and adds neighboring spans to the back of the queue.

7.5 Chapter Notes¶

The emergence of graph theory as a mathematical discipline is closely linked to a puzzle called the seven bridges of Königsberg. In the 18th century, the city of Königsberg (now Kaliningrad) was divided by the river Pregel into four districts connected by seven bridges (Fig. 7.6). In the figure, the districts are labeled with upper-case letter A to D and the bridges with lower-case letter a to g. The question is: Is there a tour of the city that starts and ends in the same district and crosses all seven bridges exactly once?

In this particular instance, it’s not hard to try all possible routes and conclude that no such tour exists, but what about more general versions of the puzzle, with different arrangements of districts and bridges? In 1736, the German mathematician Leonard Euler proved that a cyclic tour that crosses every bridge exactly once can only exist if every district has an even number of bridges [33]. This result is considered the first major theorem in the field we now refer to as graph theory: It is known as Euler’s theorem, and a cyclic path through a graph that contains every edge exactly once is called an Eulerian cycle.

Another famous puzzle that was settled with the help of graph theory is the four color problem. The problem was first posed in the early 1850s and asks whether it is possible to color any given map in such a way that only four colors are used and no two countries with a shared border have the same color. A formal proof that this is indeed possible eluded mathematicians for more than a century and was only found in 1976 by Kenneth Appel and Wolfgang Haken [4, 5]. In their proof, Appel and Haken first reduced the infinite number of possible maps to 1834 special graphs, and then used a computer program to verify that each of these graphs is in fact 4-colorable. Appel and Haken’s proof was one of the first mathematical proofs that heavily relied on computer programming, something that irked many mathematicians at the time. To this day, no proof of the four-color theorem has been found that doesn’t require the use of computers.

In this chapter we have discussed how to model and solve several different puzzles with the help of graphs and graph algorithms. Graph algorithms are discussed in more detail in most textbooks on algorithms and data structures [86, 25]. If you are interested in the mathematical theory of graphs, the book by Benjamin et al. [14] is an excellent introduction to the subject.

For a more practical take on graph algorithms, see The Stanford GraphBase by Donald E. Knuth [63], which discusses the implementation of a wide range of graph algorithms and their applications to puzzles and other combinatorial problems. An extensive collection of algorithmic puzzles can be found in the book by Levitin and Levitin [66].

The wolf-goat-cabbage problem in Exercise 7.6 and the jealous husbands problem in Exercise 7.7 belong to the class of river-crossing puzzles in which a certain number of people or other objects must cross one or more rivers according to several constraints. River-crossing puzzles first appear in one of the earliest known collection of mathematical problems, a book called Propositiones ad Acuendos Juvenes (“Problems to Sharpen the Young”) that is believed to have been written around 800 AD [46].

Many river-crossing puzzles have a hidden structure that can be studied mathematically. For instance, it is possible to prove that the \(n\)-jealous-couples problem cannot has a solution for \(n\ge 4\) only if there is an island, and that in this case the best solution requires \(4n+1\) crossings; for details, see the article by Pressman and Singmaster [78].

The die-hard problem we discussed at the beginning of this chapter was inspired by the movie of the same name, but puzzles of this kind have a much longer history and are known as water measuring problems or decanting problems. The first written record of such puzzles can be found in the Annales Stadenses, a 13th century world chronicle written by the German monk Albert of Stade. The original version of the problem differs slightly from the one we discussed at the start of this chapter: Given a jug that contains 8 units of wine and two additional jugs that can hold 5 and 3 units, respectively, is it possible to divide the wine equally? (We discuss this three-jug problem in Exercise 7.8.)

A clever graphical method for solving this kind of problem was discovered by M. C. K. Tweedie in 1939 and later popularized by Martin Gardner [93, 39]. An illustration of this method is shown in Fig. 7.7. The main idea is to draw the die-hard graph as a parallelogram, with the four corners again representing the states in which each jug is either full or empty. When visualized like this, the shortest path from \((0,0)\) to \((4,3)\) resembles the path of a billiard ball that starts in the lower-left corner and then repeatedly bounces off the sides of the parallelogram. The method can be generalized to arbitrary two-jug and three-jug problems; for details, see the references cited above.