Hamiltonian Cycle

Written by Vincent Bruijn

Visiting the Gemeente Museum Den Haag I came across a painting I knew already for quite a while, and which I like very much, but now it triggered something. Looking at Vilmos Huszár‘s painting Compositie II (schaatsenrijders) from 1917, I saw, although being sober, the ice skaters move from spot to spot on the painting. I thought: wouldn’t it be great to animate this?

Vilmos Huszar

The next question was: how then to animate the painting… A bit of research led me to the Wikipedia page of the Hamiltonian Path, quote: “a path in an undirected or directed graph that visits each vertex exactly once.” That is exactly what this painting was: an undirected graph.

Graph of the painting

Let us assume you have the painting on a post card. You put a sheet of semi-transparent paper on top, and for each ice skater you add one dot to the sheet of paper. Now you have a graph. I wanted to let each ice skater to move to another spot on the graph, but one important addition is that I wanted each cycle of movements to be complete, and connected. This means that all ice skaters would make a natural move to one of their closest neighboring spots.

var hashtable = [
    [0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1],
    [1,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0],
    [1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,1,1,0,1,0,0,0,0,0,0,0,1,0,0,0],
    [0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0],
    [0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0],
    [0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0],
    [0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0],
    [0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,1],
    [0,0,0,0,0,0,1,1,1,1,0,1,0,1,1,0],
    [0,0,0,0,0,1,1,1,0,0,1,0,1,1,0,0],
    [0,1,0,1,1,1,0,0,0,0,0,1,0,1,0,0],
    [1,1,0,0,0,0,0,0,0,0,1,1,1,0,1,0],
    [1,0,0,0,0,0,0,0,0,1,1,0,0,1,0,1],
    [1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0]
];

Knowing only so much of maths to understand more or less the ins and outs of the Hamiltonian Cycle, I came across a piece of Java code on Stackoverflow which uses a recursive method on a graph to find all Hamiltonian Cycles. I rewrote this into JavaScript and defined the graph in a matrix. After running the code using node, it happened to find 1376 paths for my defined graph. That’s nice! The first implementation I made was completely client side. This was not a good idea because:

  • why recalculate all 1376 paths for each visitor?
  • what if someone visits the site with IE9? The script will take so damn long that IE9 will complain about it…

The only up side to this is that it showed which browsers do have nice JavaScript performance, but that was of no importance here. So I ended up calculating all cycles once and add them to the script. This doesn’t mean the JavaScript implementation of Stackoverflow is lost: you can still find it on my GitHub.

Tweaking the code to get better performance is the next thing on my list. The animation runs quite smooth in Google Chrome, but on Safari Mobile or IE browsers, it might get messed up. There, the animation looks more like spreading a couple of skaters on a canvas every second, which is not wat I was aiming for. After having removed the jank, you might expect me to write a follow up on that.