8
$\begingroup$

Where can I find some code to generate random self-avoiding walks on 2 and 3-dimensional lattices whose side-lengths are powers of two? The walk should pass through every point on the lattice More specifically, how can I find a random hamiltonian path on a large $2^n \times 2^n$ or $2^n \times 2^n \times 2^n$ grid graph?

The distribution doesn't have to be completely uniform, however in general the lattice should look wrinkled. The method used to generate the path should have low probability of producing extremely long stretches of straight line.

$\endgroup$
  • 2
    $\begingroup$ It's fine to ask about an algorithm on here. But software recommendation is off-topic. Also, you could put more effort into 1. defining your problem more rigorously 2. showing your attempt at answering your question. $\endgroup$ – Apiwat Chantawibul Jul 17 '17 at 19:16
  • 2
    $\begingroup$ For example, do you mean random Hamiltonian path on grid graph? $\endgroup$ – Apiwat Chantawibul Jul 17 '17 at 19:25
  • $\begingroup$ Yes; that's exactly what I meant. $\endgroup$ – J. Antonio Perez Jul 17 '17 at 19:28
  • 2
    $\begingroup$ And since it's a random generation. Do you care if a particular path is more likely to get generated than others? i.e. Do you need uniform chance for each path possible? (uniform chance will likely be harder to do.) $\endgroup$ – Apiwat Chantawibul Jul 17 '17 at 19:40
  • 1
    $\begingroup$ What exactly are the requirements on the distribution? You say you don't need a uniform distribution. So are you OK with an algorithm that outputs any hamiltonian path (even if it's always the same one)? If not, specifically what are the requirements? Also, can you be more precise about the class of graphs you want to handle? Finding a hamiltonian path on a grid graph is NP-hard in general, though it sounds like your graph might come from a more restricted class of graphs. $\endgroup$ – D.W. Jul 17 '17 at 22:15
6
$\begingroup$

A procedure is described in A combinatorial algorithm for effective generation of long maximally compact lattice chains.

enter image description here

$\endgroup$
4
$\begingroup$

Here are two javascript implementations of an algorithm to sample Hamiltonian paths on 2-dimensional grid graphs: http://clisby.net/projects/hamiltonian_path/ and http://clisby.net/projects/hamiltonian_path/hamiltonian_path_v1.html (This is my code. The implementation at the first link has more features, while the second allows you to download the sequence of sites visited by the path.)

The javascript programs generate Hamiltonian paths 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 at https://arxiv.org/abs/cond-mat/0508094

The code includes an adjustable parameter that determines how close to the uniform distribution your sample will be, and you could adapt the method (Markov chain Monte Carlo with backbite moves) to 3d grid graphs with a little work.

$\endgroup$
  • 3
    $\begingroup$ What algorithm do these programs use? As this is not a programming site, we are more interested in the algorithm than in its implementation. $\endgroup$ – Yuval Filmus Jul 25 '17 at 5:39
  • $\begingroup$ Thanks for the suggestion, I've added a reference to the algorithm used. $\endgroup$ – Nathan Jul 26 '17 at 8:03
  • $\begingroup$ Thank you so much for your post. I think I actually understand the backbite method better than the other one, but I don't understand how to do the backbite process efficiently. I understand how to do it; just not quickly. Could you provide some more detail on this? I haven't covered graph theory in a class yet and I'm kinda new to this area of computer science. Thank you so much! $\endgroup$ – J. Antonio Perez Jul 27 '17 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.