Hamiltonian path generator

Author: Nathan Clisby, November 2014 (homepage, clisby@gmail.com). Link to an earlier version. Note: both the implementation of the algorithm and the appearance have been changed.

About: This javascript program generates a Hamiltonian path on an n × n grid using the backbite move described in the paper “Secondary structures in long compact polymers” by Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen and Jané Kondev, Phys. Rev. E 74, 051801 (2006). Paper available via the APS (subscription required) or as a pre-print on the arXiv. The resulting path is displayed below both as an image and as a sequence of grid points. (Further technical details at the bottom of the page.)

Initialisation: Specify desired grid size and choose “quality factor” which determines how “random” the path will be (QF=1 is a good default choice), then click “Generate Hamiltonian path”. Check “Circuits only” if you wish to only generate Hamiltonian circuits. The default option is for the starting configuration to visit every site, but if you unselect “Must fill” it's possible that not every site will be visited. In particular, if you set quality factor to 0, and unselect “Must fill” then the starting configuration will be a single point starting at a randomly selected site.

Play game: Toggle the active end by pressing “t”, toggle the display of arrows indicating the path direction by pressing “a”, and make backbite moves by moving the active end using the direction keys. Can you make a spiral, starting from a random configuration?

See effect of random backbite moves, enter either via keyboard or clicking appropriate button: “r” makes a random move for the active end (hold down to repeat), “shift+r” makes 100 random moves, “e” makes a random move for either end (hold down to repeat), “shift+e” makes 100 random moves.

New command (June 4, 2015): “s” toggles between different modes for showing the trace of the movement of the ends. Default mode: show nothing, record nothing (erase traces). Record mode: record traces and draw them. Show mode: no longer add to recording of traces, but continue showing existing one.

New command (February 1, 2016): “v” toggles between hiding and showing walk, in order to highly the vector field (arrows).

Rows:       Columns:       Quality factor:       Must fill:       Circuits only:



              

Canvas element not supported in your browser.

History: The impetus to create this generator came from Daniel Crooks, an artist based in Melbourne, who needed a tool for generating long Hamiltonian paths. In his words:
My original interest in the Hamiltonian paths was for a portraiture project. I've developed a process for taking large format photographs using a video camera and a robotic pan/tilt head to 'scan' the image of the sitter over time. As part of the research I became interested in Hamiltonian paths, firstly as a motion path for the camera and then subsequently the aesthetic and conceptual possibilities inherent in the paths themselves.

I had previously come across the aforementioned paper on sampling Hamiltonian paths, and took the opportunity to learn some javascript and create this generator. I hope to apply the expertise gained in this enterprise to other visualisation projects in combinatorics and statistical mechanics.

Usage: Specify desired grid size and choose “quality factor” which determines how “random” the path will be, then click "Generate Hamiltonian path" or reload page. Check “Circuits only” if you wish to only generate Hamiltonian circuits (read technical details below to see why circuits are not selected uniformly at random).

Quality factor of 1.0 should be fine for most purposes; for large grids it may be worth trying 0.5 or even 0.1.

Tested on firefox and chrome browsers. N.B.: for large grids (say 100 × 100 or larger) you may be prompted to stop the script due to the long running time. For chrome, I found that if I did nothing the script would keep running in the background, whereas for firefox I would have to click "continue" for the script to complete.

Technical details:

  • Running time(n × n grid) = (Quality factor) × 20 × n2 log2n × Pr(success of backbite move) × (Expected CPU time for backbite move)
  • The `quality factor' is an arbitrary constant, while the factor of 20 seems to ensure that Hamiltonian path with good randomness is achieved when quality factor is 1.
  • The cover time for the simple random walk on an n × n grid is n2 log2n (I've found this stated in a number of places, but if anyone could give me the original reference I would appreciate it). The Hamiltonian path endpoints perform something like a random walk on the grid, and so we use this as an approximation for the cover time. (It may be a tight bound, but I'm not an expert on this problem and can only say that it seems plausible that the bound is in fact tight.)
  • The probability of success of the backbite move approaches 1 as n becomes large.
  • I have not performed any testing to determine the mean CPU time for a backbite move, but it must be O(n2), and it is reasonable to suppose that in fact it is a relatively small power of n. A more sophisticated implementation would allow the backbite move to be performed in time O(log n).
  • The Markov chain resulting from repeated application of the backbite move has not (yet) been proved to be ergodic. This is an interesting open problem. The Markov chain is ergodic for small grid sizes, and my intuition is that the algorithm is extremely likely to be ergodic for arbitrary two-dimensional grids (it seems to me that if the set of Hamiltonian paths were to be disconnected this would be more likely to occur for smaller grids for which the grid boundary has greater influence). For three dimensions and higher I don't have any intuition because here large grids are intrinsically different to small grids due to the existence of knots.
  • Hamiltonian circuit generator just generates a path, and continues iterating the backbite move until a circuit is generated. This method cannot select a circuit uniformly at random because circuit selection probability is weighted by the (expected) space between samples. I think this can be best explained by an example: suppose we have a Markov chain to uniformly select elements 1 and 2 from a list of N elements. For each time step we can move up or down one element on the list with uniform probability; if this reaches 0 or N+1 the move is rejected. This Markov chain selects 1 and 2 with uniform probability, but if we look at the behaviour of the full chain the probability that we will sample 1 before 2 given an arbitrary starting time vanishes with increasing N as 1/N. This is because at the starting time we are almost surely in the interval [3,N], and in this case the next element must be a 2. This is an extreme example, and the Hamiltonian circuits generated here are likely to be statistically extremely similar to circuits generated from the uniform distribution, but the method used in this Hamiltonian circuit generator should most definitely not be used for serious numerical work.