Bookmark with del.icio.us submit Tutorial%3A%20Building%20a%20Force%20Directed%20Graph%20from%20XML digg.com reddit

Tutorial: Building a Force Directed Graph from XML

Part of my upcoming talk at The Ajax Experience is, of course, about graph-based data visualizations using JSViz. I've worked up a couple of tutorials using the new JSViz 0.3.1 and I'm sharing abbrieviated versions of them here. Conference attendees should find these posts useful as a recap and additional reference for coding your own apps.

In this first tutorial, we'll introduce the JSViz 0.3.1 API by modeling the contents of an XML file. The model will render in HTML or SVG if it's available. Of course you can take a look at what we're building before we get started:

Screenshot of SVG | Screenshot of HTML | "Live" Example | Hide


Create an HTML File and Import JSViz Files

<html>
  <head>
    <title>JSViz Demo: Modeling XML Data</title>

    
    <!-- JSViz Libraries -->
    <script language="JavaScript" src="DataGraph.js"></script>
    <script language="JavaScript" src="Magnet.js"></script>
    <script language="JavaScript" src="Spring.js"></script>
    <script language="JavaScript" src="Particle.js"></script>
    <script language="JavaScript" src="ParticleModel.js"></script>
    <script language="JavaScript" src="Timer.js"></script>
    <script language="JavaScript" src="EventHandler.js"></script>
    <script language="JavaScript" src="HTMLGraphView.js"></script>
    <script language="JavaScript" src="SVGGraphView.js"></script>
    <script language="JavaScript" src="RungeKuttaIntegrator.js"></script>
    <script language="JavaScript" src="Control.js"></script>

    <!-- Demo Libraries -->
    <script language="JavaScript" src="HTTP.js"></script>
    <script language="JavaScript" src="XMLLoader.js"></script>

    <script>
      function init() {

      }
    </script>
    
    <style type="text/css">
      html {
        filter: expression(document.execCommand("BackgroundImageCache", false, true));
      }

      body {
        margin: 0;
        padding: 0;
      }
    </style>

  </head>
  <body onload="init()">

  </body>
</html>

Identifying Nodes and Relationships

First, let's check out the XML file that contains the data we're going to model.

The file contains a simple XML hierarchy that indicates the relationships in our model. Each node in the graph will be a descendant of "root" and any node may have child nodes. Each node explicitly indicates the mass and color that should be used to represent it in the model. While this XML file defines our graph structure explictly, you may have XML or other data that doesn't. The first step in using JSViz is to process your data into a "DataGraph", where we define the nodes and relationships that we're going to model.

Here I've created a simple XMLLoader that will grab the XML, parse it, and populate our DataGraph.

Whether you're retrieving data from an XML file or REST service, you'll need to write some kind of "loader" to populate your DataGraph. Don't hesitate to extend DataGraphNode with any attributes (images, labels, etc.) that may be used to render a node's representation in your model.

Setting up our Model

Now we have all the tools we need to build our model. Let's get modelling! Earlier we created an HTML file, containing an empty init() function. Now we're going to populate it:

Get the width and height of our document. We'll use these to keep the nodes in our graph on the page. If you're going to render your graph inside an HTML element (a div or table, etc.), you should instead use the dimensions of that element.

var FRAME_WIDTH;
var FRAME_HEIGHT;

if (document.all) {
  FRAME_WIDTH = document.body.offsetWidth - 5;
  FRAME_HEIGHT = document.documentElement.offsetHeight - 5;
} else {
  FRAME_WIDTH = window.innerWidth - 5;
  FRAME_HEIGHT = window.innerHeight - 5;
}

Make a view to control the presentation of our model. We'll use SVG wherever it's supported and use HTML where it's not.

var view;
if ( document.implementation.hasFeature("org.w3c.dom.svg", '1.1') ) {
  view = new SVGGraphView( 0, 0, FRAME_WIDTH, FRAME_HEIGHT );
} else {
  view = new HTMLGraphView( 0, 0, FRAME_WIDTH, FRAME_HEIGHT );
}

Create a ParticleModel that will drive animated positioning of Particles in our model. The ParticleModel contains an animation timer that we can start and stop when appropriate. There aren't any particles in our model yet, but it's ok to start it up now.

