d3.js: using layout.force to plot tree graphs (where nodes may have multiple parents) - Part 1: pure tree

Experiment …… ∆ ∞

Constructing a tree view using the d3.layout.force

This is prelude to constructing tree-like graphs using the force layout.

Lessons learned

when coding constraints which are really strict, e.g. binding a certain node or set of nodes to a specific y coordinate (node.depth ~ y position in a vertical tree), it is opportune to 'insinuate' the constraint rather than enforce it, i.e. you should apply the constraint as if it was a force, i.e. verlet-integrate the delta, using the tick.alpha strength. Of course nothing stops you from strengthening the applicatiuon of the constraint when the alpha value is near zero (i.e. we're almost stable/at the end of the force iteration).
you can edit both .x/.y and .px/.py in the tick handler, but any 'force-like' constraints should best be applied to the .px/.py components as then they will mix with the repulse and verlet integration logic in the next round.
given the two items above, it is opportune to code a constraint like 'stay within visible area' as a dual constraint: one which clips the x/y node coordinates to ensure they stick within the visible area, and a second part which is a 'force' applied to repulse any nodes close to the edge(s): if you don't do the latter, you'll get graph views where a lot of nodes hug the edge(s) and don't resolve themselves to move back into the visible area proper. (Drag any graph to the edge with such a constraint and you're getting a very jittery graph where a lot of the nodes bounce against the edges but don't 'move away'. That's why you need such a second 'repulse force' to make this happen and make the graph look good, even when dragged near the edge.

Implementation Nodes, er, Notes

All constraints are applied in the force.on("tick") event handler.

We also implement drag behaviour, which, like any other use of node.fixed, will add a .px/.py coordinate pair for each node under the hood. To prevent any 'Crazy Ivan jumping' of nodes and other unexpected behaviour, we must ensure that .x/.y and .px/.py match once we are done in the force.tick handler, otherwise the next mouseenter/drag will behave very oddly. It is always a good rule to set both .px/.py and .x/.y when you update force nodes' x/y coordinates.

This example is derived off the D3 example examples/force/force-collapsible.html.

The code requires a D3 version which includes (pull request #803](https://github.com/mbostock/d3/pull/803).

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=utf-8">
    <title>Force-Directed Graph: Collapsible, Hierarchical</title>
    <script src="readme.js"></script> 
    <style type="text/css">

circle.node {
  cursor: pointer;
  stroke: #000;
  stroke-width: .5px;
}

line.link {
  fill: none;
  stroke: #9ecae1;
  stroke-width: 1.5px;
}

</style>
  </head>
  <body>
    <div id="chart"></div>

var width = 960,
    height = 500,
    node,
    link,
    root;

var force = d3.layout.force()
    .on("tick", tick)
    .charge(function(d) {
      return d._children ? -d.size / 100 : d.children ? -100 : -30;
    })
    .linkDistance(function(d) {
      return d.target._children ? 50 : 30;
    })
    .size([width, height]);

var vis = d3.select("#chart").append("svg")
    .attr("width", width)
    .attr("height", height);

d3.json("flare.json", function(json) {
  root = json;
  root.fixed = true;
  root.px = root.py = 0;
  update();
});

function update(nodes) {
  var nodes = flatten(root);
  var links = d3.layout.hierarchy().links(nodes);

// make sure we set .px/.py as well as node.fixed will use those .px/.py to 'stick' the node to:
  if (!root.px) {
    // root have not be set / dragged / moved: set initial root position
    root.px = root.x = width / 2;
    root.py = root.y = circle_radius(root) + 2;
  }

// Restart the force layout.
  force
      .nodes(nodes)
      .links(links)
      .start();

// Update the links…
  link = vis.selectAll("line.link")
      .data(links, function(d) { return d.target.id; });

// Enter any new links.
  link.enter().insert("line", ".node")
      .attr("class", "link")
      .attr("x1", function(d) { return d.source.x; })
      .attr("y1", function(d) { return d.source.y; })
      .attr("x2", function(d) { return d.target.x; })
      .attr("y2", function(d) { return d.target.y; });

// Exit any old links.
  link.exit().remove();

// Update the nodes…
  node = vis.selectAll("circle.node")
      .data(nodes, function(d) { return d.id; })
      .style("fill", color);

node.transition()
      .attr("cy", function(d) { return d.y; })
      .attr("r", function(d) { return circle_radius(d); });

// Enter any new nodes.
  node.enter().append("circle")
      .attr("class", "node")
      .attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; })
      .attr("r", function(d) { return circle_radius(d); })
      .style("fill", color)
      .on("click", click)
      .call(force.drag);

// Exit any old nodes.
  node.exit().remove();
}

