d3.js: using tree layout for graphs which have nodes with multiple 'parents'

Experiment …… ∆ ∞

How do I draw a tree, when my nodes may have multiple parents?

This question gets asked repeatedly about drawing/layout-ing 'trees', i.e. 'hierarchies' where it is then mentioned that nodes do have 'multiple parents'.

This would, of course, make these structures graphs rather than trees, but the fact they start with mentioning 'tree' hints at what sort of display is sought, and this does not come naturally when you use a vanilla d4.layout.force.

Can I do this with d3.layout.hierarchy? Which d3.layout do I use for this?

All the hierarchical layouts available in D3 require a hierarchy, that is a structure where every node has a single parent. Of course, some brutal hacking, e.g. duplication of partial trees to convert multi-parent to many times the same with single parent, can be applied, but it might be a much better option to use a true graph layout mechanism, such as d3.layout.force, and apply the proper constraints to make it do what you want.

Here we show a vertical force layout, which is constructed by applying a force layout to the graph structure, plus constraining the nodes in the vertical direction (y) depending on their 'depth' a.k.a. 'level'.

Caveats

The 'level' is determined by traversing the graph and calculating the maximum depth for each node, where 'maximum depth' for a node is defined as the largest depth number assigned to any of its direct parents, incremented by one. The 'root' node(s) are assigned a depth of 1.

The traversal mechanism will run ad infinitum when the graph contains cycles, so you must ensure that no cycles exist (as in real life, you can't be your own granpa ;-) )

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