Overfloater

This is going to be the first of a couple of posts related to Voronoi Tessellations, Centroidal Voronoi Tessellations and Voronoi TreeMaps. In this post I’ll explain what a Voronoi Tessellation is, what can it be used for, and also I’ll describe an interesting algorithm for creating a Voronoi Tessellation given a set of points (or sites as I’ll call them from now on).

What is a Voronoi Tessellation?

Given a set P := {p1, …, pn} of sites, a Voronoi Tessellation is a subdivision of the space into n cells, one for each site in P, with the property that a point q lies in the cell corresponding to a site pi iff d(pi, q) < d(pj, q) for i distinct from j. The segments in a Voronoi Tessellation correspond to all points in the plane equidistant to the two nearest sites.
Voronoi Tessellations have applications in computer science, chemistry, etc. but I’m most interested in Voronoi Diagrams for constructing Voronoi TreeMaps (more on that in later posts).

How do I create a Voronoi Tessellation?

One algorithm for creating Voronoi Tessellations was discovered by Steven Fortune in 1986.

This algorithm is described as a plane sweep algorithm. Fortune’s Algorithm maintains both a sweep line (in red) and a beach line (in black) which move through the plane as the algorithm progresses.

The structures used in this algorithm are an EventQueue, EdgeList and a binary Tree that tracks the state of the beach line.

The EventQueue stores two distinct type of events that are related to changes in the beach line. These events happen when:

• A site s crosses the sweep line: in this case a new parabola with minimum at s is added to the beach line. A Voronoi Edge is born.
• A circle that touches three sites staying behind the sweep line is found and is tangent to the sweep line (see image below). A Voronoi Vertex is found.

At each of these stages the EdgeList is updated until the algorithm is completed.

Implementations

I haven’t found any interesting implementation of this algorithm in JavaScript. Actually, I didn’t find a working implementation of this algorithm in JavaScript. There’s this version of a JavaScript applet for making Voronoi Tessellations, but it doesn’t seem to work right (the corners of the image generally hold two or more sites in the same cell). Also, the code was based in a C# implementation and isn’t very pretty. Then there’s this blog that mentions the algorithm but there’s no visible implementation, just a JQuery demo that animates parabolas when a mouse crosses a site, but no Voronoi Diagram.

So I made my own implementation, which I tried to make as similar as possible to the original C implementation from Steven Fortune. If you click on the image you can see it in action. Just refresh the page for new Voronoi Tessellations of random positioned sites.

Any comments or advices about how to make this implementation better are welcomed!

I like to see language implementors (or creators in this case) talk about the design challenges or choices they’re facing with in the next version of their languages.

In this video Brendan Eich, the creator of JavaScript, talks about the ES 3.1/4/5 thingy and also explains what features will be added to JavaScript in some near future (at least for the ECMA standard).

I’ll add a couple of comments about the JS features I liked below the video.

New stuff I liked about the language

Most of the things I liked about the new features of the language are related to Meta-Programming. These new features describe new behaviors in object properties, like getters and setters, but they are also related to object and property mutability, configuration, visibility, etc.

Getters and Setters

Getters and Setters were implemented by B.E. more than nine years ago at mozilla, but a new syntax is introduced in the standard by adding a static function to the Object class.

Object.defineProperty(obj, "length", {
  get: function() {
    return this.computeLength();
  },
  set: function(value) {
    this.changeLength(value);
  }
});

In this example the defineProperty static method of the Object class adds the length property to the obj object. The get and set methods will be called when accessing or modifying the length property.
Object.getOwnPropertyDescriptor retrieves the property descriptor of the defined property.

Defining Methods and Richer Property Descriptors
The Object.defineProperty method can also be used to define instance methods:

Object.defineProperty(Array.prototype, "inject", {
  value: function(memo, iterator, context) {
    iterator = iterator.bind(context);
    this.each(function(value, index) {
      memo = iterator(memo, value, index);
    });
    return memo;
  },

  configurable: false,
  enumerable: false,
  writable: false
});

The method does something similar as inject_into or reduce methods do in other languages:

[ 1, 2, 3 ].inject(0, function(a, b) { return a+b; }); //6

If configurable=true, the property will be enabled for deletion or to be changed in other ways.

You can set a property to be non-enumerable by setting enumerable=false, and it won’t be detected in a for in loop (or in any other “prop” in obj expression). This means that for example we could augment Object.prototype with methods without having to iterate through them in a for in loop.

The writable property if setted to false won’t allow you to change the value of that property.

Object.create

Still no support is added for classical inheritance patterns (which makes me happy I must confess).
Instead, the differential inheritance pattern gets a function that had (somewhat) been implemented by frameworks like Closure, MooTools and others with the inherits and $merge functions.
Object.create can be used for implementing prototypical inheritance: you can create a new class A that inherits from B by cloning an object and augmenting it with a Properties object. For example:

var Person = function() {};
Person.prototype.eat = function() {
  alert("eating");
};
//Ninja extends Person
var Ninja = function() {};
Ninja.prototype = Object.create(Person.prototype, {
  doKungFu: function() {
    alert("wootoo");
  }
});

