algorithm - 布置图表以在纸上打印

Question

我们的应用程序显示具有大量节点和边的潜在大图。当然，我们使用点之类的东西来布局图形，它们在屏幕上看起来很好。但是，用户希望将它们打印到纸上。现在技术上我们可以做到，我们将图表分成小图像，用户可以打印出来。但是不能保证通过按页面大小进行裁剪，我们不会裁剪节点、在不同页面之间加载大量边等。我正在寻找一种可以改变图形布局的算法，以便它在打印时更有用:- 确保没有节点会落在页面边界上- 尽量减少页面之间的边缘看起来像是找到密集相关节点的“集群”以放置在同一页面上，几乎没有边缘交叉到其他页面到其他集群。谁能指出相关文献/工具来做这类事情？

谢谢

Answer 1

聚类分析是一个好的开始。

我建议采用以下方式处理:

首先定义一个代价函数:

给定一个页面重新分区:Cost(Repartition) = f(nodes near boundaries, multipages-edges)

目标是最小化此函数。

选择聚类分析算法:

定义一个聚类算法(你可以看看我在 DBSCAN 上的帖子:DBSCAN code in C# or vb.net , for Cluster Analysis并向集群添加“页面”约束。 (页面大小)

由于“页面限制”，结果会有所不同，具体取决于您将要遍历的顺序。

选择成本最小的那个，或者在找到可以接受的成本时停止。

该算法的复杂度为 O(n!) ...对于大图来说有点大。因此，您需要考虑更多的聚类约束，或者只是进行部分搜索(首先测试 n2 以使其在 O(n2) 中)以获得良好的近似值。根据可接受的成本，您可以在合理的时间内获得结果。