我正在实现(实际上在考虑)一个控件,允许用户创建由一系列节点组成的 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