Dark Side of the Sun

Monday, May 2, 2011

Python: Hamiltonian Cycles in a graph

This is a follow-up to this other post , where I presented a python program to find Eulerian paths in a graph (more specifically, the iconic "Bridges of Königsberg" one, although the program could easily be adapted to any other arbitrary graph).

A few weeks ago, I made a variation on that, and wrote a program to explore all possible paths in a graph, to try to find any existing Hamiltonian cycles. The purpose of this was to solve a mathematical challenge by spanish newspaper "El País".

This is the graph presented for the challenge, and solved by this program:

In a graph (a series of vertices connected by edges), the basic difference between an Eulerian path and a Hamiltonian one, is that the Eulerian path is one that walks through every edge exactly once, whereas the Hamiltonian walks through every vertex exactly once. Also, the difference between a path and a cycle is simply that the cycle ends at the same place where it started, whereas the path can start and end in two different features of the graph. So, although the problems are different, the apparent similarity is what made the adaptation of the code fairly easy. The main difference was considering the additional condition of seeing the path end where it started, for a positive result.

The solution, by the way is... that there is no solution. There are no possible Hamiltonian cycles in that graph, although there are several Hamiltonian paths (not starting/ending in the same vertex).

If anyone is interested, you can find the python code here:

hamiltonianCycle.py

This could easily be adapted for any other graph, by modifying all the "Zones" and "Bridges" declarations at the beginning of the code.

Can you think of any interesting other uses/variations for this program?