The Bristol Bridge Problem

IMG_20200616_064914978

[Written as part of Notebook Blog Month.]

Last year I walked the Bristol Bridge Walk with my brother. This is a 28 mile circuit in the style of Königsberg’s famous bridge problem, where every bridge in Bristol (or more accurately, every footbridge across the Avon) has to be crossed exactly once. It was designed by Thilo Gross, who figured out that Bristol’s bridge problem can be solved, unlike Königsberg’s. At least until they build more bridges and mess it up.

I wrote a Twitter thread on this a while back but thought I’d try an expanded version here. The interesting bit for me is how much of Gross’s work in creating this route was in defining the problem, mapping all the mess of modern Bristol onto a clean mathematical model.

The original Königsberg bridge problem has the following structure, with four land masses and seven bridges:

IMG_20200616_065357229

Euler worked out that it wasn’t possible to cross each bridge exactly once. The solution is simple and short enough that I may as well reproduce it here. He found a clever reframing of the problem, where the four land masses become nodes of a graph, and the seven bridges become edges between them:

IMG_20200616_065341923

Now, ignore the start and end of the walk for a minute. For the rest of the time, every time you enter a land mass by a bridge, you also leave by a bridge. So if every bridge has been crossed exactly once, then for any node of the graph apart from the start and end ones, there must be an even number of edges coming out of it.

Now this can’t possibly work for Königsberg, because all four nodes have three edges coming out of them, and you can only get away with having the two start and end nodes with odd numbers of edges. So the problem is insoluble.

Bristol has a similar overall structure to Königsberg, so the problem maps over quite nicely. There’s one main river, the Avon, with two islands in the middle of it: Spike Island and Redcliffe. Here’s a map:

bristol_map

So there are four nodes. But modern Bristol has a whole lot more bridges. 45 in fact. (Or maybe 47 now. The two new arena bridges were closed when I did the walk. They don’t change anything though, you just cross one and immediately cross back on the other.) Here’s the graph:

IMG_20200616_072002529

A is the north bank, B is the south, C is Spike Island and D is Redcliffe. There are so many bridges between Redcliffe and the two banks that I just wrote the numbers instead of drawing each edge. There are also several internal bridges linking the north bank to itself, for reasons I’ll get to.

(I came up with that graph myself, and it might not exactly match Gross’s. I tried to construct it to match his descriptions, but there might be some edge cases I counted slightly differently to him.)

Ignoring the internal edges linking A to A (which can be removed), all nodes have an even number of edges. A has 20 without the internal edges, B has 18, C has 12 and D has 26. So it’s a soluble problem.

Now, coming up with that graph was a good deal more complicated than just counting bridges. This is the bit I find interesting as an example of problem formation, mapping complicated stuff in the real world onto a clean mathematical model with an unambiguous technical solution. Gross explains all the work he had to do to figure out the scope of the problem, and what should actually count as a bridge:

It required about three solid days of work spread over a fortnight. Two thirds of the time was spent just finding out where all the bridges were, and what was to count as a bridge and what not. Only bridges that are walkable are included and a judgement had to be made about some smaller bridges (not comparable in size to Königsberg’s bridges) on tributaries of the Avon that would have led the resulting walk long distances through some dull areas. Some bridges comprise two separate structures of segregated traffic and are counted as two.

It turns out that Bristol is like Königsberg on the large scale, but when it comes to the details there are a whole bunch of judgement calls. These generally have a reasonable, common-sense resolution, so the resulting solution doesn’t feel arbitrary, but it does mean that solving the problem is not just a quick matter of drawing some nodes and edges. I’ll go through a load of these below.

First up, Gross needed to decide what counts as a bridge. This is purpose-dependent: rail- and car-only bridges don’t count in this solution because the whole point is to be able to walk it.

Next, it’s not exactly true that there are four nodes. If you look closely at the map, there are two little islets off of Spike Island:

islets

The left islet is kind of complicated, and worth looking at on a satellite view:

small_bridges

The two bottom footbridges linking the islet to Spike Island are genuine public bridges over the Avon and should definitely be included. The two top ones are little lock gate thingies. I don’t think they’re reliably walkable, and they probably shouldn’t count. So it’s a reasonable choice to ignore them and count the islet as part of the north bank node for the purposes of this graph.

