Archive for the 'visualization' Category

JavaScript InfoVis Toolkit Customizations

I had the chance to play with the JavaScript InfoVis Toolkit lately. It’s nice to be able to use the Toolkit instead of developing it. The main reason I built the Toolkit in the first place was to create specific visualizations I was needing for MusicTrails. At the end I got to code lots of features but didn’t have the chance to play with them for a long time.

I hope these examples can demonstrate that the Toolkit was really built upon the concepts of Modularity, Extensibility and Composability.

Stacked Bar Charts

One of the things I wanted to do for some time now was to adapt the Spacetree visualization to show Bar Charts.
By watching this example we can already tell that the Spacetree can be used to represent something similar to a Bar Chart. For the next example I created a BarChart class that uses a Spacetree with some special node rendering function to plot bars for each node:

What’s also interesting about this widget is that the custom node implementation I made allows it to show stacked values:

Stacked Bar Charts are useful when aggregated results are as meaninful information as knowing the specific value of each analyzed element. The JQuery team used these kind of charts for measuring performance in different browsers for different versions of JQuery. As you can a see in the next picture, the overall performance comparison is as useful as the specific browser performance improvements data.

Implementation
In order to make Stacked Bar Charts I stored multivalued information into the nodes’ data property and then accessed it to render each node like this:

//Here we implement custom node rendering types for the ST
ST.Plot.NodeTypes.implement({
  'stacked': function(node, canvas) {
    var pos = node.pos.getc(true), nconfig = this.node, data = node.data;
    var cond = nconfig.overridable && data;
    var width  = cond && data.$width || nconfig.width;
    var height = cond && data.$height || nconfig.height;
    var algnPos = this.getAlignedPos(pos, width, height);
    var valueArray = data.valueArray;

    var ctx = canvas.getCtx();
    ctx.save();
    if(valueArray) {
     for(var i=0, l=valueArray.length, acum=0; i<l; i++) {
      var rgb = valueArray[i].color.hexToRgb(true);
      var rgbdark = rgb.map(function(e) { return (e * .3) >> 0; });

      var lgradient = ctx.createLinearGradient(algnPos.x, algnPos.y + acum,
        algnPos.x + width -1, algnPos.y + acum + (valueArray[i].hvalue || 0));

      lgradient.addColorStop(0, rgb.rgbToHex());
      lgradient.addColorStop(0.5, rgb.rgbToHex());
      lgradient.addColorStop(1, rgbdark.rgbToHex());

      ctx.fillStyle = lgradient;
      ctx.fillRect(algnPos.x, algnPos.y + acum, width, valueArray[i].hvalue || 0);
    }
    ctx.restore();
  }
});

That code also uses linear gradients to render nice gradients for each stacked bar.

Pie Charts + TreeMaps = Awesome TreeMaps

When lots of elements need to be compared the Stacked Bar Chart visualization can be confusing. This is due to the fact that each bar gets thinner and the aspect ratio for each bar tends to be very high. I wrote about the aspect ratio problem some time ago, and I also showed that it could be solved by using Squarified TreeMaps to show hierarchical structures in constrained space.
This is OK for replacing Bar Charts, but what about Stacked Bar Charts? Should we subdivide each TreeMap cell into the number of stacked elements? I didn’t find that solution very appealing: for each TreeMap node its subnodes would have the same color, same name, but different values. It seems like redundant information.
Instead, I opted to create Pie Charts inside each TreeMap node. Pie Charts are useful to compare values where the whole information also has a meaning.

Here’s an example I did with the same data collected from the second Stacked Bar Chart image (click on the image to enlarge):



Each TreeMap cell is proportional to the amount of aggregate information for each element. The Pie Chart compares the specific information of each element.
While the previous example isn’t too useful, this next example collects more data and thus makes this visualization more suitable (also click to enlarge):



Implementation
By taking a look at this example we can see that we can make Pie Charts by using RGraphs and adding a special node rendering function. We also know that we can make Squarified TreeMaps by looking at this example.

So how can we combine these two visualizations?

The TreeMap visualization accepts a controller method that is triggered on element creation. This means that for each created treemap node a callback is used that can post-process each TreeMap node. This method is called onCreateElement and I use it to append a pie chart for each TreeMap element like this:

onCreateElement: function(content, node, isLeaf, leaf) {
  if(isLeaf && node.data.valueArray) {
    var w = leaf.offsetWidth, h = leaf.offsetHeight;
    //create a canvas with unique id
    //and append it to the leaf TreeMap element
    var c = new Canvas("piechartcanvas_" + TMPieWidget.count++, {
      injectInto: leaf,
      width: w,
      height: h - 2*tm.config.titleHeight
    });
    //create a RGraph with nodepie node rendering
    //function
    var rg = new RGraph(c, {
        Node: {
            'overridable': true,
             'type': 'nodepie'
        },
        Edge: {
            'overridable': true
        },
        //Parent-children distance
        levelDistance: ((w > h? h : w) / 2) - 2*tm.config.titleHeight,  

        //Add styles to node labels on label creation
        onCreateLabel: function(domElement, node){
            domElement.innerHTML = '';//node.name;
            if(node.data.$aw)
                domElement.innerHTML += " " + node.data.$aw;
            var style = domElement.style;
            style.fontSize = "0.8em";
            style.color = "#fff";
        },
        //Add some offset to the labels when placed.
        onPlaceLabel: function(domElement, node){
            var r = rg.graph.getNode(rg.root);
            var style = domElement.style;
            var dw = domElement.offsetWidth;
            if(r.data.count == 1) {
              var dh = domElement.offsetHeight;
              style.left = (w/2 - dw / 2) + 'px';
              style.top = (h/2 - dh) + 'px';
            } else {
              var left = parseInt(style.left);
              style.left = (left - dw / 2) + 'px';
            }
        }
    });
    rg.loadJSON(that.createJSONPie(node));
    rg.refresh();
  }
}

And that’s it!

I hope these customizations inspired you enough to create your own wacky visualizations with the JavaScript InfoVis Toolkit. I honestly encourage all Toolkit users to try to extend the library with new crazy ideas and features; most of the library design was targeted at that!

PS: Some people posted a job offer at the JavaScript InfoVis Toolkit Google Group that you might find useful. To check or post about job offerings related to visualization or the JavaScript InfoVis Toolkit please join the group!

Voronoi Tessellation

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!

Speaker at the Parisian Seminar on InfoVis and HCI

I’ve been invited by Fanny Chevalier from the Microsoft-INRIA Joint Centre to the Parisian Seminar on Information Visualization and HCI.

I’ll be speaking about Using Web Standards to create Interactive Data Visualizations for the Web. Here’s the abstract:

What is the best way to render complex information on the Web? The Document metaphor has been used for years in Web Standards to define the best way to show information on the Web. Today, Web Documents are turning into full fledged Web Applications and a Web Standards revolution is taking place to provide richer ways to present complex data. HTML is covering new patterns as Drag and Drop and 2D graphics; CSS is now covering transforms and animations, and JavaScript just got 100% faster. Web Standards are important because they are built natively in Web Browsers providing common functionality guidelines, independence from third-party libraries, and high interoperability with other Web components. The JavaScript InfoVis Toolkit is a toolkit for Information Visualization built solely on Web Standards. This Toolkit provides many visualization techniques to seamlessly integrate Interactive Data Visualizations in Web Pages, turning them into Web Applications. In this talk I’d like to present an overview of the new features in Web Standards and also some concepts behind the making of the JavaScript InfoVis Toolkit, as well as some user applications..

You can find more information about this talk and how to get there here. Everyone’s invited!

Sunburst Visualization

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 :)

