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