var n = new Ninja();
n.eat(); //eating
n.doKungFu(); //wootoo

However, don’t forget to instantiate the superclass in your subclass constructor:

var Point = function(x, y) {
  this.x = x;
  this.y = y;
};

Point.prototype.distanceToOrigin = function() {
  return Math.sqrt(this.x * this.x + this.y * this.y);
};
//Complex extends Point
var Complex = function(x, y) {
  Point.call(this, x, y); //call the superclass
};

Complex.prototype = Object.create(Point.prototype, {
  add: function(complex) {
    this.x += complex.x;
    this.y += complex.y;
  }
});

Object.preventExtensions, Object.seal, Object.freeze

Mutability is nice but sometimes we need to make our objects immutable for design reasons, for security reasons. These methods change the mutability level of an object.

• Object.preventExtensions prevents an object from extending (i.e adding new properties to it). Still the properties it has can be deleted and their value can be changed.
• Object.seal does everything Object.preventExtensions does and also sets configurable=false for its properties, so they can’t be deleted. The Object properties can be changed though.
• Object.freeze makes the object completely immutable. Object.freeze does the same Object.preventExtensions and Object.seal do but also sets writable=false for all object properties.

I hope this was useful to you. There are a lot more interesting language features to come, so you can read the ECMA draft if you’re interested in knowing more about this new version.

In a previous post I showed the ForceDirected visualization I’m working on for version 1.2 of the JavaScript InfoVis Toolkit, today I’d like to talk about another visualization I’ve been working on, the Sunburst Visualization.

What’s the Sunburst Visualization?

I guess an example could help here:

A Sunburst visualization is a radial space-filling visualization technique for displaying tree like structures. There are other space-filling visualization methods that use other visual encodings for describing hierarchies. For example, the Treemap is a space-filling visualization that uses “containment” to show “parent-child” relationships.

There are a couple of subtle changes that can improve the way the information is communicated by this visualization.

• The “classic” Sunburst visualization uses horizontal labels for node names. One problem with this is that as I mentioned in a previous post labels can be occluded. One solution for this is to rotate labels in a way that they’re not occluded.
• A simple yet important thing to do when rotating labels is to rotate the labels in a way that they’re always facing up.
  In this example some labels are upside-down:

  

  A simple check could make labels more readable:

  
• Another interesting thing that can be used with the Canvas Text API is the maxWidth parameter. This is an optional parameter that can be used to try to force the text to fit some width. I use this parameter when plotting the Sunburst visualization:
  

Node Styling and Behavior

The visualization also implements events for hovering and clicking nodes. You can also provide any number of styles to be smoothly updated when hovering and clicking nodes. There’s also onClick and onHover callbacks that are called when a node is clicked or hovered respectively.
For example, this is the configuration I used in the previous example:

        NodeStyles: {
          attachToDOM: false,
          attachToCanvas: true,
          stylesHover: {
            'color': '#d33'
          },
          stylesClick: {
            'color': '#3dd'
          },
          onClick: function(node) {
            //build right column relations list
            buildRightColumnRelationsList(node);

            //hide tip
            sb.tips.tip.style.display = 'none';

            //rotate
            sb.rotate(node, 'animate', {
              'duration': 1500,
              'transition': Trans.Quart.easeInOut
            });
          }
        },

You can also add tool-tips as I did in the example. The configuration I used was:

        Tips: {
          allow: true,
          attachToDOM: false,
          attachToCanvas: true,
          onShow: function(tip, node, elem) {
            tip.innerHTML = node.name;
          }
        },

Node styling and tool-tips can be attached to DOM elements (like HTML or SVG labels) or they can also be attached to the Canvas. The latter method uses an internal MouseEventManager to calculate the position of the mouse event and determine which node of the graph is being hovered or clicked.

Collapsing and Expanding Subtrees

I’ve been also implementing animations for collpasing/expanding subtrees:

The collapsing process reduces the angle span occupied by a parent node and sets its children alpha value to zero. There’s also a visual mark set for collapsed nodes.

I hope you like this visualization. There’s still much work to do, mostly regarding browser compatibility. I’ll keep you up to date with the progress of this visualization and the next visualization I’ll be implementing in the next post

I’m currently working on three new visualizations for the JavaScript InfoVis Toolkit that will be added in version 1.2.

I started the development of these new visualizations a couple of weeks ago, and while trying to incorporate these new visualizations harmoniously into the Toolkit I’ve found myself considering new design and code abstractions I haven’t thought about before. That’s good for the Toolkit, and also good for my brain

One of the visualizations I’ll be incorporating in the next major release is a Force-Directed visualization. I first want to thank Marcus Cobden for donating a lot of code related to this algorithm that you can find here.

My code is based in his donation and also in a nice overview of Force-Directed layout algorithms that I’ve found here.

So what are Force-Directed Layout Algorithms?

