如何使用D3对非树形层次结构进行布局

Question

D3有多种针对严格树形结构的有向图布局，例如以下内容：

A
|\
B C
 / \
D   E

我需要绘制一个非树形结构的节点层次图，而是一个有向无环图。这对于树形布局来说是一个问题，因为几个分支会汇聚：

A
|\
B C
 \|
  D

有人知道D3通用层次结构布局吗？或者，对现有的树形布局进行一些巧妙的 hack？我注意到GraphVis 处理这种情况得很好，但是在这里，D3产生了更适合要求的图形。

- John Walthour

---

你可能想要查看力导向图布局。 - Christopher Chiche

Answer 1

你可以自己编写代码，而不必依赖D3布局来完成它。

我在 jsFiddle中提供了一个示例。这个例子非常简单，需要进行一些修改才能适应更复杂的情况。

这个例子也可以相对轻松地重新处理层次数据。

以下是我在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;
});

- Phil Laliberte

---

谢谢你的例子，Phil！我最终做了非常相似的事情。原来我真正想要实现的布局算法是在Graphviz中实现的。它有Python绑定，但它们不能用。于是我做了以下几步：1）将图形转换为DOT语言（http://www.graphviz.org/content/dot-language） 2）通过命令行将图形传递给Graphviz的dot命令，该命令进行布局并将（x，y）坐标放入DOT中 3）重新格式化DOT为JavaScript对象，并嵌入页面 4）使用D3根据DOT中的（x，y）坐标放置节点。这对于非常大的图形效果非常好。 - John Walthour

Answer 2

正如这个例子所展示的: "力导向树"，有一个经常奏效的技巧。在这个例子中，每次tick时调整力导向的行为，以便节点根据链接的方向稍微向上或向下漂移。正如所示，这对于树来说做得很好，但我发现它对于非循环图也能够容忍地奏效。不能保证，但可能会有所帮助。

- Ben Hyde

Answer 3

一般来说，谈到树和数据层次结构，你只需要在B和C的子节点列表中加入“D”。

创建节点列表时，请确保返回唯一的ID，以便“D”不会出现两次。

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

当您拨打电话时

var links = tree.links(nodes)

你应该看到 D 两次出现作为“目标”（分别与 B 和 C 作为“源”），这将导致两条线汇聚到单个节点“D”。

- Glenn

---

我已经按照你所描述的方式成功组装了树形结构，但是 TreeLayout 似乎无法处理它。我有可能在某些方面搞砸了；你能否尝试一下这种布局方式，看看是否能够成功呢？与此同时，我在服务器端使用 GraphViz 找到了一个相当适合的解决方法。GraphViz 能够提供漂亮的分层布局，并输出带有每个节点 (x,y) 位置的 DOT 格式。从那里，将该信息打包并使用 D3 进行绘制就相对容易了。感谢你的帮助，我非常感激！ - John Walthour

我尝试了一下，感觉非常疯狂。根据父级的不同，有时会在d3内部失败：“vom未定义：6444”，而其他时候则会呈现，但将子项放在一个丑陋的位置。所以简短的答案是，你是对的。在这种情况下，树形布局是问题所在。 - Glenn

Answer 4

我能够使用Dagre（https://github.com/dagrejs/dagre）和cytoscape的组合完成这个。

有一个叫做Dagre-D3的库，你可以用它作为这个库的渲染器，这样它看起来就像你想要的D3解决方案。

查看这个fiddle，了解使用Dagre和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'
    }
  }]
});

- KateJean