我有数千个节点和边的图表,我注意到 Cytoscape.js 的性能缺乏强制导向的 JavaScript 布局算法(cose 和 cola)。
我想知道我是否应该花时间寻找其他库或算法,或者这些算法的复杂性是否太高。在一个简单的算法中,我想每个节点都必须与其他节点进行比较,所以应该有一个二次复杂度,但是通过对连接性低的数据进行巧妙过滤,我可以想象出很好的近似值(我不需要数学上完美的结果,对用户来说只是直观的东西)。
我的目标是在典型的用户机器上在 10 秒内布局图表。
我发现的出版物(谷歌学术“力导向的复杂性”):
- 无向图的快速自适应布局算法 (1995)估计 O(|V|^3)
- 图形绘图的伽罗瓦复杂性:为什么数值解在力导向、光谱和圆包装绘图中无处不在说很难精确计算(?,我不是图论者)
- A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs “在亚二次时间和空间中生成二维、三维和更高维的图形”,我将尝试找到该图形的 JavaScript 实现。