Force-Directed Layout algorithms are graph drawing algorithms based only on information contained within the structure of the graph itself rather than relying on contextual information. The most straightforward Force-Directed algorithm uses repulsive forces between nodes and attractive forces between adjacent nodes. This physical model produces some local minima in which the graph, well, gets to a stable configuration and is drawn in an aesthetically pleasing way.

The main algorithm consists on a main loop that simulates the system for some iterations and then plots the graph. The system will consist on repulsive forces between all graph nodes and attractive forces between adjacent nodes. The force models considered correspond to Hooke’s law and Coulomb’s law.

Here’s an example with some JSON data I also use for other examples at the demos page:

There are lots of refinements and different methods for making Force-Directed Layouts. Some are just based on the model I described before, others are based on what’s called Graph Theoretic Distances: If for two adjacent nodes their ideal distance is set as d, then for nodes with shortest path distance of n their ideal layout distance should be n * d. Attractive and repulsive forces are used to make a graph system with random nodes positions get to a local minima based on these rules.

I implemented the first model I described. For each iteration the computePositionStep method is called to update all nodes positions based on attractive and repulsive forces. The formal parameters passed to the method are property which is an array of node properties which contain positions to be updated and opt which is an object containing layout options like generic repulsive and attractive force functions. $C creates a new Complex Number.

  computePositionStep: function(property, opt) {
    var graph = this.graph, GUtil = Graph.Util;
    var min = Math.min, max = Math.max;
    var dpos = $C(0, 0);
    //calculate repulsive forces
    GUtil.eachNode(graph, function(v) {
      //initialize disp
      $each(property, function(p) {
        v.disp[p].x = 0; v.disp[p].y = 0;
      });
      GUtil.eachNode(graph, function(u) {
        if(u.id != v.id) {
          $each(property, function(p) {
            var vp = v.getPos(p), up = u.getPos(p);
            dpos.x = vp.x - up.x;
            dpos.y = vp.y - up.y;
            var norm = dpos.norm() || 1;
            v.disp[p].$add(dpos
                .$scale(opt.nodef(norm) / norm));
          });
        }
      });
    });
    //calculate attractive forces
    var T = !!graph.getNode(this.root).visited;
    GUtil.eachNode(graph, function(node) {
      GUtil.eachAdjacency(node, function(adj) {
        var nodeTo = adj.nodeTo;
        if(!!nodeTo.visited === T) {
          $each(property, function(p) {
            var vp = node.getPos(p), up = nodeTo.getPos(p);
            dpos.x = vp.x - up.x;
            dpos.y = vp.y - up.y;
            var norm = dpos.norm() || 1;
            node.disp[p].$add(dpos.$scale(-opt.edgef(norm) / norm));
            nodeTo.disp[p].$add(dpos.$scale(-1));
          });
        }
      });
      node.visited = !T;
    });
    //arrange positions to fit the canvas
    var t = opt.t, w2 = opt.width / 2, h2 = opt.height / 2;
    GUtil.eachNode(graph, function(u) {
      $each(property, function(p) {
        var disp = u.disp[p];
        var norm = disp.norm() || 1;
        var p = u.getPos(p);
        p.$add($C(disp.x * min(Math.abs(disp.x), t) / norm,
            disp.y * min(Math.abs(disp.y), t) / norm));
        p.x = min(w2, max(-w2, p.x));
        p.y = min(h2, max(-h2, p.y));
      });
    });
  }

You can find more information about this algorithm in this overview of Force-Directed algorithms.
This method is called multiple times to provide a final layout, for example like this:

      for(var i=0; i < times; i++) {
        opt.t = opt.tstart * (1 - i/(times -1));
        this.computePositionStep(property, opt);
      }

Where times corresponds to the number of iterations of the simulation, and is generally > 50 and t can be thought as the global temperature of a system that gets cooler with each iteration.

Performance

Although there are a couple of methods to reduce the complexity of this algorithm, this implementation runs like O(V^3), which can be considered as really bad performance.

This is not desirable for real-time interactive visualizations, in which everlasting computation algorithms can lead to blocking browser popups like “This Script is Taking too long…” or things like that.

One way you can avoid these popups is by making incremental computations. This can be done by splitting the main algorithm that has for example 100 iterations into smaller pieces of 20 iterations each. The main iteration loop could then be changed into something like this:

  computePositions: function(property, opt, incremental) {
    var times = this.config.iterations, i = 0, that = this;
    if(incremental) {
      (function iter() {
        for(var total=incremental.iter, j=0; j<total; j++) {
          opt.t = opt.tstart * (1 - i++/(times -1));
          that.computePositionStep(property, opt);
          if(i >= times) {
            incremental.onComplete();
            return;
          }
        }
        incremental.onStep(Math.round(i / (times -1) * 100));
        setTimeout(iter, 1);
      })();
    } else {
      for(; i < times; i++) {
        opt.t = opt.tstart * (1 - i/(times -1));
        this.computePositionStep(property, opt);
      }
    }
  }

This method could be called for example like this:

    //compute positions incrementally and animate.
    fd.computePositions(property, opt, {
      iter: 20,
      onStep: function(perc) {
        Log.write(perc + '% loaded...');
      },
      onComplete: function() {
        Log.write('done');
       fd.animate();
      }
    });

