尽量减少网络图中的交叉线

我正在实现（考虑实际情况）一个控件，它允许用户创建一系列节点中的Web图。其目的是为了创建一个“流程图”，从一系列软件的另一部分要求提出的问题中进行分类;对于每个问题，选择的答案决定下一个问题。它有点FSMish，但比表格问题的线性进展要聪明得多。“如果你回答问题Y，请回答以下......”。该图是一个网络，并不能保证是一棵树，因为定义该图的用户可能想要问几个后续问题，然后返回到“正常”问题线，因此两个不同的节点可能会“合并”到同一个子节点。然而，网络保证不是循环的并且有一个起点，因此通过图的路径数量有限，而且所有的路径都是有限长的。尽量减少网络图中的交叉线

这是问题。我想要有一个“排列”按钮（或者简单地自动排列）来重新排列节点，以便连接网络节点必须相互交叉的线条数量减到最少。大多数流程图工具都有这个功能，但是我的Google-fu没有找到这种通用算法。我已经将它定义为“交叉数”问题，但似乎没有找到具有V节点和E路径的图的最小交叉数的一般解决方案，并且任何这样的解决方案都是NP-hard（if一个特定的子问题可以在一次操作中解决，那么完整的问题可以在多项式时间内解决）。最重要的是，没有任何参考文献可以找到详细的算法，可以用一个最小的（没有任何“最小”）交叉数表示一个图。

任何提示？

编辑：我给了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

来源

2012-08-09 KeithS

图形绘制是一项棘手的业务，可能有成千上万的出版物，对所有应用程序没有明确的最佳解决方案。 [Graphviz dot]（http://www.graphviz.org/Documentation.php）通常在绘制图表方面做得很好，但它没有声明任何最优性，并且有些情况下它完全不适合。你可以在子进程中运行'dot'并使用它的输出，或者如果它的结果符合你的口味，就可以计算出它的效果。 – MvG 2012-08-09 19:35:03

这里有一个关于这个话题，这给一些算法与讨论Master's thesis，并给予很多很多不同的人的方法，从精确算法近似算法引用。然而，对于一种相当简单，具体的伪代码版本的“平面化方法”，显然（不是专家，尽管我已经研究了图论，而且听起来似乎很有用），这是一种常见的近似方法，请参见this chapter中的第2.5节。 Handbook of Graph Drawing and Visualization，这是免费在线。

希望这是你想要的东西？

来源

2012-08-09 20:50:34 Sharkos

正是我想要的那种东西。 – KeithS 2012-08-09 20:52:20

尽量减少网络图中的交叉线

回答

相关问题