function tick() {
  // Apply the constraints:
  //
  force.nodes().forEach(function(d) {
    if (!d.fixed) {
      var r = circle_radius(d) + 4, dx, dy, ly = 30;

// #1: constraint all nodes to the visible screen:
      //d.x = Math.min(width - r, Math.max(r, d.x));
      //d.y = Math.min(height - r, Math.max(r, d.y));

// #1.0: hierarchy: same level nodes have to remain with a 1 LY band vertically:
      if (d.children || d._children) {
        var py = 0;
        if (d.parent) {
          py = d.parent.y;
        }
        d.py = d.y = py + d.depth * ly + r;
      }

// #1a: constraint all nodes to the visible screen: links
      dx = Math.min(0, width - r - d.x) + Math.max(0, r - d.x);
      dy = Math.min(0, height - r - d.y) + Math.max(0, r - d.y);
      d.x += 2 * Math.max(-ly, Math.min(ly, dx));
      d.y += 2 * Math.max(-ly, Math.min(ly, dy));
      // #1b: constraint all nodes to the visible screen: charges ('repulse')
      dx = Math.min(0, width - r - d.px) + Math.max(0, r - d.px);
      dy = Math.min(0, height - r - d.py) + Math.max(0, r - d.py);
      d.px += 2 * Math.max(-ly, Math.min(ly, dx));
      d.py += 2 * Math.max(-ly, Math.min(ly, dy));

// #2: hierarchy means childs must be BELOW parents in Y direction:
      if (d.parent) {
        d.y = Math.max(d.y, d.parent.y + ly);
        d.py = Math.max(d.py, d.parent.py + ly);
      }
    }
  });

link.attr("x1", function(d) { return d.source.x; })
      .attr("y1", function(d) { return d.source.y; })
      .attr("x2", function(d) { return d.target.x; })
      .attr("y2", function(d) { return d.target.y; });

node.attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; });
}

// Color leaf nodes orange, and packages white or blue.
function color(d) {
  return d._children ? "#3182bd" : d.children ? "#c6dbef" : "#fd8d3c";
}

function circle_radius(d) {
  return d.children ? 4.5 : Math.sqrt(d.size) / 10;
}

// Toggle children on click.
function click(d) {
  if (d.children) {
    d._children = d.children;
    d.children = null;
  } else {
    d.children = d._children;
    d._children = null;
  }
  update();
}

// Returns a list of all nodes under the root.
//
// Also assign each node a reasonable starting x/y position: we can do better than random placement since we're force-layout-ing a hierarchy!
function flatten(root) {
  var nodes = [], i = 0, depth = 0, level_widths = [1], max_width, max_depth = 1, kx, ky;

root.size = recurse(root, null, 0);

// now correct/balance the x positions:
  max_width = 1;
  for (i = level_widths.length; --i > 0; ) {
    max_width = Math.max(max_width, level_widths[i]);
  }
  kx = (width - 20) / max_width;
  ky = (height - 20) / max_depth;
  for (i = nodes.length; --i >= 0; ) {
    var node = nodes[i];
    if (!node.px) {
      node.y *= ky;
      node.y += 10 + ky / 2;
      node.x *= kx;
      node.x += 10 + kx / 2;
    }
  }

return nodes;
}

</script>
  </body>
</html>

Modified http://gerhobbelt.github.com/bl.ocks.org-hack/fixit.js to a secure url

https://gerhobbelt.github.com/bl.ocks.org-hack/fixit.js