The right islet is simpler: one bridge on, one bridge off. It kind of doesn’t matter much what you do with it – it could be counted separately (in which case it’s a new node with two edges), or shoved in with either the north bank or Spike Island. Gross went for the second option, preserving the similarity with Königsberg. Then the south bridge gets counted as the bridge between the north bank and Spike Island, and the second one gets counted as an internal bridge linking the north bank to itself. (At least that’s what I did. Not sure exactly how Gross formalised it.)

Also, there are a couple of minor rivers emptying into the Avon. There’s the Trym:

trym

In a sense this cuts the north bank into two: west of the Trym and east of the Trym. Should these be two nodes? And should you have to traverse all the bridges along the Trym as well, right out into the suburbs of Bristol?

Gross goes with no. It’s a small river and is just not a big deal: I don’t think that which side of the Trym you’re on is part of many people’s mental geography in Bristol, in the way that ‘north of the Avon’ (or ‘east of the motorway’) would be. (While walking this we crossed it without noticing, and had to go back to get a photo of the bridge.) Also walking to the outer suburbs and back would be a big hassle and make an already long walk really tedious. So both sides of the Trym are the same node, and the bridges over the Trym that do get crossed as part of this walk are internal bridges linking the north bank to itself.

There’s a similar argument for the Frome:

frome

This one’s easier, actually, because it’s mostly culverted in the centre and doesn’t really divide up Bristol at all. There are a couple of smaller rivers in the south, the Malago (also culverted) and Brislington Brook (tiny) which are even easier to rule out.

So we’re settled on four nodes. Now for the edges. This is mostly more straightforward, but even here there are special cases:

double_bridge

Is a bridge like this two bridges or one bridge? The aerial photo makes them look very much like one bridge, as you can see the whole intersection, but as a pedestrian they feel more like two. It doesn’t matter too much, but it would be annoying if the rule was inconsistent in different places. In this case they all get counted as two.

One last decision. There’s a single ‘outlier bridge’ in Bristol, the motorway bridge at Avonmouth. Here’s a map of the whole route area:

avonmouth_st_annes

This bridge does have a footbridge, so it ought to count. But it’s way out in the west, miles down from the next bridge, the Clifton Suspension Bridge. It adds maybe a third of the route just on its own. It would be a reasonable decision to leave it out, but also annoying, because it’s such a big important bridge and the walk wouldn’t feel complete. So it’s kept in. This actually works out quite well, because one of the nicest parts of the walk is the path through Leigh Woods on the way back from Avonmouth.

So… is the Bristol Bridge Problem soluble? It is, in the sense that you can make reasonable arguments for dividing Bristol up into nodes and edges in a way that gives you a soluble problem. It isn’t, in the sense that you could probably make different reasonable arguments for dividing it up in a different way that doesn’t. (It’s fairly robust to small changes, but if you dropped the Avonmouth outlier and counted the double bridges as single ones you could maybe get something that isn’t soluble). In the end the arguments for it being soluble were all good enough that I was happy to go along with them for the sake of an interesting walk. It’s soluble enough for my purposes.

I really like this as a demonstration of the work of problem formation. It’s easy to understand without a specific technical background: the mathematical model is a simple graph, and the decisions about how to map Bristol on to it are all easy-to-understand common sense sorts of decisions. But it’s still not a trivial toy problem you’d find in a textbook. Gross had to put days of work into finding a good formalisation, and the decisions are genuinely hard to call without being completely arbitrary. It’s a great example of mapping between a technical problem and the mess of the world.

