UML图中类的定位

Question

我正在创建一个将Python项目显示为UML图的工具（使用GUI显示一些代码错误检测）

我用Pyreverse扫描了一些项目，我有绘制UML图所需的所有数据。 问题是在画布上定位类框

首先，我决定使用已经实现的基于力的算法来决定类的位置，它很好地工作在这里 https://github.com/jvorcak/gpylint/blob/master/screenshots/gpylint.png 这里是code（Python，但是即使对于非Python程序员也很容易理解）

有一个问题，它对显示图形很好，但是如果我想显示UML，我希望有一些增强，例如如果两个类扩展一个超类，我希望它们在图中处于同一级别，就像graphs generated by dot program

你能给我一个算法吗？或者至少给我一些建议？在

Answer 1

连接组件的受约束布局是一个非常重要的问题，最好使用现有工具来解决。您提到了Graphviz，但我不认为您会找到一个直接的算法来移植到Python。更好的解决方案可能是使用pydot与Graphviz接口，让它处理布局。在

流看起来像：

1. 为UML图生成数据
2. 使用pydot转换为点语言
3. 使用Graphviz工具进行布局，输出包括布局在内的点语言
4. 用pydot解析输出的布局
5. 使用Python显示

Graphviz处理布局，但是所有的显示仍然在Python中，以允许您想要支持的任何自定义行为。在

Answer 2

似乎您缺少的主要增强功能是将图形转换为layered graph.这不是一项简单的任务，但它是可行的。（结果的质量可能因在过程中投入的时间和思想的多少而不同）。在

主要思想是在图上做一个topological sorting，把它分成几层，在里面做一些安排，然后画出这个图。（您可以找到python代码来在线进行真正的拓扑排序（example），但是真正的TS只会生成一个类似于长线的图形，我们需要一些不同的东西）

因此，我将尝试描述一种将给定图转换为分层图的算法：

1. 拓扑排序在有圈的图上不起作用，所以如果输入图还不是没有圈的有向图，你必须找到一组可以去掉（或可能反转）的边来创建一个循环图（稍后将它们添加到分层图中，但这会阻止分层，使图形变得不那么漂亮：）。因为找到最小的可能的边集是NP完全的（非常困难）-我想你必须在这里做一些捷径，不一定要找到最小的边集，但要在合理的时间内完成。

2. 把图分成层，这里可以做很多优化，但是我建议你保持简单。在图的所有顶点上迭代，每次都会收集所有顶点，而这些顶点没有进入层的边。在一些简单的情况下，这可能会生成一个类似于直线的图形，但它非常适合于UML图形的情况。

3. 一个好的图是一个边数最少的图crossing each other，这听起来并不重要，但这个事实对图的整体外观有很大贡献。决定交叉数量的是每一个层。但是同样，找到最小交叉数或找到最大无交叉边集是NP完全的：（“所以通常采用启发式方法，例如，将每个顶点放置在一个位置，该位置通过查找前一级别上相邻顶点位置的平均值或中值来确定，然后交换相邻对，只要这样可以提高交叉的数量。“

4. 在算法的第一步中移除（或反转）的边将返回到其原始位置。

就在这里！一个很好的UML分层图。在

• 如果我的解释不够清楚，试着再看一遍维基百科上的文章Layered graph drawing，或者问我任何问题，我会尽力回答。在
• 请记住，这是一个针对一般情况的算法，可以进行许多优化以更好地处理特定情况。在
• 如果您想为您的UML工具提供更多的特性，可以看看Jetbrains为他们的IntelliJ UML tool所做的出色工作

希望我在这里的评论能对你有所帮助。在

重要更新： 因为你说你“正在寻找可靠和/或官方来源的答案。“ 我附上This 来自graphviz（dot算法）的正式文档“描述了绘制有向图的四步算法。第一个过程使用网络单纯形算法找到一个最优的秩分配。第二步通过迭代启发式算法在秩内设置顶点顺序，结合新的权重函数和局部换位来减少交叉。第三步通过构造一个辅助图并对其排序来确定节点的最佳坐标。第四个过程使样条曲线绘制边。该算法可以绘制出很好的图形，并且运行速度很快。” http://www.graphviz.org/Documentation/TSE93.pdf

Answer 3

提供我自己的答案building on blahdiblah's，您确实可以使用建议的工作流成功地生成UML图。在

但是，这似乎是一条通往解决方案的道路，这对应用程序的设计似乎并不可取。具体来说，我们想reduce the number of theoretical moving parts required来实现这个功能。在

我建议您不要使用pyreverse，而是要查看the alternatives mentioned in this thread。具体地说，像Epydoc这样的工具可以更好地满足您的需求，无论是减少依赖关系还是（MIT）许可结构。在

不管你选择哪条路，祝你的应用程序好运。在