我们的应用程序显示具有大量节点和边的潜在大图。当然，我们使用点之类的东西来布局图形，它们在屏幕上看起来很好。但是，用户希望将它们打印到纸上。现在技术上我们可以做到，我们将图表分成小图像，用户可以打印出来。但是不能保证通过按页面大小进行裁剪，我们不会裁剪节点、在不同页面之间加载大量边等。我正在寻找一种可以改变图形布局的算法，以便它在打印时更有用: - 确保没有节点会落在页面边界上 - 尽量减少页面之间的边缘 看起来像是找到密集相关节点的“集群”以放置在同一页面上，几乎没有边缘交叉到其他页面到其他集群。谁能指出相关文献/工具来做这类事情？
谢谢
最佳答案
聚类分析是一个好的开始。
我建议采用以下方式处理:
首先定义一个代价函数:
给定一个页面重新分区:Cost(Repartition) = f(nodes near boundaries, multipages-edges)
目标是最小化此函数。
选择聚类分析算法:
定义一个聚类算法(你可以看看我在 DBSCAN 上的帖子:DBSCAN code in C# or vb.net , for Cluster Analysis 并向集群添加“页面”约束。 (页面大小)
由于“页面限制”，结果会有所不同，具体取决于您将要遍历的顺序。
选择成本最小的那个，或者在找到可以接受的成本时停止。
该算法的复杂度为 O(n!) ...对于大图来说有点大。 因此，您需要考虑更多的聚类约束，或者只是进行部分搜索(首先测试 n2 以使其在 O(n2) 中)以获得良好的近似值。 根据可接受的成本，您可以在合理的时间内获得结果。
关于algorithm - 布置图表以在纸上打印，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6621843/