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!
Figure 3: The path h reduces the number of odd nodes to two and paves the way to a solution.

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.

The Author

Mike Schilli works as a software engineer in the San Francisco Bay area, California. Each month in his column, which has been running since 1997, he researches practical applications of various programming languages. If you email him at mailto:mschilli@perlmeister.com he will gladly answer any questions.

Buy this article as PDF

Express-Checkout as PDF
Price $2.95
(incl. VAT)

Buy Linux Magazine

SINGLE ISSUES
 
SUBSCRIPTIONS
 
TABLET & SMARTPHONE APPS
Get it on Google Play

US / Canada

Get it on Google Play

UK / Australia

Related content

  • Bridgewall

    Firewalls are typically implemented as routers,but it doesn’t have to be that way. Bridging packet filters have a number of advantages,and you can add them to your network at a later stage without changing the configuration of your network components.

  • Perl: Neo4j

    The Neo4j graph database is much better suited than relational databases for storing and quickly querying nodes and their mutual relationships. If your circle of friends is not wide enough to warrant a graph-based application, you might just want to inventory your LAN.

  • systemd-networkd

    The new networkd component of the systemd project supports basic network configuration. Despite its early stage of development, one thing is clear: This is a daemon with brains.

  • Trembling Text

    Writing your own extension for Inkscape opens up a whole world of possibilities. Apart from creating new objects, you can modify existing objects and even animate them.

  • Graphviz

    Using drawing tools to manually create graphs and diagrams can be a slow and convoluted process. The Graphviz toolbox offers a faster way. Based on a short text with the information for the graph, Graphviz quickly generates a neat drawing.

comments powered by Disqus

Direct Download

Read full article as PDF:

Price $2.95

News