Wilson's Algorithm | Hacker News Reader

Wilson's Algorithm

bl.ocks.org

204 pointsratsbane25 comments

There is a whole pile of beautifully illustrated algorithms there:

http://bl.ocks.org/mbostock

i spent HOURS looking at that amazing site

When I see mbostock's work it reminds me of what I love about computer science and why I keep trying to learn more. Lovely stuff.

These random walks resemble voltage arcs.

That's because arcs are kind of like semi-random searches through air for a place that will equalize the voltage. See, for example, slow-motion videos of lightning: https://www.youtube.com/watch?v=7kI1d7DMbco

there is a mathematical link between random walks spanning trees and electrical networks

* http://www-math.mit.edu/~goemans/18434S11/RachelChasin-1.pdf

* RANDOM WALKS AND ELECTRIC NETWORKS Peter G. Doyle (Dartmouth), J. Laurie Snell (Dartmouth) http://arxiv.org/abs/math/0001057

Mike Bostock just showed this work last Wednesday at Eyeo Festival. It was a pure work of art.

The video of his talk will be posted next month to their Vimeo channel [1]; worth watching when it comes out.

[1] http://vimeo.com/eyeofestival

Starting in a corner seems to be a worst case choice for a random walk on a non-looped grid. I forked it to

a) use a random order for starting (and restarting) http://bl.ocks.org/jix/30e55ae16b99efe94bfc/ab5a84881174512a... and

b) start from the center and always restart with the innermost free cell http://bl.ocks.org/jix/30e55ae16b99efe94bfc/aeaced224b45a413...

Is there a practical use for this algorithm, or is is simply for beauty?

http://www.math.upenn.edu/~pemantle/papers/snell.pdf

A print out of that would keep a small child entertained for a good amount of time....

For one, it creates a maze, right?

You should consult literature.

I was looking for a nice visual explanation showing the connection between a maze and a spanning tree. I found this visual to be useful: http://cybertron.cg.tu-berlin.de/rapid_prototyping_11ws/maze...

The "Wilson" of the title is David Bruce Wilson (http://dbwilson.com), an accomplished mathematical probabilist, who may be familiar as a developer of perfect sampling ("Propp-Wilson") for Markov chain Monte Carlo computations.

> Initially, the algorithm can be frustratingly slow to watch

By "frustratingly slow", what are we talking about? It's been running for over an hour with no progress and my computer at work automatically reboots over the weekend. How long do I need to keep this tab open?

It finished in about 2 minutes for me, so you probably have a rendering issue. I'm on Chrome stable for Mac...

It depends on whether a the algorithm can generate a sufficiently large path (the white line) at first, since further development requires the purple path intersect that fixed path.

Finally finished. Question: I see I can inspect the canvas element and even edit the code. How do I run it with my edits (without pushing it to a server?)

The way bl.ocks.org works is pretty cool. Here's what you should do:

1) Go to the Gist that this bl.ock refers to: https://gist.github.com/mbostock/11357811

2) Fork that Gist and make your changes.

3) Go to bl.ocks.org/niels_olson/11357811 to see the finished product.

bl.ocks just displays whatever Gists you have up on GitHub, so you don't have to make an account or anything.

Thanks for the easy-to-follow instructions. I could quickly come up with an updated, less-likely-to-bore version ( http://bl.ocks.org/mdengler/a36fac5f10098bb94846 ), and included a version of your instructions and link to your comment.

Refresh your browser. I've had some that look like it'll take hours to complete and others than complete in 30 seconds.

The color flooding visualization is very nice!

Bostock does it again. So awesome and detailed. Great work Mike.

can you someone edit it and make it better? http://runnable.com/U5wQt8xHLYsVkYc_/wilson%E2%80%99s-algori...

Reply on news.ycombinator.com