8

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

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

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

有一个问题，它非常适合显示图表，但是如果我想显示 UML，我希望有一些增强，例如，如果 2 个类扩展一个超类，我希望它们在图表中处于同一级别就像点程序生成的图表一样

你能告诉我一个算法如何做到这一点吗？或者至少给我一些想法？

4

6 回答 6

8

您似乎缺少的主要增强功能是将您的图表转换为分层图表。这不是一件容易的事，但它是可行的。（结果的质量可能会因过程中投入的时间和思想而异）。

主要思想是对图进行某种拓扑排序，将其拆分为层，在其中进行一些排列，然后绘制图形。（你可以在网上找到 python 代码来做一个真正的拓扑排序（例子），但真正的 TS 只会产生一个长线状的图形，我们想要一些不同的东西）

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

  1. 拓扑排序不适用于具有循环的图，因此如果输入图还不是没有循环的有向图，则必须找到一组可以删除（或可能反转）的边以创建循环图表（稍后您会将它们添加到分层图表中，但这会破坏分层并使图表不那么漂亮:)。由于找到可以删除的最小可能边集是 NP 完全的（非常困难） - 我认为你必须在这里做一些捷径，不一定要找到最小的边集，但要在合理的时间内完成。

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

  3. 一个好的图是相互交叉的边数最少的图，这听起来并不重要，但这一事实对图的整体外观有很大贡献。决定交叉点数量的是每一层中边缘的排列顺序。但同样，找到最小交叉点数或找到最大无交叉边集是 NP 完全的 :( “所以这又是典型的求助于启发式方法，例如将每个顶点放置在一个位置，该位置通过找到其邻居在前一层的位置的平均值或中值来确定，然后交换相邻对，只要这样可以提高交叉的数量。”

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

你有它！您的 UML 的一个很好的分层图。

  • 如果我的解释不够清楚，请尝试再次阅读有关分层图形绘制的 Wikipedia 文章，或者问我任何问题，我会尽力回复。
  • 请记住，这是针对一般情况的算法，可以进行大量优化以更好地处理您的特定情况。
  • 如果您想了解更多关于 UML 工具功能的想法，请查看 Jetbrains 为他们的IntelliJ UML 工具所做的出色工作

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

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

于 2012-04-14T14:54:25.923 回答
3

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

流程看起来像：

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

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

于 2012-04-10T18:47:50.177 回答
2

在 blahdiblah 的基础上提供我自己的答案，您确实可以使用建议的工作流程成功生成您的 UML 图。

但是，这似乎需要通往您的解决方案的花园路径，这对于您的应用程序的设计似乎并不理想。具体来说，我们希望减少实现这项工作所需的理论运动部件的数量。

我建议不要使用pyreverse ，而是查看此线程中提到的替代方法。具体来说，像Epydoc这样的工具可以更好地满足您的需求，既可以减少依赖关系，也可以减少其 ( MIT ) 许可结构。

无论您选择哪条路径，祝您申请顺利。

于 2012-04-10T22:00:55.193 回答
0

如果您想以有序的方式显示班级（父母在上，孩子在下），您应该跟踪每个班级的“权重”。我所说的重量是指“父母”的数量。

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

当然这只是基本思想，如果您希望您支持复杂的对象（多继承等），定位元素将比这更困难。

于 2012-04-13T23:50:06.957 回答
0

我不是 python 程序员，但功能上我可以给你一些建议。

  1. 您必须计算每节课的行数

  2. 保留班级的级别编号，这将有助于您根据级别编号组织课程。

于 2012-04-13T09:33:13.643 回答
0

您不太可能从不是首先开发 UML 的实际项目中获得好的结果。这是我们大约 10 年前使用第一个 java-uml 往返工具 (TogetherJ) 学到的一个教训。在文本模式下，很容易摆脱无法很好绘制的代码。作为一种深入了解代码的方法，smalltalk 系统的基于浏览器的动态视图比 UML 工具目前所能提供的要有效得多。

对于布局，只需查看 CAD 中针对电子产品所做的所有工作，尤其是印刷电路板 (PCB)。那里有很好的放置和路由算法。我还没有看到自动化 UML 工具正确处理的一件事是处理大量子类，您希望布局从父类下方的单行类更改为低节点移动半个节点的双行。

于 2012-04-15T07:38:23.303 回答