11–20 of 27 posts
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?
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)
// 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 = height - 1) continue walk; ++j; }
else if (direction === 2) { if (i = width - 1) continue walk; ++i; }
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 r…
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.
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 r…
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.
Seriously, the style is going to generate errors.
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…
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:
[1] http://people.renci.org/~borland/pdfs/RainbowColorMap_VisVie...
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 r…
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_VisVie...