我正在实现（实际上在考虑）一个控件，允许用户创建由一系列节点组成的 Web 图。其目的是根据软件的另一部分要求的一系列问题创建类似"流程图"的东西；对于每个问题，选择的答案决定了下一个应该问什么问题。它有些类似于状态机，但比形如“如果您对问题Y的回答是X，请回答以下问题...”的线性问题智能得多。该图形是一个网络，并不保证是一棵树，因为定义图形的用户可能想要问几个后续问题，然后返回到“正常”的问题行，因此两个不同的节点可能会“合并”到同一个子节点。然而，这个网络保证不会是循环的，有一个起点，因此图形中有有限条路径，且所有路径长度都是有限的。
这里有个问题。我想要一个“排列”按钮（或者只需要自动排列），以便重新排列节点，使得互相连接的网状节点之间必须交叉的线的数量最小化。大多数流程图工具都有这样的功能，但我的 Google-fu 没有找到这种类型的通用算法。我已经将其识别为“交叉数”问题，但似乎没有通用解决方案可以找到具有 V 个节点和 E 条路径的图形的最小交叉数，并且任何这样的解决方案都将是 NP-难的（如果特定的子问题可以在单个操作中解决，那么整个问题可以在多项式时间内解决）。此外，我找到的参考资料中没有详细说明可以布局具有最小（更不用说“最小”）交叉数量的图形的算法。
有什么提示吗？
编辑：我给Sharkos打了勾，因为他提供了出色的参考文献。但是，假设图形具有明确定义的起点、单向和非循环，一个工作算法（可能不是最优的）实际上是相当简单的。伪代码如下：
这里有个问题。我想要一个“排列”按钮（或者只需要自动排列），以便重新排列节点，使得互相连接的网状节点之间必须交叉的线的数量最小化。大多数流程图工具都有这样的功能，但我的 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
dot并使用其输出，或者弄清楚它是如何做到的，如果它的结果符合您的口味。 - MvG