Overfloater

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?

In my last post I mentioned Operator Overloading, and why I think it would be interesting to see this as a proposal for the ECMAScript 4 specification (the new JavaScript specification).
I’ve been following the ECMA discussion list and the ES 4 wiki, and I was surprised to see that I feel the same way as some people in the ECMA group do about operator overloading.
The Operator Overloading proposal has been made a couple of times before, but it was disregarded as beeing too weak to be considered.

However, this proposal has been superseeded by some other (very interesting) proposal: generic functions (a.k.a multimethods).

What are generic functions?

The first time I discovered generic functions was while playing with Common Lisp’s Object System (CLOS).
In fact, early Lisp systems worked as Smalltalk did, by implementing a send function:

(send object :foo)

instead of just doing:

(foo object)

They finally came with the solution of creating generic functions that could be implemented by methods. This design is far more expressive that the classic OO design, implemented in languages such as Java.
Since this design is far from classical OO ones, explaining by example turns out to be quite difficult: the wikipedia examples aren’t very enlightening (see the article’s discussions).

So here I go.

Java has function overloading: that means that several methods with the same name can be defined in the same class, provided that the type (or number of arguments) defined in each method is not the same.

So, for example, lets define a Java class Person with two eat methods:

  class Person {
    public void eat (Food f) { println ("eating food"); }
    public void eat(Pasta p) { println ("eating pasta"); }
  }

(Pasta extends Food)

We have succesfully overloaded the eat method. However, the overloading happens at compile time, and there’s no dynamic dispatch. So, for example this code:

  Food food = new Pasta();
  somePerson.eat(food);

Will answer “eating food”, which isn’t exactly what we want.

Now lets consider this code:

class John extends Person {
    public void eat(Food f) { println ("mmm...."); }
    public void eat(Pasta p) { println ("Yummy!"); }
  }

  Person me = new John();
  Food pasta   = new Pasta();
  me.eat(pasta);

This code will answer “mmm…”. But there’s one important thing: we’ve called a method from John’s class, instead of some eat method from Person.

This had to be decided at run time, since me is of type Person, but we assigned a John to it…

Now lets define, in pseudo-code, an abstraction of these eat methods, that could be thought as decoupled from the John and Person classes. For example, we could re-write John and Person eat methods as four independent functions:

public void function eat(John john, Food f) { ... }
public void function eat(John john, Pasta p) { ... }

public void function eat(Person person, Food f) { ... }
public void function eat(Person person, Pasta p) { ... }

What we know about these methods is that Java checks its first argument type at runtime, but all other arguments are checked at compile-time.
So, as far as dynamic dispatch concerns, Java has single dispatch, and function overloading only refers to compile-time checked types, which in general doesn’t yield the expected result. (This problem beeing solved by the visitor pattern in most cases).

A generic function can be seen as a family of functions that provide multiple dispatch, that means that all arguments of the function are checked at runtime (on invocation). Not only the first argument, but all.
Compared to Java, this approach would, in most cases, yield the expected answers without having to implement some patterns like the visitor pattern.

The four methods defined above could be redefined in CLOS as:

(defmethod eat ((john John) (f Food)) ... )
(defmethod eat ((john John) (p Pasta)) ... )

(defmethod eat ((person Person) (f Food)) ... )
(defmethod eat ((person Person) (p Pasta)) ... )

Generic Functions in JavaScript

The Generic Functions JavaScript proposal aims to solve all weaknesses existing in the Operator Overloading proposal, but it also provides a more generic way of defining and manipulating functions.
Operator Overloading should be seen as a particular case of what can be done with generic functions in JavaScript.

In JavaScript, a generic function could be defined as:

generic function f(x, y);

Since a generic function defines a family of functions, there’s no function body in it.
A generic function can also be defined with type annotations:

generic function f(x: Numeric, y: Object): MyClass;

A method is then defined over an existing generic function, using specializers:

 generic function f(x:int, y:boolean): string {
      if (y)
          return string(x);
      else
          return "37";
  }

Eventually, built-in generic functions could be defined for common operators, providing a way of overloading operators:

generic function +(a:Complex, b:Complex) {
   return new Complex(a.x + b.x, a.y + b.y);
}

For a JavaScript canvas developer, this would be wonderful, since we mess with Complex, Polar, Matrix classes all the time, and a simple interpolation expression of two complex numbers could be transformed from this:

(to.$add(from.scale(-1))).$scale(delta).$add(from)

into this:

from + (to - from) * delta