4 ms·

Color Flood: Wilson's Algorithm

111 points by dsilver 12y ago

tripzilch 12y ago
Looks cool. The article could use a bit more explanation of what exactly I'm looking at. Is this is a flood-fill algorithm? Cause what I remember from back in the day when you could still watch MS Paint do the flood fill, a more efficient version fills out horizontal spans all at once, instead of growing like an ink blot. But it looks cool. EDIT: maybe this is one of those "use the entire RGB colour space" type of renderings? (see http://allrgb.com http://allrgb.com )
- morsch 12y ago
  It's mostly a visualisation of the tree underlying the colours, I'd say. The pixels of the canvas form a grid, and a spanning tree is created for this graph. A spanning tree contains all nodes of a graph, but only a subset of the edges. A tree is a graph that does not contain any cycles.
- thomasahle 12y ago
  It's a colored version of this: https://en.wikipedia.org/wiki/Uniform_spanning_tree https://en.wikipedia.org/wiki/Uniform_spanning_tree
robinhouston 12y ago
Here’s my version of this from last year: http://bl.ocks.org/robinhouston/6027749 http://bl.ocks.org/robinhouston/6027749
rectangletangle 12y ago
I'm not quite sure exactly what I'm looking at, but it looks cool as hell.
nly 12y ago
Warning for the link to Prim's Algorithm: it's a beast and will make FF fairly unresponsive.
- ne0phyte 12y ago
  Weird. It's super smooth even in the Android WebKit control embedded in the HN app on Android 4.4.2. It's been a long time since I switched to Chromium but I really thought Firefox got faster by now. Quick screencast: https://docs.google.com/file/d/0B4MGwWE_SNv0elNfUVdmalp5NVE https://docs.google.com/file/d/0B4MGwWE_SNv0elNfUVdmalp5NVE
- notjosh 12y ago
  What version/OS are you on? I'm running 29 (Aurora? Beta? Whatever it's called :)) on OS X and it's perfectly smooth, low CPU usage.
  - ema 12y ago
    I've got the same problem with version 28.0 on Linux.
  - nly 12y ago
    28, Linux
