---
jupyter:
  description: 'The Seven Bridges of Königsberg with planex2d: a map of the river, the islands and the bridges, the
    graph read from which land each bridge reaches, Euler''s criterion for the seven bridges, and a walk over the five
    that stand at the old sites today.'
---

# The Seven Bridges of Königsberg

Is there a walk through Königsberg that crosses each of its seven bridges exactly once? The city lay on both banks of
the river Pregel and on two islands, Kneiphof and Lomse, joined to each other and to the banks by seven bridges.
Leonhard Euler showed that no such walk exists, and his argument laid the foundations of graph theory. The shape of
the map does not matter, only how many bridges each piece of land has. A walk that enters a piece of land has to leave
it again, so every piece but the first and the last needs an even number of bridges. Kneiphof had five bridges, and
each of the other three pieces had three.

The general rule is known as Euler's criterion. A connected graph has a walk that uses every edge exactly once if and
only if zero or two of its nodes have an odd number of edges. With zero, the walk ends where it started, and with two,
it runs from one of them to the other. Euler stated the rule, and Carl Hierholzer proved that the condition is
enough.

The example draws a map of the city, reads the graph from which land each bridge reaches, and checks the criterion
for the seven bridges and for the five that stand at the old sites today.

This page is part of a collection of [geometry and design examples](geometry-and-design.md) using planex2d.

<!-- #raw raw_mimetype="text/restructuredtext" -->
.. rst-class:: px-example-links

`Open this example in the playground <https://planex2d.org/playground/>`__, the interactive code editor in the browser, to change the code and run it.
<!-- #endraw -->

![A map of Königsberg with its river, the islands Kneiphof and Lomse and the seven bridges, with the graph of the
land and the bridges drawn over it](../_static/gallery/seven-bridges.png){.result}

```python
from collections import Counter

import planex as px
```

```python nbsphinx="hidden"
from docs_figures import FACE, LIGHT, Row
```

## The map

The map is a box of 120 × 70. The river comes in from the west, widens into a basin around Kneiphof and leaves to the
east in two arms, with Lomse between them. The water is the union of four rectangles, less Kneiphof, a slot 22 long
and 10 wide in the basin. The land is the box less the water, and it falls apart into four faces, the four pieces of
land (Figure 1a):

```python
box = px.QuickSketch().Rectangle(120, 70).Face()
river = px.Unify([px.QuickSketch((0, 30)).Rectangle(30, 10).Face(),
                  px.QuickSketch((26, 22)).Rectangle(32, 26).Face(),
                  px.QuickSketch((56, 42)).Rectangle(64, 6).Face(),
                  px.QuickSketch((56, 22)).Rectangle(64, 6).Face()])
kneiphof = px.QuickSketch((36, 35)).Slot(12, 10).Face()
water = river - kneiphof
land = box - water
print(len(land.faces), "pieces of land")
# px.Plot(land)
```

A point inside each piece names it:

```python
places = {"Kneiphof": (42, 35), "Lomse": (90, 35), "north bank": (60, 60), "south bank": (60, 10)}
pieces = {name: next(px.Face(f) for f in land.faces if px.Face(f).Contains(p)) for name, p in places.items()}
for name, piece in pieces.items():
    print(name, "area", piece.mass)
```

## The graph

A bridge is a rectangle across the water that reaches onto the land at both ends. `Overlaps` tells which pieces of
land it reaches, and these two pieces are the ends of its edge in the graph (Figure 1b). Two bridges each run from
Kneiphof to the north bank and to the south bank, and one each from Lomse to Kneiphof and to both banks:

```python
bridges = {"Kneiphof-north 1": ((38, 44), 3, 10), "Kneiphof-north 2": ((46, 44), 3, 10),
           "Kneiphof-south 1": ((38, 26), 3, 10), "Kneiphof-south 2": ((46, 26), 3, 10),
           "Kneiphof-Lomse": ((55.5, 35), 9, 3), "north-Lomse": ((80, 45), 3, 8), "south-Lomse": ((80, 25), 3, 8)}
spans = {name: px.QuickSketch().RectangleC(center, w, h).Face() for name, (center, w, h) in bridges.items()}
edges = {name: [p for p, piece in pieces.items() if span.Overlaps(piece)] for name, span in spans.items()}
for name, ends in edges.items():
    print(name, "joins", ends)
degree = Counter(p for ends in edges.values() for p in ends)
print("bridges per piece", dict(degree), "| odd:", sum(d % 2 for d in degree.values()))
# px.Plot(px.Compound([land, *spans.values()]))
```

