javascript 使用没有 DOT 的 d3.js 的有向无环图

Directed acyclic graph using d3.js without DOT

提问by A.G.

I am trying to draw directed acyclic graph using d3.js. While searching for the layout, I came across Dagrebut it seems to be of less use as I do not want to use DOT based code anywhere. If anyone knows about pure Javascript solution for this or plugin/custom layout for DAG, please let me know. Thanks in advance.

我正在尝试使用 d3.js 绘制有向无环图。在搜索布局时，我遇到了Dagre，但它似乎用处不大，因为我不想在任何地方使用基于 DOT 的代码。如果有人知道此的纯 Javascript 解决方案或 DAG 的插件/自定义布局，请告诉我。提前致谢。

回答by Chris Pettitt

Dagre author here. Dagre doesn't include any of the graphviz code - it is pure JavaScript. It is based on similar layout techniques though; both are based on techniques from the Sugiyama paper.

达格作者在这里。Dagre 不包含任何 graphviz 代码——它是纯 JavaScript。不过，它基于类似的布局技术；两者都基于 Sugiyama 论文中的技术。

You can find some examples of dagre here:

你可以在这里找到一些 dagre 的例子：

http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.htmlhttp://cpettitt.github.io/project/dagre-d3/latest/demo/sentence-tokenization.htmlhttp://cpettitt.github.io/project/dagre-d3/latest/demo/tcp-state-diagram.html

http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html http://cpettitt.github.io/project/dagre-d3/latest/demo/sentence-tokenization.html http://cpettitt.github.io/project/dagre-d3/latest/demo/tcp-state-diagram.html

The minified source can be found here: http://cpettitt.github.io/project/dagre-d3/latest/dagre-d3.min.js. It clocks in at about 44K.

缩小后的源代码可以在这里找到：http: //cpettitt.github.io/project/dagre-d3/latest/dagre-d3.min.js。它的时钟频率约为 44K。

回答by Sebastian

Rendering directed acyclic graphs (and actually highlighting the directedness property) is a domain of the Sugiyamalayout algorithms.

渲染有向无环图（实际上突出了有向性）是Sugiyama布局算法的一个领域。

They basically assign layers (through a topological sorting) to the nodes and then calculate a sequencing for the nodes in the layers. Using a simple heuristic to reverse cycles first, this works well for cyclic graphs as well. Graphviz DOT has an implementation of this layout called dot, which is also the name of the file format it uses, so there sometimes is a bit confusion when DOT is mentioned.

他们基本上为节点分配层（通过拓扑排序），然后计算层中节点的排序。首先使用简单的启发式方法来反转循环，这也适用于循环图。Graphviz DOT 有一个名为dot 的布局实现，这也是它使用的文件格式的名称，所以在提到 DOT 时有时会有点混乱。

Of course there are other implementations of the algorithm, even a cross-compiled Javascript version of dot is available. The probably most feature-complete solution available for Javascript is the commercial implementation of the algorithm in the yFileslibrary. So if this is in a commercial scenario, you might want to take a look at the corresponding live demo. Note that although yFiles comes with its own rendering and editor implementation, you could still plug the code into d3.js, since the layout algorithms can be used as standalone implementations to "just" calculate the coordinates of the nodes, the edge connection points, the bends, and the labels. This specific implementation supports a great number of additional constraints, like "Port Constraints" (to restrict the direction of the outgoing and incoming edges as well as their exact locations at the nodes), hierarchically grouped nodes (where each node can have a parent node and the parent node "contains" all of its child nodes), layer and sequence constraints, edge labeling constraints, different edge routing styles, bus-routing, and more.

当然，该算法还有其他实现方式，甚至可以使用dot 的交叉编译 Javascript 版本。可用于 Javascript 的功能最完整的解决方案可能是yFiles库中算法的商业实现。所以如果这是在商业场景中，你可能想看看相应的现场演示. 请注意，尽管 yFiles 带有自己的渲染和编辑器实现，但您仍然可以将代码插入 d3.js，因为布局算法可以用作独立实现来“仅”计算节点的坐标、边缘连接点、弯曲和标签。这个特定的实现支持大量额外的约束，比如“端口约束”（限制传出和传入边的方向以及它们在节点上的确切位置）、分层分组的节点（每个节点可以有一个父节点）并且父节点“包含”其所有子节点）、层和序列约束、边标记约束、不同的边路由样式、总线路由等等。

Disclosure: I work for the company that creates said library, however on SO I do not represent my employer.

披露：我为创建上述图书馆的公司工作，但是在 SO 我不代表我的雇主。