绘制图结构的算法？
我有一个有向图 G=(V,E)，现在看起来非常乱，我想重新绘制一下。这个图是一个流程图，节点数量超过1000，并且每个节点都有多个出边，所以用肉眼追踪起来非常困难。比如说，左下角的一个节点通过一条边连接到右上角的一个节点。如果能把这两个节点放在一起就好了。边太多了，追踪每条边真是让人头疼。
我可以访问并修改所有节点的 (x,y) 坐标。我想在保持当前结构的基础上，重新绘制这个图，让它更容易被人理解。我觉得可以先从减少交叉边的数量入手。
有没有什么算法可以帮助我重新绘制这个图呢？
我的问题是，如何给每个节点分配 (x,y) 坐标，让它们看起来更有条理，更容易追踪和阅读？我该如何正式表达这些要求？如果这是一个 NP 问题，我应该采用启发式方法吗？这里有一个相对有序的图的例子，而这个则是一个比较乱的图（虽然比我处理的要小得多）。
任何帮助都将不胜感激。谢谢。
编辑：我仍然在寻找直接的答案。我研究了平面直线和正交绘图方法，但得到的都是冗长的研究论文。我想要的是一些实现、伪代码，或者至少一些可以让我入门的东西。
编辑 2：我并不是想展示这个图。算法的输入应该是graph G (由 V 和 E 组成)，输出应该是{(xi, yi) 对于每个 vi 在 V 中}
2 个回答
0
那个看起来很乱的图好像是用样条曲线画的，试试用平面直线算法来代替吧。其实这个问题挺复杂的，我通常会用GraphViz作为我的图形绘制工具，你可以用-Gsplines=line这个选项来生成你想要的图。
4
你可以去看看graphviz.org；这是一个比较复杂的问题，已经有很多研究在这方面做了，所以自己重新发明轮子并不是个好主意。
你可能需要让Java程序输出一个数据文件，这样像'dot'这样的工具才能读取并用来生成图形布局。