goshx 12y ago
This is beautiful. I want to hang it on my wall :)
mrcactu5 12y ago
the point of Wilson's algorithm is that each spanning is equally likely. Each tree is selected uniformly amoug the HUGE set of possible spanning trees of this graph. The color patterns in this algorithm vs. Prim algorithm are very different. Unlike Prim algorithm, this pattern is random and has a fractal structure. Is there a good reason a programmer might need each UST to be equally likely?
sltkr 12y ago
That code does NOT implement Prim's algorithm on a graph with randomly-weighted edges. Instead it just does a randomized breadth-first search of the area (starting from the corner), which is the same algorithm used for colouring, which is why the radial pattern occurs. For a randomized spanning tree, edges should be generated with a random weight, and Prim's algorithm extracts them from the frontier ordered by weight. This creates a very different tree structure that is much more similar to the uniform spanning tree generated by Wilson's algorithm. (This comment is based on the code from this page: http://bl.ocks.org/mbostock/11159599 http://bl.ocks.org/mbostock/11159599)
- mbostock 12y ago
  I’d be happy if you could explain more, but the edges here are intentionally unweighted, so I believe the algorithm is correct. It’s based on the description here: http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s... EDIT: Looks like you’re right! It makes a huge difference if you assign each edge a random weight once, rather than simply pulling a random edge of the frontier. Seems like the reference I used has this bug? Here is a fixed version: http://bl.ocks.org/mbostock/11159599 http://bl.ocks.org/mbostock/11159599
  - sltkr 12y ago
    Yeah, I'm pretty sure the site you linked is wrong too, and I think the author doesn't realize it, because he says: > My last post was about using Kruskal’s algorithm to generate random mazes. This article is about using another minimal spanning tree algorithm to do the same: Prim’s algorithm. But his implementation is NOT the same! (His implementation of Kruskal's algorithm does look correct.) Extracting elements at a random index is not equivalent to assigning random weights to elements and extracting the minimum-weight elements.
    - mbostock 12y ago
      I spoke to Jamis Buck on Twitter. It’s called “Randomized Prim’s” on Wikipedia [1], but of course Wikipedia is not authoritative. It does seem confusing to call it a variant of Prim’s given how different the behavior is. [1] http://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim.27s_algorithm http://en.wikipedia.org/wiki/Maze_generation_algorithm#Rando...
santaclaus 12y ago
It would be cool to visualize the depth with a colormap that makes it visually possible to compare depths, e.g. Matlab's Hot. HSV colormaps are pretty but make direct visual comparisons difficult [1]. [1] http://people.renci.org/~borland/pdfs/RainbowColorMap_VisViewpoints.pdf http://people.renci.org/~borland/pdfs/RainbowColorMap_VisVie...
- mbostock 12y ago
  Yes, this is not intended to be a visualization; it is merely something pretty. D3 supports Lab and HCL color spaces [1] which are perceptually uniform; I could use those to improve the accuracy of the distance encoding, but I’d have to sacrifice the current garish aesthetic. [1] http://bl.ocks.org/mbostock/3014589 http://bl.ocks.org/mbostock/3014589
cwmma 12y ago
I love mike bostock's stuff, but his code often makes me feel sorry for whoever has to deal with his code after him // Pick a location that’s not yet in the maze (if any). do if ((index0 = remaining.pop()) == null) return true; while (cells[index0] >= 0); // Perform a random walk starting at this location, previous[index0] = index0; walk: while (true) { i = index0 % width; j = index0 / width | 0; // picking a legal random direction at each step. direction = Math.random() * 4 | 0; if (direction === 0) { if (j <= 0) continue walk; --j; } else if (direction === 1) { if (j >= height - 1) continue walk; ++j; } else if (direction === 2) { if (i <= 0) continue walk; --i; } else { if (i >= width - 1) continue walk; ++i; } note the braceless do while and the labeled jump statements
- judk 12y ago
  Those labelled jumps are equivalent to common unlabeled continues, but safer. The braceless do-whiles are isolated by blank lines and have leading comments. I'd prefer bostock's code over the average uncommented code with cryptic abbreviated var names.
  - kabdib 12y ago
    These would basically be "time for serious feedback" at any place I've worked in the last 25 years. Seriously, the style is going to generate errors.
  - cwmma 12y ago
    so bostock has gotten better, but there was a time (also known as when I did a lot of stuff with topojson and unraveled how it worked) where it looked like this https://github.com/mbostock/topojson/blob/fe691fc61c38a79b093807bd86117e5d13a0d38c/lib/topojson/topology.js https://github.com/mbostock/topojson/blob/fe691fc61c38a79b09...
- IneffablePigeon 12y ago
  Yep, I just a couple of hours messing around with it and got tripped up many times by this stuff.
tantalor 12y ago
You could use an transferable typed array buffer instead of copying an array of integers from the worker thread. Looks like the array is under 4mb, so copying doesn't take very long, and you only do it once, but if you're going to use a worker you might as well. http://updates.html5rocks.com/2011/12/Transferable-Objects-Lightning-Fast http://updates.html5rocks.com/2011/12/Transferable-Objects-L...
hcarvalhoalves 12y ago
I've noticed it stops filling the canvas when I switch tabs, why is that?

111 points by dsilver 12y ago

Looks cool. The article could use a bit more explanation of what exactly I'm looking at. Is this is a flood-fill algorithm? Cause what I remember from back in the day when you could still watch MS Paint do the flood fill, a more efficient version fills out horizontal spans all at once, instead of growing like an ink blot. But it looks cool. EDIT: maybe this is one of those "use the entire RGB colour space" type of renderings? (see http://allrgb.com http://allrgb.com )

morsch 12y ago
It's mostly a visualisation of the tree underlying the colours, I'd say. The pixels of the canvas form a grid, and a spanning tree is created for this graph. A spanning tree contains all nodes of a graph, but only a subset of the edges. A tree is a graph that does not contain any cycles.
thomasahle 12y ago
It's a colored version of this: https://en.wikipedia.org/wiki/Uniform_spanning_tree https://en.wikipedia.org/wiki/Uniform_spanning_tree

robinhouston 12y ago

Here’s my version of this from last year: http://bl.ocks.org/robinhouston/6027749 http://bl.ocks.org/robinhouston/6027749

rectangletangle 12y ago

I'm not quite sure exactly what I'm looking at, but it looks cool as hell.

nly 12y ago

Warning for the link to Prim's Algorithm: it's a beast and will make FF fairly unresponsive.

ne0phyte 12y ago
Weird. It's super smooth even in the Android WebKit control embedded in the HN app on Android 4.4.2. It's been a long time since I switched to Chromium but I really thought Firefox got faster by now. Quick screencast: https://docs.google.com/file/d/0B4MGwWE_SNv0elNfUVdmalp5NVE https://docs.google.com/file/d/0B4MGwWE_SNv0elNfUVdmalp5NVE
notjosh 12y ago
What version/OS are you on? I'm running 29 (Aurora? Beta? Whatever it's called :)) on OS X and it's perfectly smooth, low CPU usage.
- ema 12y ago
  I've got the same problem with version 28.0 on Linux.
- nly 12y ago
  28, Linux

goshx 12y ago

This is beautiful. I want to hang it on my wall :)

mrcactu5 12y ago

the point of Wilson's algorithm is that each spanning is equally likely. Each tree is selected uniformly amoug the HUGE set of possible spanning trees of this graph. The color patterns in this algorithm vs. Prim algorithm are very different. Unlike Prim algorithm, this pattern is random and has a fractal structure. Is there a good reason a programmer might need each UST to be equally likely?

