Hacks, science and curiosities

Hamiltonian Path

– 🕓 2 min read

Yesterday at midnight was the deadline of El PaĆ­s math challenge which consisted in finding the Hamiltonian path of a given graph (or to give a demonstration it hadn't any as it was the case).

A friend of mine told me a simple and elegant demonstration based on graph coloration, which is the one explained in the video (the video is in Spanish but it's my bet there are more demonstrations like this in English on the internet).

If you can understand Spanish, I encourage you to watch the video. It's really short, entertaining and easy to understand.

This tiny python program finds a Hamiltonian path for a given graph and prints the solution (or None if it doesn't exist, as it happens in this math challenge).

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# vim:ts=4:et:sw=4

class Vertex(object):
    def __init__(self, node, *nodeList):
        self.i = node
        self.nodeList = list(nodeList)

    def __hash__(self):
        return self.i

    def reaches(self, vertex):
        """ Can receive an integer or a Vertex
        if isinstance(vertex, int):
            return vertex in self.nodeList

        return self.reaches(vertex.i)

    def __str__(self):
        return '< ' + str(self.i) + '>'

    def __repr__(self):
        return self.__str__()

class Graph(object):
    def __init__(self):
        self.vList = {}

    def add(self, node, *nodeList):
        vertex = Vertex(node, *nodeList)
        self.vList[node] = vertex

    def hamiltonian(self, current = None, pending = None, destiny = None):
        """ Returns a list of nodes which represent
        a hamiltonian path, or None if not found
        if pending is None:
            pending = self.vList.values()

        result = None

        if current is None:
            for current in pending:
                result = self.hamiltonian(current, [x for x in pending if x is not current], current)
                if result is not None:
            if pending == []: 
                if current.reaches(destiny):
                    return [current]
                    return None

            for x in [self.vList[v] for v in current.nodeList]:
                if x in pending:
                    result = self.hamiltonian(x, [y for y in pending if y is not x], destiny)
                    if result is not None:
                        result = [current] + result

        return result

if __name__ == '__main__':
    G = Graph() 
    G.add(1, 2, 8, 11)
    G.add(2, 1, 6, 9)
    G.add(3, 6, 7, 9, 10)
    G.add(4, 5, 7, 10)
    G.add(5, 4, 8, 11)
    G.add(6, 2, 3, 8)
    G.add(7, 3, 4, 8)
    G.add(8, 1, 6, 7, 5)
    G.add(9, 2, 3, 11)
    G.add(10, 3, 4, 11)
    G.add(11, 1, 9, 10, 5)
    print G.hamiltonian()