在纸上布局图形打印

Question

我们的应用程序显示可能包含许多节点和边的大型图形。当然，我们使用像dot这样的工具来布局图形，并且它们在屏幕上看起来很好。但是，用户希望将它们打印到纸张上。现在从技术上讲，我们可以做到这一点，我们将图形分成小图像，用户可以打印出来。但是，没有保证通过在页面大小处切割时，我们不会切断节点，在不同页面之间有大量的边等等。我正在寻找一种算法，可以改变图形的布局，使其在打印时更易于使用： - 确保没有节点会落在页面边界上 - 尝试最小化页面之间的边缘 看起来像是找到密集相关节点的“聚类”，将它们放在同一页上，并尽量减少与其他聚类之间的边缘交叉。有人能指点我相关的文献/工具来做这种事吗？

谢谢

- JP Moresmau

Answer 1

聚类分析是一个不错的起点。

我建议以下处理方式：

首先定义成本函数：

给定页面重分配：Cost（Repartition）= f（靠近边界的节点，多页边缘）

目标是最小化此函数。

选择聚类分析算法：

定义聚类算法（您可以查看我的帖子DBSCAN：{{link1：C#或vb.net中的DBSCAN代码，用于聚类分析}} 并将“页面”约束添加到聚类中。 （页面大小）

根据您处理点的顺序，由于“页面约束”，结果会有所不同。

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

该算法的复杂度可能达到O(n!)，对于大型图形而言这是相当庞大的。因此，您需要考虑一些更多的集群限制条件，或者仅进行部分搜索（首先测试n2以使其达到O(n2)），以获得较好的近似结果。根据可接受的成本，您可以在合理的时间内得出结果，也可能不行。

- Ricky Bobby