(N x M) 绘图问题
我需要一种算法来（有效地）解决我正在编写的某些图表软件中出现的问题。
我有两组节点，N 和 M。N 中的每个节点 n0 与 M 中的唯一（对于 n0）节点有 0 到 M 个连接。这些节点组将排列在两条平行的水平线上，其中 N 个节点在 M 个节点上方的行中。连接将被绘制为从 N 到 M 的直线。
我需要做的是在水平线内重新排列 N 和 M 节点，以尽量减少交叉。他们有什么方法可以比简单地枚举所有可能的排列（即 O(N!*M!)）更有效吗？ （实际上，它比这要糟糕得多，因为还必须检查每个连接是否存在交叉）。
也欢迎参考相关文献，但需要解释其相关性的原因。
正如已经指出的，在一般情况下，这可以被认为是二分图（集合 N 和 M）平面化算法。然而，这个特定问题比那个问题受到更多限制（我希望可以使其更快），并且需要生成附加信息（这可能使其更慢），如下所示：
该图的限制是连接必须是绘制为从 N 到 M 的直线。在图论中，这实际上意味着连接不能位于 N 或 M 中的节点后面，而只能位于它们之间。因此，具有四个连接器的 2x2 情况可以在一般二分图情况下平面化，但在我的图表情况下不能。
附加信息是，如果无法平面化，我仍然需要最小交叉解决方案（或接近它）。一般来说，最小交叉算法与仅平面化的算法有显着不同。
I need an algorithm to (efficiently) solve a problem that has come up in some diagramming software that I am writing.
I have two sets of nodes, N and M. Each node n0 in N has 0 to M connections to a unique (for n0) node in M. These sets of nodes are to be arranged on two parallel horizontal lines, with the N nodes in the line above the M nodes. The connections will be drawn as straight lines from N to M.
What I need to do is to rearrange the N and M nodes within their horizontal lines, to minimize crossings. Is their any way to do this that is more efficient than just naively enumerating all possible arrangements, which is O(N!*M!)? (actually, its considerably worse than that, since each connection has to be checked for crossing also).
References to relevant literature are welcome also, though an explanation as to why its relevant is desired.
As has been pointed out, in the general case this could be considered a bipartite graph (the sets N and M) planarization algorithm. However, this specific problem is considerably more restricted than that (which I hope can make it faster) and is required to produce additional information (which may make it slower), as follows:
the diagram's restrictions are that the connections must be drawn as straight lines from N to M. In graph theory, this practically means that the connections cannot go behind the nodes in N or M, only between them. Thus, the 2x2 case with four connectors can be planarized in the general Bipartite graph case, but cannot in the case of my diagram.
The additional information, is that if it cannot be planarized, I still need a minimal-crossing solution (or close to it). Generally, minimal-crossing algorithims are significantly different from those that only planarize.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
suddnely_me 是对的，但也许您不需要完美的解决方案。你也可以尝试一个非常简单的贪心算法。根据连接数对所有节点进行排序。然后将其逐一添加到水平线上..虽然没有考虑清楚..但可能会导致一种简单的方法..
suddnely_me is right, but maybe you don't need a perfect solution. you could also try a really simple greedy algorithm. sorting all the nodes depending on the number of connections. then add one by one to the horizontal line.. didn't thought it through though.. but could lead to a simple approach..
您描述的模型称为二分图，您要求的是平面化算法。回答你的问题的最好方法是用谷歌搜索一下。
The model you described is called bipartite graph, and what you request is a planarization algorythm. The best way to answer your question is to google a bit.
您的问题可以通过力图对齐来解决，只要您不要求节点在其线上保持特定位置（即使您确实需要进行一些更改，您也可以将其关闭）
您需要的主要内容变化是使力对齐为 1D 而不是 2D，仅对齐 X 轴上的节点，而不是同时对齐 X 和 Y 上的节点。
该算法的前提是有力作用在节点上，因此节点有排斥力作用在它们导致它们彼此远离，但是彼此连接的节点所具有的吸引力大于排斥力。在每个循环中，您将力相加，导致相互吸引的节点彼此靠近，而没有相互吸引的节点将相互排斥，当您将总力相加低于某个阈值时，您的对齐就完成了，例如0.001。
http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)< /a>
Your problem can be solved with force graph alignment, as long as you don't require that the nodes keep a specific position on their lines (even if you do require that with some alteration you could pull it off)
The main thing you need to change is make force alignment 1D instead of 2D, only aligning the nodes on the X axes instead of aligning nodes on both X and Y.
The premise of the algorithm is that you have forces acting on the nodes, so the nodes have repulsion acting on them causing them to move further away from each other, however nodes that are connected to one another have attraction acting on them that is greater then the repulsion. In each loop you add the forces up causing the nodes that are attracted to one another to come in closer to one another while nodes that are not will repel, your alignment is done when you sum a total force thats lower then some threshold, something like 0.001.
http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)
N 和 M 有多大？有一个基于动态规划的解决方案，运行时间为 O(min(N, M)! * 2**max(N, M) * poly(N, M))，但我不确定这是否是一个显着的改进在你看来，过度暴力。
How large are N and M? There's a solution based on dynamic programming that runs in time O(min(N, M)! * 2**max(N, M) * poly(N, M)), but I'm not sure if that's a significant improvement over brute force in your view.