var particleModel = new ParticleModel( view );
particleModel.start();

A set of basic user controls that handle drag-and-drop of particles and window resizing is provided. Most interactive applications will extend this to provide a richer user experience.

var control = new Control( particleModel, view );

Next we initialize the DataGraph that we discussed above and create a NodeHandler. We're going to code our own NodeHandler below so we'll talk more about it in a moment.

var dataGraph = new DataGraph();
var nodeHandler = new NodeHandler( dataGraph, particleModel, view, control );
dataGraph.subscribe( nodeHandler );

Initialize the XMLLoader and instruct it to load a file.

var xmlLoader = new XMLLoader( dataGraph );
xmlLoader.load( "nodes.xml" );

In this demo, we're going to add nodes over time, enabling the model to organize under less entropy. The build timer will add 1 node every 150ms.

var buildTimer = new Timer( 150 );
buildTimer.subscribe( nodeHandler );
buildTimer.start();

Phew! We're almost done. We just covered all of the contents of the init() function but we still need to implement a NodeHandler to tell our model and view how to interpret the nodes and relationships in the DataGraph.

Controlling Model and View behavior with a NodeHandler

The NodeHandler is where everything comes together. It interprets the DataGraph to determine how to model and present the graph. In this example, we also pass in the "control" defined above because it contains some event handlers that we'll attach to view elements.

var NodeHandler = function( dataGraph, particleModel, view, control ) {
  this.dataGraph = dataGraph;
  this.particleModel = particleModel;
  this.view = view;
  this.control = control;
  this.queue = new Array();

This NodeHandler observes a DataGraph. It must implement some functions to be notified of new nodes and relationships.

this['newDataGraphNode'] = function( dataGraphNode ) {
  this.enqueueNode( dataGraphNode );						
}

this['newDataGraphEdge'] = function( nodeA, nodeB ) {
  // Empty. We learn everything we need from newDataGraphNode()
}

This NodeHandler queues nodes for additon to the model. An external timer instructs it to dequeue nodes periodically.

this['enqueueNode'] = function( dataGraphNode ) {
  this.queue.push( dataGraphNode );
}

this['dequeueNode'] = function() {
  var node = this.queue.shift();
  if ( node ) {
    this.addParticle( node );						
  }
}

this.update = function() {
  this.dequeueNode();
}

Finally, we're about to implement the function that adds particles to our model and constructs the presentation. This one is big so I'm placing comments throughout.

this['addParticle'] = function( dataGraphNode ) {
  // Create a particle to represent this data node in our model.
  particle = this.particleModel.makeParticle( dataGraphNode.mass, 0, 0 );

  // Create view for SVG
  if ( document.implementation.hasFeature("org.w3c.dom.svg", '1.1') ) {
    var bubble = document.createElementNS("http://www.w3.org/2000/svg", "circle");
    bubble.setAttribute('stroke', '#888888');
    bubble.setAttribute('stroke-width', '.25px');
    bubble.setAttribute('fill', dataGraphNode.color);
    bubble.setAttribute('r', 6 + 'px');
    bubble.onmousedown =  new EventHandler( control, control.handleMouseDownEvent, particle.id )
    var viewNode = this.view.addNode( particle, bubble );

    // Create view for HTML
  } else {
    var bubble = document.createElement( 'div' );
    bubble.style.position = "absolute";
    bubble.style.width = "12px";
    bubble.style.height = "12px";
						
    var color = dataGraphNode.color;
    color = color.replace( "#", "" );

    bubble.style.backgroundImage = "url(/cgi-bin/bubble.pl?title=&r=12&pt=8&b=888888&c=" + color + ")";

    bubble.innerHTML = '';
    bubble.onmousedown =  new EventHandler( control, control.handleMouseDownEvent, particle.id )
    var viewNode = this.view.addNode( particle, bubble );
  }

  // Determine if this particle's position should be fixed.
  if ( dataGraphNode.fixed ) { particle.fixed = true; }

  // Assign a random position to the particle.
  var rx = Math.random()*2-1;
  var ry = Math.random()*2-1;
  particle.positionX = rx;
  particle.positionY = ry;

  // Add a Spring Force between child and parent
  if ( dataGraphNode.parent ) {
    particle.positionX = dataGraphNode.parent.particle.positionX + rx;
    particle.positionY = dataGraphNode.parent.particle.positionY + ry;
    particleModel.makeSpring( particle, dataGraphNode.parent.particle, .2, .2, 10 );
    var props;
    if ( document.implementation.hasFeature("org.w3c.dom.svg", '1.1') ) {
      props = {
        'stroke': dataGraphNode.parent.color,
        'stroke-width': '2px',
        'stroke-dasharray': '2,4'
      }
    } else {
      props = {
        'pixelColor': dataGraphNode.color,
        'pixelWidth': '2px',
        'pixelHeight': '2px',
        'pixels': 5
      }
    }

    this.view.addEdge( particle, dataGraphNode.parent.particle, props );
  }

  // Add repsulsive force between this particle and all other particle.
  for( var j=0, l=this.particleModel.particles.length; j<l; j++ ) {
    if ( this.particleModel.particles[j] != particle ) {
      this.particleModel.makeMagnet( particle, this.particleModel.particles[j], -2000, 10 );
    }
  }

  dataGraphNode.particle = particle;

  // Set a width and height for this particle for bounds checking
  particle.width=12;
  particle.height=12;

  dataGraphNode.viewNode = viewNode;
  return dataGraphNode;
},

Got all that? There's a lot to do when we add a particle to the system. Make sure you remember the closing brace on NodeHandler.

}

