Previous page Next page Navigation bar

Puzzles

In memoriam: Edsger W. Dijkstra

The Computational Plan, part 2

Now we need to figure out how to determine whether a given subset of bridges leaves the two shores connected. You may recall we interpreted this as determining whether there is a path from one shore to the other shore, where the path goes from a location over a remaining bridge to another location, and from that location over a remaining bridge to yet another location, and so forth. Now, in addition to telling bridges apart, we need to tell locations apart.

We call the two shores location 1 and location 2, and we number the islands with 3 through 8. Our map now looks like this:

Map of shores, islands, and bridges with locations numbered

Also, because where we can get to depends on which bridges in particular remain or are removed, it makes a difference which bridge is which. So we assign numbers to the bridges as well. Now our map is as follows:

Map of shores, islands, and bridges with locations and bridges numbered

Obviously, if the two shores are connected, then there is a path from the top shore, location 1, to the bottom shore, location 2. Similarly, if there is a path from location 1 to location 2, then there is a path from location 2 to location 1, and the shores are connected. So, then, the question of the shores being connected is equivalent to the question of whether there is a path from location 1 to location 2.

We can apply the trick of the trade about generating possibilities here, also. We consider the set of locations we can reach from location 1. Clearly, we can reach location 1 from location 1: this is the first of the sets of possibilities. Now we consider each of the bridges in turn: if it connects a location we know we can reach to a location we do not know we can reach, then we have discovered a new place we can reach. And, finally, if no bridge reaches from a location we know we can reach to a location we do not know we can reach, we are done: we have determined the set of the locations we can reach from location 1. If location 2 is in that set, then the shores are connected; if location 2 is not in that set, the shores are not connected.

a merry-go-round

Mathematical Amusements (a diversion)

In general, this process is called computing the closure of a set under a relation. In this instance, we are computing the closure of location 1 under connectedness.

If A and B are sets, then a relation R may hold between some elements of A and B. If the relationship holds between elements a of A and b of B, we write aRb. For example, the relationship “less than” (“<”)is defined on the natural numbers and the natural numbers; we write a < b if a is less than b. The relationship R may equivalently be defined as a subset of A×B: R = {(a, b) : aA, bB, aRb}.

We can use matrix algebra to compute closures. Let A be a set, and R be a relation on that set and itself. Let E0 = (e0,1, e0,2, ..., e0,n)T indicate an initial subset of A: e0,i is 1 if ai is in the initial subset, and 0 otherwise. Let B = (bi,j) be the incidence matrix of the relation R: bi,j = 1 if aiRaj and 0 otherwise. Now compute the matrix Ek+1 = BTEk using the following boolean operations:

+01   ×01
001   000
111   101

E1 then indicates the subset of A related to the initial subset E0; E2, the subset related to E1; and so forth. The limit of the sequence {Ek}, if it exists (and it does for finite n), is the closure of A under R.

As an example, consider a set of surviving bridges, as follows:

Map of shores, islands, and bridges

We indicate the locations we know we can reach by coloring them burgundy; initially, we know we can reach location 1, the top shore, as follows:

Map of shores, islands, and bridges

Now we color bridges leading us to places we do not yet know we can reach as blue, and color the newly known places we can reach burgundy; we do this four times, as follows:

Map of shores, islands, and bridges Map of shores, islands, and bridges Map of shores, islands, and bridges Map of shores, islands, and bridges

And we see that with this combination of bridges, we can indeed reach location 2, the other shore, and the shores are connected. This combination of bridges would be counted towards the total of combinations leaving the shores connected.

Consider a second combination of bridges, and the progression through the discovery of the reachable locations:

Map of shores, islands, and bridges Map of shores, islands, and bridges Map of shores, islands, and bridges Map of shores, islands, and bridges Map of shores, islands, and bridges

We see this combination of bridges disconnects the two shores, and this combination of bridges would not be counted towards the total.

There are several ways we could program figuring what locations we can reach, given a collection of surviving bridges. We will use the following Trick of the Trade:

a magician showing a card trick

Tricks of the Trade

A graph is a set of vertices and a set of edges where each edge connects two distinct vertices. (This sounds an awful lot like locations and bridges.) A common way of representing an edge of a graph is as a set of the two edges it connects: so if vi and vj are vertices, {vi, vj} would be an edge connecting them.

Sets are unordered, so the set {vi, vj} is the same as the set {vj, vi}.

A multigraph extends a graph in two ways: it permits multiple edges to connect the same two vertices, and it lets a vertex connect to itself. A directed graph extends a graph by letting the edges be ordered pairs, rather than sets: an edge (vi, vj) connects vertex vi to vertex vj, but not vice-versa. A directed graph would be useful for modeling a set of roads that included one-way streets.

Bridge 1, for example, connects location 1 and 3; so we associate the set {1,3} with bridge 1. Similarly, we associated {1,4} with bridge 2, {1,5} with bridge 3, {3,4} with bridge 4, and so on. For each bridge, we will store in a list the pair of locations it connects. Each element of a list can store only one value, though; how will we do this? We use another trick of the trade:

a magician showing a card trick

Tricks of the Trade

A single variable can hold several values, if the values to be held are small enough. Remember from elementary arithmetic that the result of a division of one positive integer by another, a÷b, is an non-negative integer quotient q and a non-negative integer remainder r. Also, the remainder r is in the range 0 to b-1.

Suppose we have two non-negative values, x and y, to store, and we know the value x is never as large as some value m. Then we can combine x and y as my + x; and from this, we can recover the individual values x and y. We recover the values by dividing by m: the value of y is the quotient, and the value of x is the remainder. We can repeat this to hold as many values as desired: the value y may be a combined value as well, and so forth. If we have several values x1, x2, ..., xk to store, which never reach value m1, m2, ..., mk, the range of the combined value is between 0 and m1m2...mk.

Note that the value m must exceed the maximum possible value for x.

We will represent the set {a, b}, and hence the edge from location a to location b, by the value 1000a + b: {1,3}, for example, would appear as 1003. We can easily recover the individual values by taking the integer portion of the quotient after dividing the combined value by 1000, and the remainder after dividing the value by 1000.

Is there anything more to plan? Apparently not; time to code, then!

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
Page last updated 10 April 2006.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

In memoriam: Dijkstra

Introduction

Interpretation

Plan, part 1

Plan, part 2

Code

Extension 1

Extension 2

Final Modification

Bridge Collections

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data