6

我正在使用 Processing 为复杂的数据和流程开发导航系统。作为其中的一部分，我已经深入了解了图形布局。这一切都很有趣，我对布局算法的看法是：力导向适用于娘娘腔（看看它的比例......哈哈），特征向量投影很酷，Sugiyama 层看起来不错，但在图形图上很快失败，虽然我依赖到目前为止，在特征向量上，我需要最小化边缘交叉以真正到达数据点。我知道，我知道 NP-complete 等。

我应该补充一点，我在应用xy拳击和使用类似 Sugiyama 的排列来减少跨行和列的边缘交叉方面取得了一些成功。即：图形 (|V|=90,avg degree log|V|) 可以从 11000 个交叉点 -> 1500（按盒装特征向量）-> 300 通过交替行和列排列来减少交叉点。

但是局部最小值……无论它是什么都围绕着这个标记，结果并不像它可能的那样清楚。我对 lit 的研究表明，我真的很想使用平面化算法，就像他们在 VLSI 中使用的那样：

  1. 使用 BFS 或其他东西来制作最大平面子图 1.a。布局平面子图 nice-like
  2. 巧妙地添加突出边来恢复原始图

请回复您对最快平面化算法的想法，欢迎您深入了解您熟悉的任何特定优化。

非常感谢！

4

2 回答 2

3

鉴于所有图表都不是平面的（您知道），最好采用“次佳”方法而不是“始终提供最佳答案”方法。

我这么说是因为我在研究生院的室友和你有同样的问题。他试图将图形转换为平面形式，而所有保证最小边缘交叉的算法都太慢了。他最终做了什么，只是实现了一个随机算法。基本上，布置图表，然后对边缘有很多交叉点的节点进行调整，最终您将处理最差的边缘块。

优点是：您可以在特定时间后将其删除，因此如果您有时间限制，这总是会在一定时间内出现，如果您得到一个糟糕的图表，您可以再次运行它（超过已经布局图）以获得更好的东西，并且相对容易编码。

缺点是你并不总是在交叉点中获得全局最小值，如果图形卡在高交叉区域，他的算法有时会将一个节点射向远处以尝试解决它，这有时会导致看起来非常奇怪的图形.

于 2011-11-18T14:56:31.250 回答
2

您已经知道很多图形布局，但不幸的是，我相信您的问题仍然没有明确说明。

您可以通过执行以下操作非常快速地平面化任何图形：(1) 在平面上随机布局图形 (2) 计算边的交叉位置 (3) 在交叉处创建伪顶点（这就是您在使用平面性时所做的事情基于非平面图的布局）（4）用新顶点和分割边扩展的图是自动平面的。

第一个困难来自于有一种算法来计算最小化边缘交叉次数的组合嵌入。第二个困难是使用组合嵌入在欧几里得平面中进行视觉上吸引人的布局，例如对于正交图布局，您可能希望最小化弯曲的数量，最大化面的大小，最小化整个图形的面积，等等，而这些目标可能会相互冲突。

于 2011-11-19T01:49:21.993 回答