And the main computation would be split into smaller parts calling on each step of the computation the onStep callback.

Graph Operations

For graph operations (Adding/Removing nodes and edges, Graph Sum and Graph Morphing) I make all iterations in the first layout and then only apply 20 iterations after some operation has been completed. Here's a video:

When (*not*) to use Force-Directed Layouts

Force-Directed Layouts can be a good choice when you're drawing general graphs and you don't have domain specific (or any other topological) information about them.
Tree structures however are a special case of graphs: this means that tree structures have more constrains and therefore there's more contextual information for drawing a Tree than for drawing a general graph.
Also, Trees are easier to grasp for the human eye than "general graphs". There's that intrinsic notion of hierarchy that can be used to draw aesthetically pleasing graph layouts. Think about the "general graph" layouts that start with the drawing of a spanning tree and then add the "extra edges" to complete the graph structure (for example here and here). The Multitrees method I mentioned a couple of posts ago was also developed to try to extract more contextual information about a graph and draw it based on a notion of partial hierarchy.

Because of this, in my opinion, it wouldn't be wise to plot Trees that have many nodes with this Force-Directed algorithm: this extra-information about trees isn't used in this layout. However, if you're planning on drawing general graphs and you don't have any other information about them, then this algorithm can detect interesting symmetries and make aesthetically pleasing drawings.

I'll keep you updated with the other visualizations I'm working on in the next posts.

As you might know, the JavaScript InfoVis Toolkit uses the HTML5 Canvas element for plotting and animating graphs. This is all very nice, Canvas performance compared to other techniques for plotting these things (SVG for example) is by far superior. But of course, there are drawbacks.

Canvas better performance is due to the fact that there are no tracked elements: the Canvas is simply an image and you’re drawing there just like you’d be drawing something in paint. One big problem is that there’s no native possibility to add events to what’s drawn in Canvas, like a plotted node, edge or label.

As opposed to Canvas, SVG has a DOM/XML like spec: you have all these tags (<g> <text> <rect>) and each of them is just like a DOM element: you can add click event handlers, individual styling with CSS, etc.
Having to keep track of all these elements and handling a DOM-tree makes the performance of SVG not suitable for visualizing (and animating) medium to large datasets on the web.

Using HTML labels

Just like SVG, HTML is a DOM/XML-like spec, where you can add event handlers to each element. Also, every web developer knows HTML so exposing HTML labels through user-defined controller methods in the library seemed to me like a good choice. For controller methods like onCreateLabel or onPlaceLabel an HTML element is passed and the user can style or add event-handlers to it.

For example, here’s a fragment of the code used in the RGraph demo. You can see the rest of the code here:

        //Add the name of the node in the correponding label
        //and a click handler to move the graph.
        //This method is called once, on label creation.
        onCreateLabel: function(domElement, node){
            domElement.innerHTML = node.name;
            domElement.onclick = function(){
                rgraph.onClick(node.id);
            };
        },
        //Change some label dom properties.
        //This method is called each time a label is plotted.
        onPlaceLabel: function(domElement, node){
            var style = domElement.style;
            style.display = '';
            style.cursor = 'pointer';

            if (node._depth <= 1) {
                style.fontSize = "0.8em";
                style.color = "#ccc";

            } else if(node._depth == 2){
                style.fontSize = "0.7em";
                style.color = "#494949";

            } else {
                style.display = 'none';
            }

            var left = parseInt(style.left);
            var w = domElement.offsetWidth;
            style.left = (left - w / 2) + 'px';
        }

In my opinion this is a good approach, good points are:

1. I'm using well known HTML elements.
2. Dealing with DOM elements let's you add event handlers, individual styling and things like that.

Weak points are:

1. I'm using a DOM tree, which means that if labels are plotted at all times I'm exhaustively updating the DOM and this might lead to performance problems.
2. HTML is good for structuring pages, but for example you might want to apply transformations to HTML elements (like rotating labels, etc), and these aren't supported by all browsers yet.

   So one of the problems that might arise is, for example, the fact that in radial layouts labels might be occluded:

   

Using SVG labels

So I began exploring other possibilities to create labels. For this I abstracted the Label interface I had and split it into:

• Graph.Label.Native (for native canvas labels)
• Graph.Label.DOM(abstract class for dom elements)
• Graph.Label.HTML(extends the DOM interface with HTML specific stuff)
• Graph.Label.SVG(extends the DOM interface with SVG specific stuff)

I also modified the Canvas class so you can specify the type of labels you want to use, labels:'HTML', labels:'SVG' or labels:'Native'. Default's HTML.

