.net – 最小化Web图形中的交叉线

概述我正在实现(实际上考虑它)一个控件,允许用户从一系列节点创建Web图表.目的是创建一个“流程图”,其中包含一系列问题,这些问题将由软件的另一部分提出;对于每个问题,选择的答案决定了接下来应该问哪个问题.它有点FSMish,但比形式问题的线性进展要聪明得多“如果您回答X问Y,请回答以下问题……”.该图是一个网络,并不保证是一棵树,因为定义图形的用户可能想要问几个后续问题然后返回到“正常”的提问线,因 我正在实现(实际上考虑它)一个控件,允许用户从一系列节点创建Web图表.目的是创建一个“流程图”,其中包含一系列问题,这些问题将由软件的另一部分提出;对于每个问题,选择的答案决定了接下来应该问哪个问题.它有点FSMish,但比形式问题的线性进展要聪明得多“如果您回答X问Y,请回答以下问题……”.该图是一个网络,并不保证是一棵树,因为定义图形的用户可能想要问几个后续问题然后返回到“正常”的提问线,因此两个不同的节点可以“合并”到相同的子节点.然而,保证网络不是圆形的并且具有一个起始点,因此通过图形存在有限数量的路径并且所有有限长度.

这是问题所在.我希望有一个“排列”按钮(或简单地自动排列)重新排列节点,以便连接必须相互交叉的网络节点的线数最小化.大多数流程图工具都有这样的功能,但是我的Google-fu无法找到这种类型的通用算法.我已经将其识别为“交叉数”问题,但似乎没有找到具有V节点和E路径的图的最小交叉数的一般解决方案,并且任何此类解决方案都是NP难的(如果可以在单个 *** 作中解决特定的子问题,然后可以在多项式时间内解决完整的问题.最重要的是,我发现的参考文献中没有一个能够详细列出具有最小(更不用说“最小”)交叉数的图形的算法.

任何提示？

编辑：我给了Sharkos他的优秀参考书.然而,假设图形具有明确的起始点,是单向和非圆形的,则工作算法(可能不是最佳的)实际上非常简单.在伪代码中：

"Give all nodes an initial Xscore,Yscore and linkscore of 0Determine the start node (either designated,or the one not linked to by any other)Set start node's Xscore and Yscore to 1Set running Yscore = 1Start recursionfor 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 YscoreOrder 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

解决方法 这是关于该主题的 Master’s thesis,它给出了一些讨论的算法,并提供了许多不同人的方法的参考,从精确算法到近似算法.

然而,对于“平面化方法”的一个相当简单,具体的伪代码版本,显然(不是专家,虽然我已经研究过图论并且听起来似乎很有用)一个常见的近似,见0700的this chapter第2.5节,这是免费在线提供.

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

总结

以上是内存溢出为你收集整理的.net – 最小化Web图形中的交叉线全部内容，希望文章能够帮你解决.net – 最小化Web图形中的交叉线所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。