Seven Bridges to Cross
Programming Snapshot – Graph Theory
Pretty much any computer science lecture about graph theory covers the "Seven Bridges of Königsberg" problem. Mike Schilli puts a Python script to work on a solution, but finds that a new bridge must be built.
The task of crossing the seven bridges over the Pregola River on a city tour of Königsberg (nowadays known as Kaliningrad) without missing one or walking across one twice [1] is simply captivating.
The Swiss mathematician Leonhard Euler already proved that this was impossible as early as 1736, but the task is still useful as a mathematical brain teaser today because the network of bridges can be converted into a graph (Figure 1) and bombarded with graphtheory axioms and algorithms.
Euler found that Königsberg's land masses can be represented as nodes in a graph, connected by seven paths – referred to as edges by graph theorists – that represent the connecting bridges (a
to g
in Figure 2). The task for the Königsberg city guide is therefore to cover all the edges drawn in the graph without passing a segment more than once.
Leonhard Euler recognized that the number of edges leading to a node (he called it "degree" of the node) directly determines whether or not the problem of a repetitionfree walkthrough can be solved.
Odd or Even
If each node has an even number of edges, a tourist can walk across all the bridges in sequence without ever getting stuck. A similar situation occurs if exactly two of the nodes in the graph have an odd number of access points and the remaining nodes have an even number – in this case, the walker starts walking at the first of the odd nodes and ends the walk at the second odd node. In all other cases, for example also in the present Königsberg bridge problem, where all four nodes exhibit odd degrees, a repetitionfree round trip is mathematically impossible.
Brute Force
For fun, you could now tackle the problem with a Python script that marches through the graph and only stops if it cannot continue at a node, because all adjacent segments have already been traversed. If a following check shows that the trip has covered all segments of the graph, the result is the correct solution to the problem. In the case of Königsberg, this is not possible. However, as we'll see later, if you add another connection to the graph, there is a way.
For the script to try all possible path combinations, a recursive depthfirst algorithm works through the different bridge combinations. On the journey, it keeps track of the crossed bridges in a dictionary and does not take a route that leads over a bridge that previously has been passed.
If it gets stuck on a node, it resets and tries further combinations of previously chosen directions at branches. It stores the longest path found so far in an object attribute for later reference. If its length later matches the number of all defined bridges, the script has solved the problem.
Inserting the Graph
As a first task, the script in Listing 1 [2] models the graph from Figure 2 in the data structure starting on line 4. Node names ("1"
, "2"
, etc.) are used as keys into the dictionary, whose values consist of lists of connected nodes along with a list of path options, for example ["a", "b"]
in the first entry, because bridges a
and b
lead from node 1
to node 2
.
Listing 1
koenigsberg.py
01 #!/usr/bin/env python3 02 from bridgewalk import BridgeWalk 03 04 g = { "1" : [["2", ["a", "b"]], 05 ["3", ["d", "e"]], 06 ["4", ["c"]] 07 ], 08 "2" : [["1", ["a", "b"]], 09 ["4", ["f"]] 10 ], 11 "3" : [["1", ["d", "e"]], 12 ["4", ["g"]], 13 ], 14 "4" : [["2", ["f"]], 15 ["3", ["g"]], 16 ["1", ["c"]] 17 ] 18 } 19 20 trail = BridgeWalk(g) 21 trail.explore() 22 23 print(trail.maxpath) 24 25 if len(trail.bridges) == \ 26 len(trail.maxpath): 27 print("Solved!") 28 else: 29 print("Impossible!")
This puzzle's definition gets passed to the BridgeWalk
class' constructor in line 20; the class itself is defined further down in Listing 2. The explore()
method on the resulting object then shimmies through the graph to find the longest path without an overlap.
Listing 2
bridgewalk.py
01 #!/usr/bin/env python3 02 class BridgeWalk(object): 03 def __init__(self, graph): 04 self.graph = graph 05 self.bridges = {} 06 self.maxpath = [] 07 08 for node in self.graph: 09 for fork in self.graph[node]: 10 for bridge in fork[1]: 11 self.bridges[bridge] = 1 12 13 def explore(self): 14 # try different start nodes 15 for node in self.graph: 16 self.scan(node) 17 18 def scan(self, node, path=[], seen={}): 19 # try different connected nodes 20 for fork in self.graph[node]: 21 # try all bridges leading there 22 for bridge in fork[1]: 23 self.bridge_ok(bridge, fork[0], 24 path.copy(), seen.copy()) 25 26 def bridge_ok(self, bridge, 27 node, path, seen): 28 if not bridge in seen: 29 seen[bridge]=1 30 path.append(bridge) 31 32 if len(self.maxpath) < len(path): 33 self.maxpath = path.copy() 34 35 # recurse 36 self.scan(node, path, seen)
At any point in time during the run, the maxpath
object attribute contains a list of bridges in the order they were crossed. The print()
statement in line 23 in Listing 1 automatically converts the list into a string and outputs it. The bridges
attribute maintains a dictionary with the keys for all bridges defined in the graph for easy counting of unique bridges.
If the number of bridges in the graph determined with len()
matches the number of bridges on the longest path in maxpath
, the script in line 27 reports the successful solution of the puzzle.
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you've found an article to be beneficial.
News

elementary OS 7.1 is Now Available for Download
The team behind elementary OS has released the latest version of its operating system with a focus on personalization, inclusivity, accessibility, and privacy.

The GNU Project Celebrates Its 40th Birthday
September 27 marks the 40th anniversary of the GNU Project, and it was celebrated with a hacker meeting in Biel/Bienne, Switzerland.

Linux Kernel Reducing LongTerm Support
LTS support for the Linux kernel is about to undergo some serious changes that will have a considerable impact on the future.

Fedora 39 Beta Now Available for Testing
For fans and users of Fedora Linux, the first beta of release 39 is now available, which is a minor upgrade but does include GNOME 45.

Fedora Linux 40 to Drop X11 for KDE Plasma
When Fedora 40 arrives in 2024, there will be a few big changes coming, especially for the KDE Plasma option.

RealTime Ubuntu Available in AWS Marketplace
Anyone looking for a Linux distribution for realtime processing could do a whole lot worse than RealTime Ubuntu.

KSMBD Finally Reaches a Stable State
For those who've been looking forward to the first release of KSMBD, after two years it's no longer considered experimental.

Nitrux 3.0.0 Has Been Released
The latest version of Nitrux brings plenty of innovation and fresh apps to the table.

Linux From Scratch 12.0 Now Available
If you're looking to roll your own Linux distribution, the latest version of Linux From Scratch is now available with plenty of updates.

Linux Kernel 6.5 Has Been Released
The newest Linux kernel, version 6.5, now includes initial support for two very exciting features.