<p>似乎您缺少的主要增强功能是将图形转换为<a href="http://en.wikipedia.org/wiki/Layered_graph_drawing" rel="nofollow">layered graph.</a>这不是一项简单的任务,但它是可行的</strong>。(结果的质量可能因在过程中投入的时间和思想的多少而不同)。在</p>
<p>主要思想是在图上做一个<a href="http://en.wikipedia.org/wiki/Topological_sorting" rel="nofollow">topological sorting</a>,把它分成几层,在里面做一些安排,然后画出这个图。(您可以找到python代码来在线进行真正的拓扑排序(<a href="http://code.activestate.com/recipes/577413-topological-sort/" rel="nofollow">example</a>),但是真正的TS只会生成一个类似于长线的图形,我们需要一些不同的东西)</p>
<p>因此,我将尝试描述一种将给定图转换为分层图的算法:</p>
<ol>
<li><p>拓扑排序在有圈的图上不起作用,所以如果输入图还不是没有圈的有向图,你必须找到一组可以去掉(或可能反转)的边来创建一个循环图(稍后将它们添加到分层图中,但这会阻止分层,使图形变得不那么漂亮:)。因为找到最小的可能的边集是NP完全的(非常困难)-我想你必须在这里做一些捷径,不一定要找到最小的边集,但要在合理的时间内完成。</p></li>
<li><p>把图分成层,这里可以做很多优化,但是我建议你保持简单。在图的所有顶点上迭代,每次都会收集所有顶点,而这些顶点没有进入层的边。在一些简单的情况下,这可能会生成一个类似于直线的图形,但它非常适合于UML图形的情况。</p></li>
<li><p>一个好的图是一个边数最少的图<a href="http://en.wikipedia.org/wiki/Crossing_number_%28graph_theory%29" rel="nofollow">crossing each other</a>,这听起来并不重要,但这个事实对图的整体外观有很大贡献。决定交叉数量的是每一个层。但是同样,找到最小交叉数或找到最大无交叉边集是NP完全的:(“所以通常采用启发式方法,例如,将每个顶点放置在一个位置,该位置通过查找前一级别上相邻顶点位置的平均值或中值来确定,然后交换相邻对,只要这样可以提高交叉的数量。“</p></li>
<li><p>在算法的第一步中移除(或反转)的边将返回到其原始位置。</p></li>
</ol>
<p>就在这里!一个很好的UML分层图。在</p>
<ul>
<li>如果我的解释不够清楚,试着再看一遍维基百科上的文章<a href="http://en.wikipedia.org/wiki/Layered_graph_drawing" rel="nofollow">Layered graph drawing</a>,或者问我任何问题,我会尽力回答。在</li>
<li>请记住,这是一个针对一般情况的算法,可以进行许多优化以更好地处理特定情况。在</li>
<li>如果您想为您的UML工具提供更多的特性,可以看看Jetbrains为他们的<a href="http://www.jetbrains.com/idea/training/demos/uml-class-diagrams.html" rel="nofollow">IntelliJ UML tool</a>所做的出色工作</li>
</ul>
<p>希望我在这里的评论能对你有所帮助。在</p>
<p><strong>重要更新:</strong>
因为你说你“<em>正在寻找可靠和/或官方来源的答案。</em>“
我附上<strong><a href="http://www.graphviz.org/Documentation/TSE93.pdf" rel="nofollow">This</a></strong>
来自graphviz(dot算法)的正式文档“描述了绘制有向图的四步算法。第一个过程使用网络单纯形算法找到一个最优的秩分配。第二步通过迭代启发式算法在秩内设置顶点顺序,结合新的权重函数和局部换位来减少交叉。第三步通过构造一个辅助图并对其排序来确定节点的最佳坐标。第四个过程使样条曲线绘制边。该算法可以绘制出很好的图形,并且运行速度很快。”
<a href="http://www.graphviz.org/Documentation/TSE93.pdf" rel="nofollow">http://www.graphviz.org/Documentation/TSE93.pdf</a></p>