sltkr 12y ago

That code does NOT implement Prim's algorithm on a graph with randomly-weighted edges. Instead it just does a randomized breadth-first search of the area (starting from the corner), which is the same algorithm used for colouring, which is why the radial pattern occurs. For a randomized spanning tree, edges should be generated with a random weight, and Prim's algorithm extracts them from the frontier ordered by weight. This creates a very different tree structure that is much more similar to the uniform spanning tree generated by Wilson's algorithm. (This comment is based on the code from this page: http://bl.ocks.org/mbostock/11159599 http://bl.ocks.org/mbostock/11159599)

mbostock 12y ago
I’d be happy if you could explain more, but the edges here are intentionally unweighted, so I believe the algorithm is correct. It’s based on the description here: http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s... EDIT: Looks like you’re right! It makes a huge difference if you assign each edge a random weight once, rather than simply pulling a random edge of the frontier. Seems like the reference I used has this bug? Here is a fixed version: http://bl.ocks.org/mbostock/11159599 http://bl.ocks.org/mbostock/11159599
- sltkr 12y ago
  Yeah, I'm pretty sure the site you linked is wrong too, and I think the author doesn't realize it, because he says: > My last post was about using Kruskal’s algorithm to generate random mazes. This article is about using another minimal spanning tree algorithm to do the same: Prim’s algorithm. But his implementation is NOT the same! (His implementation of Kruskal's algorithm does look correct.) Extracting elements at a random index is not equivalent to assigning random weights to elements and extracting the minimum-weight elements.
  - mbostock 12y ago
    I spoke to Jamis Buck on Twitter. It’s called “Randomized Prim’s” on Wikipedia [1], but of course Wikipedia is not authoritative. It does seem confusing to call it a variant of Prim’s given how different the behavior is. [1] http://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim.27s_algorithm http://en.wikipedia.org/wiki/Maze_generation_algorithm#Rando...

santaclaus 12y ago

It would be cool to visualize the depth with a colormap that makes it visually possible to compare depths, e.g. Matlab's Hot. HSV colormaps are pretty but make direct visual comparisons difficult [1]. [1] http://people.renci.org/~borland/pdfs/RainbowColorMap_VisViewpoints.pdf http://people.renci.org/~borland/pdfs/RainbowColorMap_VisVie...

mbostock 12y ago
Yes, this is not intended to be a visualization; it is merely something pretty. D3 supports Lab and HCL color spaces [1] which are perceptually uniform; I could use those to improve the accuracy of the distance encoding, but I’d have to sacrifice the current garish aesthetic. [1] http://bl.ocks.org/mbostock/3014589 http://bl.ocks.org/mbostock/3014589

cwmma 12y ago

I love mike bostock's stuff, but his code often makes me feel sorry for whoever has to deal with his code after him // Pick a location that’s not yet in the maze (if any). do if ((index0 = remaining.pop()) == null) return true; while (cells[index0] >= 0); // Perform a random walk starting at this location, previous[index0] = index0; walk: while (true) { i = index0 % width; j = index0 / width | 0; // picking a legal random direction at each step. direction = Math.random() * 4 | 0; if (direction === 0) { if (j <= 0) continue walk; --j; } else if (direction === 1) { if (j >= height - 1) continue walk; ++j; } else if (direction === 2) { if (i <= 0) continue walk; --i; } else { if (i >= width - 1) continue walk; ++i; } note the braceless do while and the labeled jump statements

judk 12y ago
Those labelled jumps are equivalent to common unlabeled continues, but safer. The braceless do-whiles are isolated by blank lines and have leading comments. I'd prefer bostock's code over the average uncommented code with cryptic abbreviated var names.
- kabdib 12y ago
  These would basically be "time for serious feedback" at any place I've worked in the last 25 years. Seriously, the style is going to generate errors.
- cwmma 12y ago
  so bostock has gotten better, but there was a time (also known as when I did a lot of stuff with topojson and unraveled how it worked) where it looked like this https://github.com/mbostock/topojson/blob/fe691fc61c38a79b093807bd86117e5d13a0d38c/lib/topojson/topology.js https://github.com/mbostock/topojson/blob/fe691fc61c38a79b09...
IneffablePigeon 12y ago
Yep, I just a couple of hours messing around with it and got tripped up many times by this stuff.

tantalor 12y ago

You could use an transferable typed array buffer instead of copying an array of integers from the worker thread. Looks like the array is under 4mb, so copying doesn't take very long, and you only do it once, but if you're going to use a worker you might as well. http://updates.html5rocks.com/2011/12/Transferable-Objects-Lightning-Fast http://updates.html5rocks.com/2011/12/Transferable-Objects-L...

hcarvalhoalves 12y ago

I've noticed it stops filling the canvas when I switch tabs, why is that?