UML图中类的定位

Question

我正在创建一个工具，用于将Python项目显示为UML图（+使用GUI显示一些代码错误检测）。 我使用Pyreverse扫描了一些项目，并且我拥有绘制UML图所需的所有数据。问题在于类框在画布上的定位。首先，我决定使用已经实现的力导向算法来决定类的位置，它在这里运行得很好，这是结果https://github.com/jvorcak/gpylint/blob/master/screenshots/gpylint.png 这是 代码（Python，但即使对于非Python程序员也很容易理解）。有一个问题，它非常适合显示图形，但如果我想显示UML，我希望有一些增强功能，例如，如果两个类扩展一个超类，我希望它们在图中处于相同的级别，就像 由dot程序生成的图形 一样。

- Jan Vorcak

---

你需要用户动态调整摆放位置吗？如果不需要，你可以使用graphviz的dot程序为您布局（http://www.graphviz.org/）。 - Mr Fooz

谢谢您的回复，我已经提到我想知道点程序的算法（如果没有的话，我将不得不浏览它的源代码），因为我想在画布上绘制这些对象并允许用户移动它们。 - Jan Vorcak

这可能有点困难，因为大多数Python程序都是使用鸭子类型完成的。对于我的一些程序，我并没有为所有类使用继承。 - quantum

Answer 1

似乎你所缺少的主要增强功能是将图形转换为分层图。这并非易事，但是可以做到（结果的质量取决于投入的时间和思考）。主要思路是在图中进行某种拓扑排序以将其分成层，对其进行一些排列，然后绘制图形。（你可以在网上找到Python代码来进行真正的拓扑排序（示例），但真正的拓扑排序只会产生类似长线的图形，我们需要的是有所不同的东西）因此，我将尝试描述一个算法，将给定的图形转换为分层图：

1. 拓扑排序无法在有环图上进行，因此如果输入的图不是已经没有环的有向图，则需要找到一组可删除（或可能翻转）的边，以创建无环图（稍后将把它们添加到分层图中，但这将破坏分层并使图形不太美观 :）。由于找到可以删除的最小边集是NP完全问题（非常困难），我认为您必须在这里做一些快捷方式，并不一定要找到最小的边集，而是在合理的时间内完成。

2. 将图形分成层，这里可以进行许多优化，但我建议您保持简单。遍历所有图形的顶点，并每次将没有入边的顶点收集到一个层中。这可能会在某些简单情况下产生类似线条的图形，但它非常适合UML图的情况。

3. 好的图形是具有最小交叉边数的图形（交叉边数），这听起来并不重要，但这个事实对整体图形的外观有很大贡献。决定交叉数量的是每层中边的排列顺序。但同样地，找到最小交叉数或找到最大无交叉边集是NP完全的 :( "因此，通常会采用启发式方法，例如将每个顶点放置在一个位置上，该位置由其前一级邻居的位置的平均值或中位数确定，然后交换相邻对，只要这改善了交叉数量。"

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

这样就完成了！您的UML图现在有了漂亮的分层图。

• 如果我的解释不够清晰，请再次阅读分层图绘制的维基百科文章，或者问我任何问题，我会尽力回答。
• 请记住，这是一个适用于一般情况的算法，可以进行许多优化以更好地处理您的特定情况。
• 如果您想要更多关于UML工具功能的想法，请查看Jetbrains为其IntelliJ UML工具所做的出色工作。

希望我的评论对您有所帮助。

重要更新： 由于您表示您希望“寻求可信和/或官方来源的答案。” 我附上了此处 来自graphviz（dot算法的正式文档），其中“描述了一种用于绘制有向图的四遍算法。第一遍使用网络单纯形算法找到最佳排名分配。第二遍通过迭代启发式方法将顶点顺序设置在等级内，该方法包括一种新颖的权重函数和局部置换以减少交叉。第三遍通过构建和排名辅助图找到节点的最佳坐标。第四遍制作样条线以绘制边缘。该算法能够产生良好的绘图效果并且运行速度快。” http://www.graphviz.org/Documentation/TSE93.pdf

- Ido.Co

---

对于这个问题，基础图论的加分项是+1。大多数强大的图形布局生成器将提供数据的拓扑排序视图和层次结构，特别是在保证图形无环或有规则修剪简单循环（例如UML、组织图表和许多其他以图形空间中的数据为层次结构的组织）的情况下。这非常好地解决了这个问题的算法部分，尽管我很好奇是否有一个预设的解决方案会更好地满足他们的需求。 :) - MrGomez

谢谢您的评论。您当然是正确的，自己实现一个令人满意的解决方案需要付出很多努力，唯一的好处是结果将更容易控制和定制。如果这个单一的好处值得这样做...那就由读者决定 :）。我发布这篇冗长的答案的原因是@javo表示他“想知道点程序的算法”，这将使他对算法的机制有一些基本的了解。 - Ido.Co

同意！这对我来说也非常有用，因为它为该领域提供了一个良好的设计概述。感谢您在此发布它。 :) - MrGomez

Answer 2

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

流程大致如下：

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

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

- blahdiblah

Answer 3

提供我的答案基于blahdiblah的建议, 您确实可以使用建议的工作流程成功生成您的UML图。但是，这似乎走了一条到达解决方案的花园小路，这似乎不符合您的应用程序设计的要求。具体来说，我们希望减少所需的理论移动部件数量才能使其正常工作。

与其使用pyreverse，我建议您研究本主题中提到的替代方法。特别是，像Epydoc这样的工具可能更好地满足您的需求，既减少依赖性，又符合（MIT）许可结构。

无论您选择哪条道路，祝您的应用程序好运。

- MrGomez

Answer 4

我不是Python程序员，但从功能上来说，我可以给您建议。

1. 您必须知道每个类别中将要包含的行数。

2. 保留类别的级别编号，这将帮助您根据级别号组织类别。

- Shaikh Farooque

Answer 5

如果您想按顺序显示类（父类在上，子类在下），则应跟踪每个类的“权重”。我所说的权重是指“父级”的数量。

例如，如果B继承自A，则B.weight = 1，A.weight = 0。如果C继承自B，则C.weight = 2。如果将此表示为一行，则类A将打印在第0行，B将打印在第1行，C将打印在第2行。一般来说，所有相同“权重”的类都将打印在同一虚拟行上。

当然，这只是基本思想，如果要支持复杂对象（多重继承等），则定位元素将更加困难。

- Thibaut D.

Answer 6

使用UML-first未开发的真实项目，很可能无法得到良好的结果。这是我们10年前使用第一个java-uml往返工具（TogetherJ）学到的教训。在文本模式下，很容易逃脱代码，使其无法漂亮地绘制。Smalltalk系统的动态基于浏览器的视图比UML工具更有效，可以提供深入了解代码的方式。

对于布局，只需查看电子CAD中完成的所有工作，特别是印刷电路板（PCB）。那里有很好的放置和布线算法。我从未见过自动化的UML工具正确处理大量子类的事情，其中您希望将布局从父代下面的单行类更改为双行，并将低节点移动半个节点。

- Stephan Eggermont