3

我需要一种算法来（有效地）解决我正在编写的一些图表软件中出现的问题。

我有两组节点，N 和 M。N 中的每个节点 n0 与 M 中的唯一（对于 n0）节点有 0 到 M 个连接。这些节点集将排列在两条平行的水平线上，N 个节点在 M 个节点上方的行中。连接将绘制为从 N 到 M 的直线。

我需要做的是在它们的水平线上重新排列 N 和 M 节点，以尽量减少交叉。他们有什么方法比简单地列举所有可能的安排更有效，即 O(N!*M!)？（实际上，它比这差得多，因为还必须检查每个连接是否交叉）。

也欢迎参考相关文献，尽管解释为什么需要它的相关性。

正如已经指出的，在一般情况下，这可以被认为是二分图（集合 N 和 M）平面化算法。然而，这个特定的问题比那个（我希望可以让它更快）受到更多的限制，并且需要产生额外的信息（这可能会使它变慢），如下所示：

  1. 该图的限制是连接必须绘制为从 N 到 M 的直线。在图论中，这实际上意味着连接不能在 N 或 M 中的节点后面，只能在它们之间。因此，具有四个连接器的 2x2 案例可以在一般的二分图案例中进行平面化，但在我的图表中不能。

  2. 额外的信息是，如果它不能被平面化，我仍然需要一个最小交叉的解决方案（或接近它）。通常，最小交叉算法与仅平面化的算法有很大不同。

4

4 回答 4

1

您的问题可以通过力图对齐来解决，只要您不要求节点在其线上保持特定位置（即使您确实需要进行一些更改，您也可以将其拉下来）

您需要更改的主要内容是强制对齐 1D 而不是 2D，仅对齐 X 轴上的节点而不是对齐 X 和 Y 上的节点。

该算法的前提是你有力作用在节点上，所以节点有排斥作用在它们上，导致它们彼此远离，但是相互连接的节点对它们有更大的吸引力排斥。在每个循环中，您将力相加，导致相互吸引的节点彼此靠近，而不相互吸引的节点将排斥，当您将总力相加低于某个阈值时，您的对齐就完成了，例如0.001。

http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)

于 2012-10-21T03:20:09.420 回答
1

您描述的模型称为二分图，您要求的是平面化算法。回答您的问题的最佳方法是谷歌一下。

于 2011-04-10T12:46:12.870 回答
1

suddnely_me 是对的，但也许您不需要完美的解决方案。你也可以尝试一个非常简单的贪心算法。根据连接数对所有节点进行排序。然后将一条一条添加到水平线..虽然没有考虑过..但可能会导致一个简单的方法..

于 2011-04-10T13:04:40.207 回答
0

N和M有多大？有一个基于动态规划的解决方案，运行时间为 O(min(N, M)! * 2**max(N, M) * poly(N, M))，但我不确定这是否是一个显着的改进在你看来，过度暴力。

于 2011-04-10T16:56:32.670 回答