13

我很想知道 D3 使用什么算法来实现库中的力导向图功能。阅读了 Kobourov对力导向图历史的总结后，我对图书馆中使用的确切算法或方法（算法/启发式的组合）有点困惑。

D3 API 参考说 Barnes-Hut 算法用于计算作用在物体上的电荷，一个 O(N*log(N)) 操作。Kobourov 的文章提到 Quigley-Eades 算法和 Hu 的算法是利用 Barnes-Hut 的多级算法。其中一个是否在 D3 中以某种方式使用？

API wiki 进一步说 Verlet 集成用于粒子定位。源代码中提到了 Gauss-Seidel 算法，在Hu 的算法和 Dwyer 的图形布局论文中都提到了该算法。我想我正在寻找答案的问题是 D3 使用的“综合”算法；Kobourov 的文章列出了几个和 D3 强制导向功能似乎并不直接适合其中任何一个。

4

3 回答 3

4

在最初的d3 论文中，Mike Bostock & al. 写道 Dwyer 的实现用于力图布局：

力布局结合了物理模拟和迭代约束松弛 [7] 以实现稳定的图形布局。

[7] T.德怀尔。可扩展、通用且简单的受限图形布局。在 EuroVis，2009 年。

有关更多信息，Dwyer 的论文详细描述了整个算法。

于 2014-05-13T09:35:51.833 回答
3

好吧，这不是您具体问题的答案，但在他的强制导向布局演示页面上，他说，“布局算法灵感来自Tim Dwyer和Thomas Jakobsen。”

于 2012-11-14T02:08:07.420 回答
0

可以在 https://github.com/mbostock/d3/wiki/Force-Layout找到 Force-Layout 算法的概述

于 2014-10-28T10:22:29.357 回答