Force Directed Layouts

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:

Force Directed Image

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.

MultiTrees (Part 1)

I found this CHI 94′ visualization paper on MultiTrees in the internet and I’ve been trying to see what type of applications and ideas I could “borrow” for the JavaScript InfoVis Toolkit.

What are MultiTrees?

A MultiTree is a type of directed acyclic graph (DAG) where each node has a tree both as parent structure and as descendants.

For example, a MultiTree can be created by overlapping different tree structures on a set of nodes, as shown in the picture below:

As you can see MultiTrees can have cycles if they’re not directed.

Laying and Navigating MultiTrees

What’s interesting about this structure is that if we take two nodes x and y such that x <= y and the path connecting them, then we can form a topological tree by adding all descendants and ancestors of each node belonging to that path in the new graph.

Implementation

I recently pushed support for a small subset of MultiTrees: those where x = y.
This is just a centered node and its tree of descendants and ancestors.

The tree navigation is the same as the SpaceTree:

I also implemented a way of changing the current focused node, so that when the clicked node is centered a centrifugal view from that node is adopted.
This way the current selected node is set as root of the visualization.
Hopefully you’ll understand the difference between this navigation and the previous one.

Anyway, as soon as I get this feature fully functional I’ll make another post explaining how to use this stuff in the JavaScript InfoVis Toolkit.

Outside In

While taking a look at some of the talks by Tamara Munzner I found this video/documentary about turning a sphere inside out.
I’ve found this to be very impressive (and pedagogic). The style of the video reminds me the Moebius Transformation video I posted last year.

For those who don’t know Tamara Munzner she’s like a big reference in all InfoVis-related stuff. One of the most inspiring InfoVis talks I’ve found was done by her and can be seen here. This is the talk that started my interest in InfoVis and the making of the JavaScript InfoVis Toolkit.

Drawing Trees

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:

  1. Two nodes at the same level should be placed at least a given distance apart.
  2. A parent should be centred over its offspring.
  3. Tree drawings should be symmetrical with respect to reflection—a tree and
    its mirror image should produce drawings that are reflections of each other. In
    particular, this means that symmetric trees will be rendered symmetrically.
  4. Identical subtrees should be rendered identically—their position in the larger
    tree should not affect their appearance.
  5. Trees should be as narrow as possible without violating these 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);
 };

More about the JavaScript InfoVis Toolkit 1.1

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.

Interactive Visualization of Genealogical Graphs

It’s been a while since I last bumped into a nice visualization project like this one.
It offers an advanced interface for exploring Genealogical graphs.

I personally like how nodes are hidden/shown in demand, how the subtree widget is implemented and how you can easily switch between different layouts.

On a side note, I’ve been screencasting the artist/band visualization project I made some time ago with the JavaScript InfoVis Toolkit, hope you find it interesting: it shows relations between artists and bands by collaborations in albums/songs/bands, etc.

You can access a live example here. I think its better rendered with Firefox, Safari, Opera and Chrome 2 (version 1.0.x has a bug).

The left menu offers some navigation options to choose a band as starting point. You can also find details about the focused band under the Details toggler.

Here’s a short video of what you should be able to see: