1

我正在做一个作业，我必须在网页上绘制一个带有多个框的图表，其中一些框将通过箭头连接。我已经完成了所有设置，以便能够绘制实际的图表、箭头和所有内容，但现在我面临着以最佳方式放置盒子的问题。我的意思是布局页面，以便我有最少的线交叉。

我必须做两种类型的图表：一种是更分层的图表，我知道将哪个框放置在左上方以及所有框形成层次结构的位置。另一个比较棘手，没有盒子需要有一个特定的位置，最终结果不是层次结构。在任何一种情况下，两个盒子之间都存在不止一个连接。这与以最易读的方式为数据库布置 E/R 图几乎相同。

有谁知道如何执行此操作或在哪里可以找到有关如何执行此操作的信息？

提前致谢

./CJ

4

1 回答 1

2

布置具有最小交叉点的任意图是一个 NP 难题，因此您只能找到一个好的启发式方法。

想到的是这样的：

  1. 将您的物品放在带有连接边缘的圆圈的周边上。
  2. 使用模拟退火交换项目，旨在最大限度地减少交叉次数。
  3. 使用强制定向布局进行整理。

另一种选择是找到一个生成树，渲染它，然后添加反向链接。与模拟退火方法相比，这可能会产生更多的交叉，但它的好处是可以将解决方案重用于作业的第一部分。

祝你好运！

于 2012-09-11T05:23:29.893 回答