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.

You might want to have a look at the force directed graph layout. — Christopher Chiche, Apr 09 '13 at 05:45

score 18 · Answer 1 · answered Jul 17 '12 at 18:25

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

Thanks for the example, Phil! I ended up doing something very similar. It turns out the layout algorithm I really wanted was implemented in GraphViz. It has python bindings, but they don't work. Instead I did the following: 1) Form graph into DOT language (http://www.graphviz.org/content/dot-language) 2) Pass graph to graphviz's dot command via commandline, which does the layout and puts (x,y) coordinates into DOT 3) Reformat DOT into javascript objects, embed into page 4) Use D3 to place nodes according to (x,y) coordinates in DOT. This works really well with very large graphs. — John Walthour, Jul 23 '12 at 14:35

score 9 · Answer 2 · answered Jun 25 '13 at 16:45

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.

score 1 · Answer 3 · answered Jul 11 '12 at 22:18

1

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

answered Jul 11 '12 at 22:18

Glenn

5,334
4
28
31

I was able to get the tree assembled in the manner you describe, but the TreeLayout doesn't seem to be able to handle it. There is a chance I screwed that up somehow; have you had luck getting a layout to run this way? In the meantime, I've managed a pretty suitable workaround using GraphViz on the server side. GraphViz will do a nice hierarchical layout and output in DOT format with (x,y) positions for each node. From there, it's relatively easy to package that information into the page and draw it using D3. Thanks for your help, I appreciate the effort! – John Walthour Jul 16 '12 at 12:30
I played around with it and it was pretty crazy. Depending on the parent it would sometimes fail inside d3: "vom is undefined: 6444" and other times it would render, but put the child in an ugly spot. So short answer is, you're right. The tree layout in the case is the problem. – Glenn Jul 16 '12 at 21:45

score 0 · Answer 4 · answered Aug 29 '18 at 22:18

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'
    }
  }]
});

How to layout a non-tree hierarchy with D3

4 Answers4

Linked