4

我正在实现（实际上考虑）一个控件，该控件允许用户从一系列节点中创建一个 web 图表。目的是从软件的另一部分提出的一系列问题中创建一个“流程图”；对于每个问题，选择的答案决定了接下来应该问哪个问题。这有点 FSMish 但比“如果您对问题 Y 回答 X，请回答以下...”形式的问题的线性进展要聪明得多。该图是一个网络，并不保证是一棵树，因为定义该图的用户可能想问几个后续问题，然后返回到“正常”的提问线，因此两个不同的节点可能会“合并”到同一个子节点。然而，

这是问题。我想要一个“排列”按钮（或简单地自动排列）来重新排列节点，以便将必须相互交叉的网络节点连接线的数量降至最低。大多数流程图工具都有这样做的功能，但我的 Google-fu 未能找到这种类型的通用算法。我已将其确定为“交叉数”问题，但似乎没有通用解决方案来找到具有 V 节点和 E 路径的图的最小交叉数，并且任何此类解决方案都是 NP 难的（如果一个特定的子问题可以在单个操作中解决，然后整个问题可以在多项式时间内解决）。最重要的是，我没有找到可以用最小的图形布置图形的详细算法（更不用说“

有什么提示吗？

编辑：我给 Sharkos 打勾是因为他的出色参考。然而，假设图有一个明确的起点，是单向的和非圆形的，一个工作算法（可能不是最优的）实际上非常简单。在伪代码中：

"
Give all nodes an initial XScore, YScore and LinkScore of 0
Determine the start node (either designated, or the one not linked to by any other)
Set start node's XScore and YScore to 1
Set running YScore = 1
Start recursion
for each path from node
   if node on other end has XScore <= current      
      set other node's XScore to current + 1
   if node on other end has YScore <= running YScore
      set other node's YScore to running YScore
      increment other node's LinkScore
   Recurse with node on other end
   Increment running YScore

Order nodes by XScore, then YScore.

--If the graph happens to be planar, we're done.

--To minimize crossover:

for each XScore
   for each node with that XScore
      if the next node with the same XScore has a higher LinkScore
         swap the two nodes, exchanging YScores
4

1 回答 1

3

这是一篇关于该主题的硕士论文，其中给出了一些带有讨论的算法，并参考了许多不同的人的方法，从精确算法到近似算法。

然而，对于“平面化方法”的一个相当简单、具体的伪代码版本，显然（不是专家，尽管我研究过图论并且听起来似乎很有用）一个常见的近似值，请参阅图手册本章中的第 2.5 节绘图和可视化，可在线免费获得。

希望那是你想要的那种东西？

于 2012-08-09T20:50:34.853 回答