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
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
-
TUXEDO Computers Unveils Linux Laptop Featuring AMD Ryzen CPU
This latest release is the first laptop to include the new CPU from Ryzen and Linux preinstalled.
-
XZ Gets the All-Clear
The back door xz vulnerability has been officially reverted for Fedora 40 and versions 38 and 39 were never affected.
-
Canonical Collaborates with Qualcomm on New Venture
This new joint effort is geared toward bringing Ubuntu and Ubuntu Core to Qualcomm-powered devices.
-
Kodi 21.0 Open-Source Entertainment Hub Released
After a year of development, the award-winning Kodi cross-platform, media center software is now available with many new additions and improvements.
-
Linux Usage Increases in Two Key Areas
If market share is your thing, you'll be happy to know that Linux is on the rise in two areas that, if they keep climbing, could have serious meaning for Linux's future.
-
Vulnerability Discovered in xz Libraries
An urgent alert for Fedora 40 has been posted and users should pay attention.
-
Canonical Bumps LTS Support to 12 years
If you're worried that your Ubuntu LTS release won't be supported long enough to last, Canonical has a surprise for you in the form of 12 years of security coverage.
-
Fedora 40 Beta Released Soon
With the official release of Fedora 40 coming in April, it's almost time to download the beta and see what's new.
-
New Pentesting Distribution to Compete with Kali Linux
SnoopGod is now available for your testing needs
-
Juno Computers Launches Another Linux Laptop
If you're looking for a powerhouse laptop that runs Ubuntu, the Juno Computers Neptune 17 v6 should be on your radar.