Force directed graphs

Force-directed graphs are still an experimental component of Paths.js. They work as advertised, but the performance is currently very bad. In the next iterations we will improve and optimize the layout algorithm, while leaving the API unchanged. In this way, graphs drawn today will still work, just with a smoother experience and possibly a nicer layout of nodes.

A graph is laid out with a physical simulation, where nodes repel each other, but nodes connected via links are attracted. The use of graphs is more complicated than other Paths.js APIs since we must be able to support server-side rendering, as well as client-side animations and drag and drop interaction.

The usage is as follows:

var Graph = require('paths/graph');
var graph = Graph({
  data: {
    nodes:[
      {id:"pippo"},
      {id:"pluto"},
      {id:"paperino"}
      {id:"qui"},
      {id:"quo"},
      {id:"qua"}
      {id:"nonna papera"},
      {id:"ciccio"}
    ],
    links:[
      {start:"pippo", end:"quo", weight:10},
      {start:"pippo", end:"qua", weight:30},
      {start:"pluto", end:"nonna papera", weight:10},
      {start:"pluto", end:"qui", weight:10},
      {start:"pluto", end:"quo", weight:10},
      {start:"paperino", end:"ciccio", weight:100},
      {start:"qui", end:"ciccio", weight: 20},
      {start:"quo", end:"ciccio", weight: 10},
      {start:"qua", end:"nonna papera", weight: 30}
    ]
  },
  compute: {
    color: function(i) { return somePalette[i]; }
  },
  nodeaccessor: function (x) { return x.id; },
  width: 500,
  height: 400,
  attraction: 1.1,
  repulsion: 1.3,
  threshold: 0.6
});

Parameters:

• width, height: have the obvious geometric meaning
• data: contains an object with nodes and links. The precise form of the data is not important, because the actual value of the data will be extracted by the node_accessor and link_accessor functions.
• nodeaccessor (optional, default identity): a function that is applied to each datum inside each item in data.nodes to extract its id.
• linkaccessor (optional, default identity): a function that is applied to each datum inside each item in data.links.
• attraction (optional, default 1): a physical parameter: increasing it will make the links stronger
• repulsion (optional, default 1): a physical parameter: increasing it will make nodes repel each other more strongly
• threshold (optional, default 0.5): a parameter between 0 and 1: higher values will lead to more accurate layouts but slower rendering
• compute (optional): see the introduction

nodes is a list of objects; each element in a list is an object from which we can extract an id with the node_accessor function. Ids should be unique to avoid wrong associations.

links is a list of objects. Applying the link_accessor function, we should extract something which contains a start and end properties (ids of nodes) and a weight,

The object returned by the Graph function contains two arrays curves and nodes. One can iterate on curves to draw the links and on nodes to draw the points. Each member of curves has the properties link, index, item, the latter containing the actual datum associated to the link. Each member of nodes has the properties point and item. You can add more properties by passing them within the compute object.

Finally, there is a significant difference between Graph and the other Paths.js APIs. A force-directed graph is meant to be animated, where the layout is computed in steps by a physical simulation. The object we have described above is static, but it has a method tick. The result of tick is the next step of the graph. An excerpt of its use in the demo application looks like:

var moving = true;
function step() {
  ractive.set({graph: graph.tick()});
  if (moving) requestAnimationFrame(step);
}

requestAnimationFrame(step);
setTimeout(function() { moving = false; }, 10000);

It makes use of Ractive.js, but it should be easy to understand: on each animation frame we update the graph using graph.tick and then render it.

If you make use of Graph on the server side, you will need to perform a number of ticks before returning the graph to display.

Graph objects also have to other methods, constrain and unconstrain. One can use graph.constrain(id, coordinates) to guarantee that the node represented by id will be stuck at coordinates regardless of the layout algorithm (starting from next tick), and graph.unconstrain(id) to release the node. This can be used to enable drag and drop of the nodes, as in this example:

var svgX, svgY = null; // coordinates of the SVG frame
var following = null;
ractive.on('constrain', function(event) { // runs on mousedown
  moving = true;
  target = event.original.target;
  svgX = event.original.clientX - target.cx.baseVal.value;
  svgY = event.original.clientY - target.cy.baseVal.value;
  following = event.index.num // node id
  requestAnimationFrame(step); // reenable the animation if it was stopped
}

ractive.on('move', function(event) { // runs on mousemove
  if (!following) return null;
  if (event.original.button != 0) return null;
  coordinates = [event.original.clientX - svgX, event.original.clientY - svgY];
  graph.constrain(following, coordinates);
}

ractive.on('unconstrain', function(event) { // runs on mouseup
  graph.unconstrain(following);
  following = null;
  setTimeout(function() { moving = false; }, 10000);
}