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

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

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

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

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

解决方案

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

主要思想是对图形进行某种拓扑排序，以将其拆分为层，在其中进行一些排列，然后绘制图形。（您可以找到python代码在线进行真实的拓扑排序（示例），但是真实的TS只会生成长线状图，我们希望有所不同）

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

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

2. 将图分成几层，可以在此处进行许多优化，但是我建议您保持简单。遍历图的所有顶点，并且每次都收集所有顶点，而没有到层的输入边。在某些简单情况下，这可能会生成线状图，但在UML图中非常适合。

3. 好的图形是相互交叉的边最少的图形，虽然听起来并不重要，但是这一事实对图形的整体外观有很大的帮助。决定相交数量的是每一层边的排列顺序。但是，再次找到最小相交数量或找到最大无相交边集是NP-complete :(求助于启发式方法，例如将每个顶点放置在一个位置上，该位置通过找到邻居在先前级别上的位置的平均值或中间值来确定，然后交换相邻的对，只要这能改善交叉的次数即可。”

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

在那里，您拥有了！一个很好的UML分层图。

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

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

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