We're all done! We've created a force directed graph from the contents of an XML file.

I'll be covering this tutorial and a lot more, in depth, in a little over a week at The Ajax Experience. I'll post again shortly with another tutorial from this talk. Please comment with any questions or to show us your work. Thanks!

Check out the final product.

Trackback

Listed below are links to weblogs that reference Tutorial: Building a Force Directed Graph from XML:

» Force Directed Graphs with JavaScript from Metaportal der Medienpolemik
kylescholz.com presents Force Directed Graphs with JavaScript. [Read More]

» Modeling Music Recommendations in JavaScript with JSViz from kylescholz.com :: blog
Last week I showed you a tutorial that I put together for The Ajax Experience, where we built a force directed model from the contents of an XML file. Today I'm presenting an example with full source from another... [Read More]

Comments

thanks a lot for this Post, i will try to use this... I will say to you about it next time !

IN THE TUTORIAL it says to use http.js (demo library) but i didn't find it ion your downloads. where can I find itdo you have a zip file of the entire project /web page so I could try it in my own enviroment without cut and paste from the site?

Hi Paie,
you can download HTTP.js from here obviously:
http://www.kylescholz.com/projects/speaking/tae2006/xml/HTTP.js

Kyle,
Thank you so much from that lib, I'm starting integrating it into my new social site called http://www.livetribune.org (to be up very soon). Especially, serving XML data with RHTML seems very easy. I was thinking actually about facing extremely hard C++ programming to produce my graph layouts from the server side (it couldn't be done in Ruby because it would have generated a lot of overhead under heavy load), but letting the clients use their CPU at layouting in such a sexy way is rather temptating... Are you still making some progress? Are you still willing to maintain your work for some time? Would you mind if I redistribute your work under the same license but merged into one single javascript file in order to speed up the download? Best Regards.

Raphaël Valyi from Paris.

Raphaël,

Thanks for the compliments! I'm continuing to build on JSViz and will unveil a development roadmap and new project website shortly. I also hope to provide some better tools to help JSViz users contribute to the project. Feel free to create a bundled JSViz package. I get a lot of requests for this so I'll bet a lot of others will appreciate your work. Please send me a copy or a link and I'll post a copy on my site, too. Thanks!

I can't get this to work for me. I get

Warning: Unknown property 'filter'. Declaration dropped.
Source File: http://localhost/
Line: 252

and

Error: this.container.appendChild is not a function
Source File: http://localhost/SVGGraphView.js
Line: 61

Is there something else I need?

Exactly, what i was searching for. thx

Post a Comment

(optional)
(optional)