4 thoughts on “The Bristol Bridge Problem

  1. Bunthut August 9, 2020 / 11:29 pm

    >I really like this as a demonstration of the work of problem formation.

    I think it’s rather atypical. In the Bristol bride problem, your goal originally comes from the map: The whole thing is conceived because the map you’re using has elements called “bridges”. The challenge is to make this notion precise in a way that intuitively seems faithful to “bride” and works with practical considerations.

    But if my goal were for example to not be hungry, there is an additional consideration: even if I think I’ve been faithful to the concept of hunger, and I dont have practical difficulties avoiding that, there’s the possibility that my lizardbrain will break in and tell me that actually I’m still hungry. By contrast with the bristol bridges, once you have convinced yourself that your representation is faithful, the only resistance you can encounter is in practically achieving that representation – it can’t turn out to have been the wrong representation. Most problems I think are closer to the hunger example – notice how the bristol bridges were invented as a problem to illustrate mathematics, rather than because some *actually had* a problem.

    Like

    • Lucy Keer August 14, 2020 / 6:13 pm

      Hmm… not sure whether I agree or not. Maybe I don’t understand your argument very well? I was thinking of the Bristol Bridge Problem as an example of fitting real life to a formal system, like a mathematical model or some business rules in a computer application. Your hunger example is not of this type: you’ll solve it by some common-sense method like buying and eating a burger, rather than mapping it to some formal system. I’m not really sure what you mean by being ‘faithful to the concept of hunger’ when there’s no mapping involved?

      But it’s true that it’s a fairly contrived example where nobody really *needs* to solve the problem. You could compare that to say the rules of, I dunno, an emergency call routing system, where a bad mapping will kill people. Otoh it isn’t arbitrary either? If you define some piddling irrelevant crossing over the Trym as ‘a bridge’, and the Clifton Suspension Bridge (the most famous bridge in Bristol) as ‘not a bridge’, then it would be a completely stupid walk. If I walked 28 miles on a ‘bridge walk’ round Bristol without crossing Brunel’s bridge my lizard brain would definitely have some complaints!

      To me it does seem to share a lot of properties with harder real-life questions I’ve come across in software development, where there are multiple compelling ways to map the domain to a set of rules. E.g. I worked on software for reporting car crashes and we’d get requests for changes to various dropdowns… exciting stuff like road classifications. Do motorway sections of A roads (https://en.wikipedia.org/wiki/Great_Britain_road_numbering_scheme#Motorway_sections) count as motorways or their own thing? Answering this is higher stakes than the bridge problem but there’s still an arbitrary element to it.

      Like

      • Bunthut August 20, 2020 / 2:30 pm

        >Maybe I don’t understand your argument very well?

        I’m thinking about where you can encounter resistance from reality. We can split up the task into two parts: Connecting (some of) the formal concepts to real things, and solving the formal problem. Now with each of those parts, consider: If you believe you’ve succeeded, can you still run into problems? For solving the formal problem, the answer is yes in either case. Just because you believe your walk crosses every bridge once, you can still find out it doesn’t (if you mark them after passing for example). But not with the connecting part. If you think that something doesnt count as a bridge, then your walk will never make you realize that it actually was one.

        By contrast, if I correctly predict my physical state after eating a salad, but incorrectly identify that state as “not hungry”, then when I actually get to that state, I will know that I was wrong. Maybe hunger was a bad example, because as you say it’s usually not solved systematically (though you can), but I picked it because it illustrates the resistance from reality especially well.

        For a maybe better example, imagine you’re engineering a motor. One of the requirements is that the motor actually works at all. Now you can try to assign states of the motor to “works” and “doesnt work”, and then solve the formal problem of making a motor that “works”. But even if you succeed and the motor really is in a state you assigned “works”, you might realize after trying to use it that it actually doesn’t work.

        This doesnt mean that you could call just anything a bridge and be satisfied. You do have to *believe* its a bridge, and you can’t easily make yourself for arbitrary things. But if you do believe it, theres no further issue. In “normal” problems there can be.

        >Do motorway sections of A roads count as motorways or their own thing? Answering this is higher stakes than the bridge problem but there’s still an arbitrary element to it.

        Well, I don’t know the background here, but I do think this could fit into the hunger paradigm. Repeatedly ask “What will this classification be used for? What is its purpose?” and see if you get to something that obviously gives resistance. In this case, it might be something about preventing accidents or calculating insurance rates. And then you can consider which ways of classifying best work towards that goal, and here you can again encounter resistance.

        Of course, it might also be that there is no purpose, and the metrics were created just so some manager could say “Hey, we have metrics, I’m doing something”. In that case its more like the bridges. There is a difference in that now what matters isnt whether *you* think it looks like “real metrics”, but what whoever he wants to show it to thinks, but given the relative similarity in culture you will propably solve it in the same introspective way.

        Really this is also a good way to tell the difference. Does a categorisation have some real-world purpose, or is it only there for someone to think it’s an adequately categorised? The first being the hunger-type, and the second the bridge-type.

        This is important because conclusions like

        >So… is the Bristol Bridge Problem soluble? It is, in the sense that you can make reasonable arguments for dividing Bristol up into nodes and edges in a way that gives you a soluble problem. It isn’t, in the sense that you could probably make different reasonable arguments for dividing it up in a different way that doesn’t.

        do not go over well with hunger-type problems.

        Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s