# Hamiltonian Path

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 = {}

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

def hamiltonian(self, current = None, pending = None, destiny = None):
""" Returns a list of nodes which represent
"""
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:
break
else:
if pending == []:
if current.reaches(destiny):
return [current]
else:
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
break

return result

if __name__ == '__main__':
G = Graph()