How to layout a non-tree hierarchy with D3

Question

D3 has a variety of layouts for directed graphs that are strict trees, such as the following:

A
|\
B C
 / \
D   E

I need to draw a hierarchy of nodes that is not a tree, but is a directed acyclic graph. This is a problem for a tree layout, because several of the branches converge:

A
|\
B C
 \|
  D

Does anyone know of a D3 layout for general hierarchies? Or alternatively, some clever hack to the existing treelayout? I've noticed GraphVis handles this situation well, but D3 produces a graph that better suits the requirements here.

Answer 1

I was able to do this using a combination of Dagre(https://github.com/dagrejs/dagre) and cytoscape

There's a library called Dagre-D3 that you can use as a renderer for this library so it looks like the D3 solution you want.

Check out this fiddle to see the basic implementation with Dagre and Cytoscape: https://jsfiddle.net/KateJean/xweudjvm/

var cy = cytoscape({
  container: document.getElementById('cy'),
  elements: {
          nodes: [
            { data: { id: '1' } },
            { data: { id: '2' } },
            { data: { id: '3' } },
            { data: { id: '4' } },
            { data: { id: '5' } },
            { data: { id: '6' } },
            { data: { id: '7' } },
            { data: { id: '8' } },
            { data: { id: '9' } },
            { data: { id: '10' } },
            { data: { id: '11' } },
            { data: { id: '12' } },
            { data: { id: '13' } },
            { data: { id: '14' } },
            { data: { id: '15' } },
            { data: { id: '16' } },
            { data: { id: '17' } },
            { data: { id: '18' } }
          ],
          edges: [
            { data: { source: '1', target: '2' } },
            { data: { source: '1', target: '3' } },
            { data: { source: '2', target: '4' } },
            { data: { source: '4', target: '5' } },
            { data: { source: '4', target: '6' } },
            { data: { source: '5', target: '6' } },
            { data: { source: '5', target: '7' } },
            { data: { source: '7', target: '8' } },
            { data: { source: '3', target: '9' } },
            { data: { source: '3', target: '10' } },
            { data: { source: '10', target: '11' } },
            { data: { source: '11', target: '12' } },
            { data: { source: '12', target: '13' } },
            { data: { source: '12', target: '14' } },
            { data: { source: '14', target: '15' } },
            { data: { source: '15', target: '16' } },
            { data: { source: '16', target: '17' } },
            { data: { source: '16', target: '18' } }

          ]
        },
  layout: {
    name: "dagre",
    rankDir: 'TB' //love this. you can quickly change the orientation here from LR(left to right) TB (top to bottom), RL, BT. Great dropdown option for users here. 
  },
  style: [{
    selector: 'node',
    style: {
      'label': 'data(id)',
      'width': '30%',
      'font-size': '20px',
      'text-valign': 'center',
      'shape': 'circle',
      'background-color': 'rgba(113,158,252,1)', 
      'border': '2px grey #ccc'
    }
  }, {
    selector: 'edge',
    style: {
      'width': 2,
      'line-color': '#ccc',
      'target-arrow-color': '#ccc',
      'target-arrow-shape': 'triangle'
    }
  }]
});

Answer 2

As this example: "Force Directed Trees" illustrates there is a trick that often works. In the example the force direction's behavior is adjusted on each tick so that nodes drift slightly up or down depending on the direction of the links. As shown this will do a fine job for trees, but I've found it also works tolerable well for acyclic graphs. No promises, but it may help.

Answer 3

You could create your own code without having to rely on a D3 layout in order to get it done.

I've provided an example in a jsFiddle. The example is pretty simplistic and would need to be worked a little bit to accommodate more complex examples.

The example could be re-worked to process hierarchical data as well with relatively little effort.

Here is the code I have used in the jsFiddle:

 // Sample data set
var json = {
    nodes: [{
        name: 'A'},
    {
        name: 'B'},
    {
        name: 'C'},
    {
        name: 'D'}],
    links: [{
        source: 'A',
        target: 'B'},
    {
        source: 'A',
        target: 'C'},
    {
        source: 'B',
        target: 'D'},
    {
        source: 'C',
        target: 'D'}
                                                                                   ]

};

var vis = d3.select('#vis').attr('transform', 'translate(20, 20)');

// Build initial link elements - Build first so they are under the nodes
var links = vis.selectAll('line.link').data(json.links);
links.enter().append('line').attr('class', 'link').attr('stroke', '#000');

// Build initial node elements
var nodes = vis.selectAll('g.node').data(json.nodes);
nodes.enter().append('g').attr('class', 'node').append('circle').attr('r', 10).append('title').text(function(d) {
    return d.name;
});

// Store nodes in a hash by name
var nodesByName = {};
nodes.each(function(d) {
    nodesByName[d.name] = d;
});

// Convert link references to objects
links.each(function(link) {
    link.source = nodesByName[link.source];
    link.target = nodesByName[link.target];
    if (!link.source.links) {
        link.source.links = [];
    }
    link.source.links.push(link.target);
    if (!link.target.links) {
        link.target.links = [];
    }
    link.target.links.push(link.source);
});

// Compute positions based on distance from root
var setPosition = function(node, i, depth) {
    if (!depth) {
        depth = 0;
    }
    if (!node.x) {
        node.x = (i + 1) * 40;
        node.y = (depth + 1) * 40;
        if (depth <= 1) {
            node.links.each(function(d, i2) {
                setPosition(d, i2, depth + 1);
            });
        }

    }

};
nodes.each(setPosition);

// Update inserted elements with computed positions
nodes.attr('transform', function(d) {
    return 'translate(' + d.x + ', ' + d.y + ')';
});

links.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;
});

Answer 4

Speaking generally of trees and the data hierarchy, you just need to have "D" in the children list for both B and C.

Creating your node list, make sure you have a unique id returned so that "D" doesn't appear twice.

vis.selectAll("g.node").data(nodes, function(d) { return d.id; });

Then when you call

var links = tree.links(nodes)

you should get D appearing as the "target" twice (with B and C as the "source" respectively) which results in two lines to the single node "D".