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)