I was amazed by Mike Bostock’s algorithms visualization. If you haven’t had a chance to see it, stop reading and go there. The fact is that I felt inspired to learn some Javascript and d3.js. Here are my favorite references: Eloquent Javascript (which is a great book that is open for download), a fun, difficult introduction to d3.js (that’s the name of the tutorial) and mbostock’s blocks (which is a series of examples by Mike Bostock). I think I learned mostly by taking some of Bostock’s examples and trying to modify them. I also learned a lot by just googling and searching StackOverflow.

When someone mentioned Javascript to me, my first thought was: oh, this is going to look like Java ! Actually no ! To my surprise it has nothing (or very little) to do with Java. It is a functional language like Haskell (btw, learning Haskell is a lot of fun. Here is a tutorial that is so much fun you can do just to entertain yourself — and it is free online).

My first impulse was to create an algorithms visualization. When I was trying to find a good one to implement, I saw in my bookshelf the Markov Chains and Mixing Times book that was sitting there for a while and I recalled it had all those nice models from statistical physics that are analyzed algorithmically. The one that is at the same time very simple and interesting is the Ising Model. In the Ising Model, there is a grid (or more generally a graph) in which each cell (or node in the graph) has a spin . So a state is an association of a spin for each cell. A transition in the Ising model is as follows: we choose a cell at random, look at its neighbors (the cells adjacent to it) and compute where is the set of neighbors of . Then we update the spin of to with probability , where is a parameter known as the inverse temperature parameter. If the selected node transition to each spin at random. If , it transitions to the spin that is more frequent among its neighbors (breaking ties at random).

Here is the visualization: you can choose the inverse temperature (parameter ) as well as the speed. Then in each timestep, one cell is chosen at random, colored in red, and then updated (it is colored in black if the spin is 1 and in white if the spin is -1). We start the simulation from a random configuration (observe that setting the inverse temperature to 0, the spins are scattered, but increasing the inverse temperature, spins start concentrating on certain regions) :

Here is how to do it in Javascript ? First, let me show you a standalone example (i.e. not an example embedded in a blogpost). Follow this link. There you can just look at the source code (in Chrome, View->Developer->View Source) and you get the entire code, which we will discuss in a bit. One other cool thing you can do there is to open the Javascript Console and interact with visualization. In Chrome, go to View->Developer->JavascriptConsole. Then you will open an interface where you can play with the visualization. Try typing something like `interv1`

and it will return the value of this variable, which is the interval between two updates in the first graph. Now try changing the value by writing `interv1=2`

and making it a lot faster (you might also want to set the temperature to zero to make updates more evident, either by using the slider or by doing `itemp1=0`

in the console). Now, to see you can iteract even more, try changing the color of the first cell to green, by doing:

i1_pointmap[[0,0]].attr("fill","rgb(0,255,0)");

Ok, now to the code. If you look at the html file, the first thing we do is to import the d3.js library, which is the library we use for visualization (in Javascript, like in any programming language we use libraries to get all sorts of cool functionalities). After that we define a function call `generateGrid`

which takes number of horizontal tiles, number of vertical tiles and size of each tile size. The function first creates an SVG canvas, which is a container for graphics. Then adds to it Nx times Ny squares. Notice the for-loop in Javascript is a bit different: we create a range and then call a function for each element of the range, by doing `d3.range(n).forEach(function(x) { ... })`

, which would be equivalent to `for(int x = 0; x < n ; ++x) { ... } `

. The function returns a map from coordinates of type `[i,j]`

to the corresponding square. Now the subsequent code just takes some cell and modifies its color. Here is the part discussed so far:

