D3.js用于力导向图的算法是什么？ [英] What algorithms does D3.js use for the force-directed graph?

问题描述

我有兴趣知道什么算法D3用来在库中实现力导向图特性。阅读了 Kobourov的总结的武力历史导向图让我有点不知道什么是在库中使用的确切的算法或方法（算法/启发式组合）。

I would be interested to know exactly what algorithms D3 uses to achieve the force-directed graph feature in the library. Having read Kobourov's summary of the history of force-directed graphs left me a bit baffled as to what is the exact algorithm or method (combination of algorithms / heuristics) used in the library.

D3 API参考

D3 API reference says Barnes-Hut algorithm is used to calculate the charges acting on bodies, an O(N*log(N)) operation. Kobourov's article mentions that Quigley-Eades algorithm, and Hu's algorithm are multilevel algorithms that make use of Barnes-Hut. Is one of them utilized in some way in D3?

API维基说，Verlet集成用于粒子定位。 源代码提及Gauss-Seidel算法，反过来在胡的算法和Dwyer的图形布局纸。我想我正在寻找答案的问题是什么整合算法D3利用;

The API wiki futher says Verlet integration is used for particle positioning. The source code mentions Gauss-Seidel algorithm, which in turn is mentioned both in Hu's algorithm and Dwyer's graph layout paper. I guess the question I'm looking an answer to is what "integrative" algorithm D3 utilizes; Kobourov's article lists several and D3 force-directed features don't directly seem to fit any of those.

推荐答案

在原始的< a href =http://vis.stanford.edu/papers/d3 =nofollow> d3 paper ，Mike Bostock& et al。写入Dwyer的实现用于力图布局：

In the original d3 paper, Mike Bostock & al. wrote that Dwyer's implementation is used for the force graph layout :

力布局结合物理模拟和迭代约束松弛[7]布局。

The force layout combines physical simulation and iterative constraint relaxation [7] for stable graph layout.

[7] T. Dwyer。可扩展，通用和简单的约束图布局。在EuroVis，2009。

[7] T. Dwyer. Scalable, versatile and simple constrained graph layout. In EuroVis, 2009.

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

For more information, Dwyer's paper describes in details the whole algorithm.

这篇关于D3.js用于力导向图的算法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！