The same RGraph example code now would look like this:

        //Add the name of the node in the correponding label
        //and a click handler to move the graph.
        //This method is called once, on label creation.
        onCreateLabel: function(domElement, node){
            domElement.firstChild
              .appendChild(document
                .createTextNode(node.name));
            domElement.onclick = function(){
                rgraph.onClick(node.id, {
                  hideLabels: false
                });
            };
        },
        //Change some label dom properties.
        //This method is called each time a label is plotted.
        onPlaceLabel: function(domElement, node){
            var bb = domElement.getBBox();
            if(bb) {
              //center the label
              var x = domElement.getAttribute('x');
              var y = domElement.getAttribute('y');
              //get polar coordinates
              var p = node.pos.getp(true);
              //get angle in degrees
              var pi = Math.PI;
              var cond = (p.theta > pi/2 && p.theta < 3* pi /2);
              if(cond) {
                domElement.setAttribute('x', x - bb.width );
                domElement.setAttribute('y', y - bb.height );
              } else if(node.id == rgraph.root) {
                domElement.setAttribute('x', x - bb.width/2);
              }

              var thetap =  cond? p.theta + pi : p.theta;
                domElement.setAttribute('transform', 'rotate('
                + thetap * 360 / (2 * pi) + ' ' + x + ' ' + y + ')');
            }

This code does a little bit more than just plotting the label, it rotates the labels so they're not occluded:

Good points of this approach are:

• Just like with any other DOM element, you can add event handlers.
• You can apply transformations to labels.

Weak points:

• Performance, for the same reasons as HTML.
• IE does not support SVG.

Bonus good point: Google is making work SVG in IE with some open source library that works apparently the same as the ExCanvas library. Here's the Open Source project that will be presented here.

That's like the main reason why I've been considering a different approach for labels

Native Canvas labels

Native Canvas labels make use of the HTML5 Canvas text API to plot labels.
Since the labels are just painted in the Canvas there's no DOM tree to update, and performance is good.
The Canvas text API has fillText, strokeText and measureText as methods. You can read more about the Canvas Text API here.

This is the code I added to the Graph.Label.Native class:

Graph.Label.Native = new Class({

    plotLabel: function(canvas, node, controller) {
        var ctx = canvas.getCtx();
        var coord = node.pos.getc(true);
        ctx.fillText(node.name, coord.x, coord.y);
    },

    hideLabel: $empty
});

A very good point about this approach is performance. Also, the code is simpler. You don't have to keep a labelContainer and update DOM labels each time you're making an animation.

Weak points are:

• Opera does not support this feature.
• You can't natively add event handlers to labels. I think I've seen someone do something similar for text in processing, but I'm not sure there's a good way of doing this without keeping track of the position of each label and perform a check each time a click is triggered in the canvas element.
• I should change the way I define controller methods, in order to be able to pass a custom label object with x, y, theta, rho, width, height properties that could be modified on the fly, and then translate these changes into translate and rotate native canvas calls to be able to plot the text the way the user wants it. This seems just to damn complicated.... But I'll consider it.

Anyway, these are the methods I've found to plot labels into graphs.

Which one do you think is the best?
Do you know about any other approaches I could take to solve this problem?

Most of us JavaScript developers can’t work without using a JavaScript Library/Framework today. JavaScript is a very nice language, but it requires for you to write a lot of code before you can implement some interesting animation, drag and drop feature, or Ajax request/polling.
This is in part due to the fact that every line of code we write must be browser compatible, and that adds lots of “ifs” to our code.
So I guess it’s understandable to think that choosing a framework that can abstract these kind of things for us is good. By using a framework we can concentrate on other kind of problems, more like high-level-usability-pattern problems.

Some frameworks stick with JavaScript as their main language (like MooTools or JQuery). Other frameworks simply let you type another kind of language that then gets compiled into JavaScript. I guess that having a language with built-in classical inheritance syntax and a nice IDE to support it are good reasons to develop these kind of libraries that translate some code into another.

Frameworks are undeniably good, but most of the things I learn about the JavaScript programming language were learn while hacking some pure JavaScript code.
When hacking pure JavaScript code you find yourself hacking common language idioms that are usually abstracted by frameworks. And it’s nice to understand how these things work. When you get how a specific JavaScript pattern/idiom works you get to understand lots of things about the language itself.

Most of the people don’t do this today. You can see posts about call and apply, closures and private members patterns very often in Reddit and Ajaxian, and each time that post appears lots of other people upmod it. So that means that most of the people today probably use the bind Function method without really knowing what it does.

The worst part is that JavaScript is a very beginner-friendly language, a good start for people not having a computer sicence related background, but at the same time there are lots of things about the language itself that are advanced features (object mutability, booleans as defaults, functions as first class citizen, prototypal inheritance) and most of the users are never aware of these features, most of the time due to the abstraction of the frameworks they’re using.

An Example

This is a very simple example (and interesting interview question also).
If you’re dealing with the dom when hacking JavaScript then you might often use the hasClass and removeClass methods from JQuery, MooTools, or whatever.

So, how would you write them?

function hasClass(domElement, className) {
 //code here...
}

function removeClass(domElement, className) {
//code here...
}

Please, if you’re reading this, take five minutes of your time and write these functions out before reading the answers. Believe me, it’s worth the effort. I mean, how much time can it take?

The Answers

click here to show the answers

function hasClass(domElement, className) {
  return (' ' + domElement.className + ' ')
        .indexOf(' ' + className + ' ') >= 0;
}

function removeClass(domElement, className) {
 domElement.className = domElement.className
      .replace(new RegExp('(^|\\s)' + className + '(?:\\s|$)'), '$1');
}

var className = 'myclassname';
domElement.className = 'myclassname yeah';

removeClass(domElement, className);

'(^|\\s)myclassname(?:\\s|$)'

'(^|\\s)myclassname(\\s|$)'

domElement.className == className //means '^className$'
|| domElement.className
          .startsWith(className + ' ') //means '^className\\s'
|| domElement.className
          .endsWith(' ' + className) //means '\\sclassName$'

Conclusion

These methods could have probably been written differently if disk space and performance weren’t such an important issue in JavaScript, but with those constraints even the most trivial methods like hasClass and removeClass can be interesting to read.
So this is my recommendation: try to understand how things you normally use are implemented. There are lots of interesting JavaScript libraries that make excellent code that’s performant and save disk space (:P) so check them out, you might learn about lots of things, even the most simple functions can have interesting concepts.

While trying to fix a SpaceTree layout issue for version 1.1.2 of the JavaScript InfoVis Toolkit I found a Microsoft Research paper that describes a functional programming approach for rendering trees in an aesthetically pleasing way.

But what is aesthetically pleasing?

Andrew J. Kennedy takes Radack and Walker rules:

In order to calculate nodes’ positions Kennedy takes a “bottom-up” approach:

Starting from the root node, draw for each node all its subtrees without breaking any rules. Fit these subtrees together without changing their shape, and also without breaking rules 1 and 3 (i.e do not break symmetry and avoid cluttering/overlapping of nodes). Finally, center their parent above them like specified in rule 2.

The “fitting” of the subtrees is calculated by operating on subtrees extents. A subtree extent is a data structure containing the relative coordinates of the boundary of a subtree. One frequent operation between extents is merging:

Other operations involve setting the distance between two extents, translating extents, etc.

Implementation

Kennedy implements this algorithm in Standard ML. I made a JavaScript adaptation. I like the Standard ML version a lot more; in this case rich typing makes very elegant code.

Here’s my code implementation, in case you want to compare it to Kennedy’s.
My version takes into account different tree layouts (left, right, bottom, top), siblings and subtrees offsets and different node sizes as opposed to Kennedy’s version.

 function movetree(node, prop, val, orn) {
   var p = (orn == "left" || orn == "right")? "y" : "x";
   node[prop][p] += val;
 };

 function moveextent(extent, val) {
     var ans = [];
     $each(extent, function(elem) {
         elem = slice.call(elem);
         elem[0] += val;
         elem[1] += val;
         ans.push(elem);
     });
     return ans;
 };

 function merge(ps, qs) {
   if(ps.length == 0) return qs;
   if(qs.length == 0) return ps;
   var p = ps.shift(), q = qs.shift();
   return [[p[0], q[1]]].concat(merge(ps, qs));
 };

 function mergelist(ls, def) {
     def = def || [];
     if(ls.length == 0) return def;
     var ps = ls.pop();
     return mergelist(ls, merge(ps, def));
 };

 function fit(ext1, ext2, subtreeOffset, siblingOffset, i) {
     i = i || 0;
     if(ext1.length <= i ||
        ext2.length <= i) return 0;

     var p = ext1[i][1], q = ext2[i][0];
     return Math.max(fit(ext1, ext2, subtreeOffset, siblingOffset, ++i) + subtreeOffset,
                 p - q + siblingOffset);
 };

 function fitlistl(es, subtreeOffset, siblingOffset) {
   function $fitlistl(acc, es, i) {
       i = i || 0;
       if(es.length <= i) return [];
       var e = es[i], ans = fit(acc, e, subtreeOffset, siblingOffset);
       return [ans].concat($fitlistl(merge(acc, moveextent(e, ans)), es, ++i));
   };
   return $fitlistl([], es);
 };

 function fitlistr(es, subtreeOffset, siblingOffset) {
   function $fitlistr(acc, es, i) {
       i = i || 0;
       if(es.length <= i) return [];
       var e = es[i], ans = -fit(e, acc, subtreeOffset, siblingOffset);
       return [ans].concat($fitlistr(merge(moveextent(e, ans), acc), es, ++i));
   };
   es = slice.call(es);
   var ans = $fitlistr([], es.reverse());
   return ans.reverse();
 };

 function fitlist(es, subtreeOffset, siblingOffset) {
    var esl = fitlistl(es, subtreeOffset, siblingOffset),
        esr = fitlistr(es, subtreeOffset, siblingOffset);
    for(var i = 0, ans = []; i < esl.length; i++) {
        ans[i] = (esl[i] + esr[i]) / 2;
    }
    return ans;
 };

 function design(graph, node, prop, config) {
     var orn = config.orientation;
     var auxp = ['x', 'y'], auxs = ['width', 'height'];
     var ind = +(orn == "left" || orn == "right");
     var p = auxp[ind], notp = auxp[1 - ind];

     var cnode = config.Node;
     var s = auxs[ind], nots = auxs[1 - ind];

     var siblingOffset = config.siblingOffset;
     var subtreeOffset = config.subtreeOffset;

     var GUtil = Graph.Util;
     function $design(node, maxsize, acum) {
         var sval = (cnode.overridable && node.data["$" + s]) || cnode[s];
         var notsval = maxsize || ((cnode.overridable && node.data["$" + nots]) || cnode[nots]);

         var trees = [], extents = [], chmaxsize = false;
         var chacum = notsval + config.levelDistance;
         GUtil.eachSubnode(node, function(n) {
             if(n.exist) {
                 if(!chmaxsize)
                    chmaxsize = getBoundaries(graph, config, n._depth);

                 var s = $design(n, chmaxsize[nots], acum + chacum);
                 trees.push(s.tree);
                 extents.push(s.extent);
             }
         });
         var positions = fitlist(extents, subtreeOffset, siblingOffset);
         for(var i=0, ptrees = [], pextents = []; i < trees.length; i++) {
             movetree(trees[i], prop, positions[i], orn);
             pextents.push(moveextent(extents[i], positions[i]));
         }
         var resultextent = [[-sval/2, sval/2]].concat(mergelist(pextents));
         node[prop][p] = 0;

         if (orn == "top" || orn == "left") {
            node[prop][notp] = acum;
         } else {
            node[prop][notp] = -acum;
         }
         return {
           tree: node,
           extent: resultextent
         };
     };
     $design(node, false, 0);
 };

After several months of hard work I can finally announce version 1.1 of the JavaScript InfoVis Toolkit.

What’s the JavaScript InfoVis Toolkit?

The JavaScript InfoVis Toolkit provides tools for creating Interactive Data Visualizations for the Web.

What’s new in this version?

• A new project page where you can access all things related to this library: documentation, demos, tutorials, this blog, etc.
• A complete API documentation generated with Natural Docs, with some Narrative Documentation and Syntax Highlighted Code Examples.
• A Demos page where you can find some interactive library examples and you can browse through the examples code.
• The JavaScript InfoVis Toolkit is now hosted at GitHub, so you can fork it and do whatever you like with it. You can also report bugs with the new issue tracker.

Code-Related

• The library has been split into modules for code reuse.
• All visualizations are packaged in the same file. You can create multiple instances of any visualization. Moreover, you can combine and compose visualizations. If you want to know more take a look at the Advanced Demos.
• This Toolkit is library agnostic. This means that you can combine this toolkit with your favorite DOM/Events/Ajax framework such as Prototype, MooTools, ExtJS, YUI, JQuery, etc.
• You can extend this library in many ways by adding or overriding class methods. The JavaScript InfoVis Toolkit has a robust (and private) class system, heavily inspired by MooTools’, that allows you to implement new methods in the same class without having to define any new Class extension. By creating mutable classes you can add new custom Node and Edge rendering functions pretty easily.
• Custom visualizations are created by adding or changing Node/Edge colors, shapes, rendering functions, etc. You can also implement many controller methods that are triggered at different stages of the animation, like onBefore/AfterPlotLine, onBefore/AfterCompute, onBefore/AfterPlotNode, request, etc.
  You can also add new Animation transitions like Elastic or Back with easeIn/Out transitions.
  If you want to know more about these features please take a look at the Demos code.

As you can see, this new version has been built with four concepts/goals in mind: Modularity, Customization, Composition and Extensibility. I already explained some of these things in the previous post.

Hope you enjoy it.

I’ve been putting a lot of effort in the upcoming version of the JavaScript InfoVis Toolkit lately, and I though it would be a good idea to show some of the new features I came up with.

The new version isn’t finished yet, but I’ve come pretty far and wanted to make a sort of checkpoint for the things I’ve done, the things I’ll be doing and the things I’m thinking about doing.

So what have I been working on?

• A new project page design.
• A complete documentation. I made an API documentation that is also mixed with some narrative documentation for each Class, so you can learn how the visualizations are implemented and how to use them.
• Packaging All visualizations will be packaged in the same file, and you’ll be able to make your own build based on what you’re going to use (Treemaps, Hypertrees, RGraphs, Spacetrees or any combination of those). This is a cool aspect of making modular code.
  The other good thing about modular code is that the size of the full package will drop in ~30% compared to version 1.0.8a
• Examples I’ve been coding some new visualization examples that will be packaged with the library. Some of them are very similar to the ones found in 1.0.8a, but adapted for version 1.1. Other examples show some of the new features of the library, and others try to expose some features of version 1.0.8a that were not properly documented.

Library features

I’ve been building this library with four things in mind:

• Extensibility The library has multiple access points where it can be extended in different ways. For example, all main Classes are mutable objects, so you can extend or implement any method of any class in-place, like for example re-implement the nodes coloring method in the Squarified treemap:

     //TM.Strip, TM.SliceAndDice also work
     TM.Squarified.implement({
       'setColor': function(json) {
         return json.data.$color;
       }
     });
  

  …or adding new node/edge plotting methods in the Hypertree, ST or RGraph:

  Hypertree.Plot.NodeTypes.implement({
    'my-node-rendering-method': function(node, canvas) {
      //implement node rendering here
    }
  });
  

  etc.

• Customization The library provides many ways for customizing the visualizations. There are controller methods that determine the behavior of the visualization, and configuration parameters like node and edge types, color and dimensions. Node shapes can be square, rectangle, circle, ellipse, etc. and edge shapes: line, hyperline and arrow. I also added transition effects like Quart, Bounce, Elastic, Back, etc. for the animations.
• Modularity As explained above, the code has been divided into modules, providing a way for making custom builds of the library. Modularity also takes care of namespacing: I only add Classes that are meant to be accessed by the user and I don’t pollute the window object with unnecessary global objects.
• Composition A major improvement in this version is that all visualizations can co-exist in the same namespace. That means that multiple instances of different visualizations can be used and composed to make new visualizations. I haven’t explored this feature of the library yet, but this would mean that for example I can make a Treemap that has Hypertrees rendered as leaves, or a Spacetree that has Treemaps as nodes, or… well, any other combination of things.

Examples

As you might know, I don’t have the most suited computer for making screencasts, so sorry if you see some performance problems.

This is a short video I made of a RGraph example.

The main idea behind this example is Customization.
That can be seen for example in the different node types, edge types and colors used, as well as in the Elastic transition effect for the animation.

This is just an example to expose as much features as I can in one visualization, so don’t take this as a “useful” visualization example please.

Here is another short video: it illustrates how Graph Operations can be made with the Hypertree visualization.

You’ll see 4 consecutive operations:

1. Removing a subtree The bottom right subtree will be removed with an animation.
2. Removing edges Edges from the top left subtree will be removed with an animation.
3. Adding a graph A graph will be added with an animation
4. Morphing The graph will transform into another graph -with an animation

Enjoy.

I was looking for some way to easily create, read, manipulate and print cyclic or recursive data structures in some programming languages, and got to the cool concept of sharp variables.

Manipulating Recursive Structures in Python

A straightforward way of defining a recursive structure is to first assign a base (non-recursive) structure to a variable, and then alter or extend that variable with a recursive expression. For example, in Python you can write:

my_rec_var = [1, 2, 3]
my_rec_var.append(my_rec_var)

That code will create a recursive data structure: [1, 2, 3, [1, 2, 3, [...]]],
or a = [1, 2, 3, a].

Actually, Python’s print function lets you print a representation of a recursive structure without recursing indefinitely:

>>> print my_rec_var
[1, 2, 3, [...]]

Python’s pickle module lets you dump a recursive data structure into a file. You can also read that serialized structure from the file:

import pickle

#dump it to file
output = open("out.pkl", "wb")
pickle.dump(my_rec_var, output)

However, there’s no literal way of creating, reading or modifying that structure:

>>> my_rec_var = [1, 2, 3, [...]]
 ERROR

Manipulating Recursive Structures in Lisp

For manipulating/printing recursive data structures in Common Lisp we first assign T to the global variable *print-circle*

(setq *print-circle* T)

We can define a recursive structure just as we did with Python, by defining some base structure and then modifying the structure to be recursive:

(defvar *my-rec-var* (list 1 2 3 _))
;Replace the underscore placeholder with a self-reference
(setf (fourth *my-rec-var*) *my-rec-var*)

The final structure is represented with sharp variables:

>>> (print *my-rec-var*)
#1=(1 2 3 #1#)

This is just as the “Mathematical” definition we gave above:
a = [1, 2, 3, a].

What’s interesting about this “serialization format” is that expressions involving sharp variables are truly expressions: these “objects” can be read and manipulated just like any other structure:

>>> (defvar *another-rec-var* ‘#1=(1 2 3 #1#))
#1=(1 2 3 #1#)

>>> (fourth ‘#1=(1 2 3 #1#))
#1=(1 2 3 #1#)

>>> (cons 5 ‘#1=(1 2 3 #1#))
(5 . #1=(1 2 3 #1#))

Sharp variables seem like an excellent solution for creating, reading and manipulating cyclic data structures.

Sharp Variables in JavaScript

Mozilla’s JavaScript implementation has Sharp Variables. They’ve been introduced by Brendan Eich and they are inspired by Common Lisp’s syntax.
Sharp Variables can be pretty useful in JavaScript, since most of the time we’re manipulating object references and Firefox’s toSource() method is pretty useful for debugging (among other things).

var myArray = [1, 2, 3];
myArray.push(myArray);
myArray.toSource();

Try running that in your Firefox console, it should return “#1=[1, 2, 3, #1#]“.

Oh, and did I mention that you can also explicitly manipulate cyclic structures in JavaScript?

//Assign a literal recursive data structure
var anotherArray = #1=[1, 2, 3, #1#];

console.log(anotherArray.toSource());
//"#1=[1, 2, 3, #1#]"

console.log(anotherArray[0]);
//1

console.log(anotherArray[3].toSource());
//"#1=[1, 2, 3, #1#]"

I was happy to find such an interesting Lisp feature in JavaScript.