Seven Bridges to Cross
Traversing Algorithm
The algorithm for analyzing the graph is shown in the BridgeWalk
class in Listing 2. The __init__
constructor from line 3 defines three instance variables: graph
for storing the graph structure from Listing 1, a dictionary named bridges
that gets populated by the for
loop as of line 8 with keys from all bridges defined in the graph, and maxpath
, a list with the longest path found over the seven bridges during the run. Listing 1 calls the explore()
method without parameters as of line 21; the corresponding definition in Listing 2 only shows the self
placeholder as a parameter, which is common in Python classes, for the code to make object-specific calls with it later.
The for
loop from line 15 in Listing 2 iterates through all node definitions in the graph and calls the scan()
method with the number of the current node as a starting point. Since scan()
is also called recursively later when two more parameters are passed to it – the current path
as a list and a dictionary with the bridges encountered so far (seen
) – the function definition in line 18 predefines them as the empty list and the empty dictionary if they are missing, which is the case on the first call.
The two for
loops in lines 20 and 22 try all possibilities for moving from the current node to the next one and cover all directly connected nodes as well as any bridges to connect them. To see whether a bridge is walkable (i.e., make sure it has not been accessed before), the bridge_ok
method checks whether it already exists in the seen
dictionary; if it cannot find the bridge there, it picks it and marks the traversal in line 29 by setting the key in seen
to a value of 1
.
It also appends the bridge name to the path in path
. If the path is longer than the longest in maxpath
so far, line 33 stores a copy there so that the program can retrieve the longest path data later.
Isolating
When the algorithm enters a new bridge, the path continues from there, using recursion, by line 36 again calling the scan()
method, going back to line 18, but now passing the new target node from the fork as a parameter. The values for path
and seen
, passed to bridge_ok()
in line 24, provide the function with information but are also modified by it. You need to pay attention here: Parts of the code leading up to this point (the for
loops in lines 20 and 22) require the unmodified data structures, because they want to pick fresh, not already trodden, paths.
The solution to the dilemma lies in encapsulating the check in bridge_ok()
together with the .copy()
calls in line 24, which do not pass the two parameters as pointers, as is usual in Python, but as separate copies. When all possibilities are exhausted, at the end of the run, Listing 1 prints the message
['a', 'b', 'f', 'g', 'd', 'e'] Impossible!
because it could only connect six bridges. Leonhard Euler was, of course, right.
Now, if Kaliningrad were to build another bridge, h
, connecting nodes 3
and 4
parallel to bridge g
(see Figure 3), the city could offer a repetition-free tour! To prove that, we modify the graph definition in Listing 1 according to Listing 3 and run the script again:
$ ./solved.py ['a', 'b', 'd', 'e', 'c', 'g', 'h', 'f'] Solved!
Listing 3
eight-bridges
01 "3" : [["1", ["d", "e"]], 02 ["4", ["g","h"]], 03 ], 04 "4" : [["2", ["f"]], 05 ["3", ["g","h"]], 06 ["1", ["c"]] 07 ]
Figure 3 shows that an odd number of bridges is attached to only two of the four nodes, thus fulfilling Euler's requirement. The corresponding change in the data structure shown in Listing 3 builds a bridge h
between nodes 3
and 4
and, as the output above shows, solves the problem with the same algorithm – something for the Kaliningrad city fathers to consider, for sure.
Infos
- Seven Bridges of Königsberg: https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
- Listings for this article: ftp://ftp.linux-magazine.com/pub/listings/linux-magazine.com/217/
« Previous 1 2
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Direct Download
Read full article as PDF:
Price $2.95
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Find SysAdmin Jobs
News
-
Escuelas Linux 8.0 is Now Available
Just in time for its 25th anniversary, the developers of Escuelas Linux have released the latest version.
-
LibreOffice 7.5 has Arrived Loaded with New Features and Improvements
The favorite office suite of the Linux community has a new release that includes some visual refreshing and new features across all modules.
-
The Next Major Release of Elementary OS Has Arrived
It's been over a year since the developers of elementary OS released version 6.1 (Jólnir) but they've finally made their latest release (Horus) available with a renewed focus on the user.
-
KDE Plasma 5.27 Beta Is Ready for Testing
The latest beta iteration of the KDE Plasma desktop is now available and includes some important additions and fixes.
-
Netrunner OS 23 Is Now Available
The latest version of this Linux distribution is now based on Debian Bullseye and is ready for installation and finally hits the KDE 5.20 branch of the desktop.
-
New Linux Distribution Built for Gamers
With a Gnome desktop that offers different layouts and a custom kernel, PikaOS is a great option for gamers of all types.
-
System76 Beefs Up Popular Pangolin Laptop
The darling of open-source-powered laptops and desktops will soon drop a new AMD Ryzen 7-powered version of their popular Pangolin laptop.
-
Nobara Project Is a Modified Version of Fedora with User-Friendly Fixes
If you're looking for a version of Fedora that includes third-party and proprietary packages, look no further than the Nobara Project.
-
Gnome 44 Now Has a Release Date
Gnome 44 will be officially released on March 22, 2023.
-
Nitrux 2.6 Available with Kernel 6.1 and a Major Change
The developers of Nitrux have officially released version 2.6 of their Linux distribution with plenty of new features to excite users.