<script src="http://d3js.org/d3.v3.min.js"></script> <script> // Generates and Nx by Ny grid with pointers to each tile in the grid // return a map from [i,j] to the corresponding tile function generateGrid(Nx, Ny, side_length) { var svg = d3.select("body").append("svg") .attr("width", side_length*(Nx+2)) .attr("height", side_length*(Ny+2)); var gTile = svg.append("g") .attr("fill","#FFFFFF") .attr("stroke", "#000000") var gPointmap = {}; d3.range(Nx).forEach(function(x) { d3.range(Ny).forEach(function(y) { gPointmap[[x,y]] = gTile.append("rect") .attr("x", side_length*(x+1)) .attr("y", side_length*(y+1)) .attr("width", side_length) .attr("height", side_length) .attr("fill", "#FFFFFF"); }) }); return gPointmap; } var spincolor = {"1":"#000000", "-1":"#FFFFFF"}; </script>

So far we have only a helper function but we don't have yet anything. So if you just add the line `pm = generateGrid(10,10,20);`

you create a chessboard. Actually not quite because it is all white. In fact, if you go to this link, open the Javascript console and type:

pm = generateGrid(10,10,20);

you will see your 10 by 10 white grid appearing in the end. If you want to color some of its nodes like a chessboard, you can do something like:

d3.range(10).forEach(function(x) { d3.range(10).forEach(function(y) { if ((x+y)%2 ==0) pm[[x,y]].attr("fill","red"); }) });

then you will get a chessboard. You can create others and keep changing their colors. But now, let's go for the Ising Model simulation: first we create a grid, then we pick a spin at random for each of the nodes. Finally, we define a main loop iteration. We do it as a callback: i.e. a function that returns another function, which is the mainloop execution. We do that since `d3.timer(...)`

takes a function and executes it after a certain interval, so the main loop callback returns a function

<script> // create a white grid 20 by 20 grid var n2 = 20; var i2_pointmap = generateGrid(n2,n2,20); itemp2 = 10; interv2 = 200; directions = [[-1,0],[1,0],[0,-1],[0,1]]; spin2 = {}; // random spin for each cell and color it accordingly d3.range(n2).forEach(function(x) { d3.range(n2).forEach(function(y) { spin2[[x,y]] = 1-2*(~~(2*Math.random())); i2_pointmap[[x,y]].attr("fill", spincolor[spin2[[x,y]]]); }) }); // main loop (in fact a callback, returns a function that executes // one iteration of the main loop) function square_ising_callback() { return function() { // samples a random cell var x = ~~(n2*Math.random()); var y = ~~(n2*Math.random()); // colors this red to display with cell is being updated i2_pointmap[[x,y]].transition().attr("fill", "#FF0000"); // calculate the sum of neighbors spins var neighbors_spin = 0; d3.range(4).forEach(function(i) { var x1 = x+directions[i][0], y1 = y+directions[i][1]; if (x1 >= 0 & x1 < n2 & y >= 0 & y < n2) { neighbors_spin += spin2[[x1,y1]]; } }); // compute the probability of changing to spin 1 and samples // the new spin according to this probability var prob_pos_spin = Math.exp(itemp2 * neighbors_spin) / ( Math.exp(itemp2 * neighbors_spin)+ Math.exp(-itemp2 * neighbors_spin) ); if (Math.random() < prob_pos_spin) { spin2[[x,y]] = 1; } else { spin2[[x,y]] = -1; } // colors the cell with the color of its new spin. We add // a small transition with delay interv2/2 such that the transition // is visible i2_pointmap[[x,y]].transition().delay(interv2/2).attr("fill", spincolor[spin2[[x,y]]]); // after interv2 time, calls back the main loop d3.timer(square_ising_callback(),interv2); return true; } } // call the main loop for the first time d3.timer(square_ising_callback(), interv2); </script>

And that's it ! I was surprised how little effort it took. And I guess it would have taken a lot less if I took time to write the appropriate functions to simulate the Ising model instead of just writing everything in the main loop, which admittedly is not a good practice.

-----

PS: You might wonder how to include Javascript in WordPress. The solution I got was to create an html file and add to WordPress as an iframe. To do that, simply add something as follows in the textual editor (and of course, adding this to any webpage will display the diagram in this blog post):

<iframe src="http://www.renatoppl.com/js/ising5.html" style="border:0; width: 700px; height:550px"></iframe>