```python nbsphinx="hide-input"
def bent(a, b, k):
    """the k-th of several edges between the same two pieces, bowed to one side or the other"""
    middle, normal = ((a[0] + b[0]) / 2, (a[1] + b[1]) / 2), (b[1] - a[1], a[0] - b[0])
    bow = 0.18 * k
    return px.Spline([a, (middle[0] + bow * normal[0], middle[1] + bow * normal[1]), b])


def graph(edges):
    seen = Counter()
    lines = []
    for ends in edges.values():
        pair = tuple(sorted(ends))
        k = seen[pair]
        seen[pair] += 1
        both = sum(tuple(sorted(e)) == pair for e in edges.values())
        lines.append(px.Line(places[ends[0]], places[ends[1]]) if both == 1 else bent(places[pair[0]], places[pair[1]],
                                                                                    1 if k == 0 else -1))
    return px.Compound(lines)


map_labels = [(name, p) for name, p in places.items()]
degree_labels = [(f"{name}: {degree[name]}", places[name]) for name in places]
Row((px.Compound([land, *spans.values()]), "Four pieces of land and seven bridges", {"labels": map_labels}),
    (graph(edges), "The graph: the bridges per piece", {"fill": False, "dots": list(places.values()),
                                                        "labels": degree_labels, "dashed": [land]}),
    caption="Königsberg's seven bridges and their graph")
```

All four pieces have an odd number of bridges, so by Euler's criterion no walk crosses every bridge exactly once.

## The bridges today

Two of the seven bridges did not survive the bombing of the Second World War, and two more were later replaced by a
highway at the same sites. Five bridges stand at the old sites, one from Kneiphof to each bank and the three to Lomse.
Now only the two islands have an odd number of bridges, so a walk exists, and it has to run from one island to the
other.

Hierholzer's algorithm finds it. It walks from the start over bridges not yet crossed until it gets stuck, then backs
up to the last piece of land with a bridge left and inserts the detour from there. The walk below starts on Kneiphof
(Figure 2):

```python
today = {name: ends for name, ends in edges.items() if name not in ("Kneiphof-north 2", "Kneiphof-south 2")}
degree_today = Counter(p for ends in today.values() for p in ends)
print("bridges per piece today", dict(degree_today))


def euler_walk(edges, start):
    """a walk over every edge {name: (a, b)} exactly once from start (Hierholzer), as the edges' names in order"""
    left, stack, walk = dict(edges), [(start, None)], []
    while stack:
        here, via = stack[-1]
        out = next((name for name, ends in left.items() if here in ends), None)
        if out is None:
            walk.append(via)
            stack.pop()
        else:
            a, b = left.pop(out)
            stack.append((b if a == here else a, out))
    return [name for name in reversed(walk) if name is not None]


walk = euler_walk(today, "Kneiphof")
here = "Kneiphof"
for name in walk:
    a, b = today[name]
    here = b if a == here else a
    print(name, "to", here)
print("every bridge once:", sorted(walk) == sorted(today), "| ends on", here)
# px.Plot(px.Compound([land, *[spans[name] for name in today]]))
```

```python nbsphinx="hide-input"
steps = [(str(k), bridges[name][0]) for k, name in enumerate(walk, 1)]
Row((px.Compound([land, *[spans[name] for name in today]]), "The walk over today's five bridges, in order",
     {"labels": steps}), caption="A walk from Kneiphof to Lomse over every bridge that stands today")
```

The walk ends on Lomse, the other island with an odd number of bridges. See
[Relations between shapes](../core/measuring/relations.md) for `Overlaps` and the other relations, and
[Squaring the square](squaring-the-square.md) for another graph read from a drawing.

```python nbsphinx="hidden"
import sys
import matplotlib.pyplot as plt
sys.path.insert(0, "..")
from docs_figures import INK, RED, SOFT
from gallery import save_figure

# the map in the house colors, the graph of the seven bridges over it
fig, ax = plt.subplots(figsize=(6, 4))
water.Plot(ax=ax, face_col=LIGHT, line_col=LIGHT, legend=False)
land.Plot(ax=ax, face_col=FACE, line_col=INK, legend=False)
for span in spans.values():
    span.Plot(ax=ax, face_col=SOFT, line_col=INK, legend=False)
graph(edges).Plot(ax=ax, line_col=RED, arc_col=RED, spline_col=RED, legend=False)
ax.plot(*zip(*places.values()), "o", color=RED, markersize=7, zorder=5)
ax.set_aspect("equal", adjustable="box")
ax.set_xlim(-2, 122)
ax.set_ylim(-6, 76)
ax.axis("off")
save_figure(fig, "seven-bridges", bare=True)
plt.close(fig)
```