Jan*_*cak 6 python drawing uml graph-drawing
我正在创建一个用于将Python项目显示为UML图的工具(+使用GUI显示一些代码错误检测)
我使用Pyreverse扫描一些项目,我拥有绘制UML图所需的所有数据.问题是在画布上定位类框
首先,我决定使用已经实现的基于力的算法来决定类的位置,它的效果非常好,这里的结果是 https://github.com/jvorcak/gpylint/blob/master/screenshots/gpylint.png ,这里是该代码(Python,但它即使非Python程序员很容易理解)
有一个proble,这是伟大的显示图形,但如果我想显示UML我想有一些改进,例如,如果2类扩展了一个超类,我希望他们是在图中的同一水平比如点程序生成的图表
你能告诉我一个算法怎么做吗？或者至少给我一些想法？
您似乎缺少的主要增强功能是将图形转换为分层图形.这不是一件容易的事,但它是可行的.(结果的质量可能会因为过程中投入的时间和精力而有所不同).
主要思想是在图形上进行某种拓扑排序,将其拆分为图层,在其中进行一些排列,然后绘制图形.(你可以找到python代码在网上做一个真正的拓扑排序(例子),但真正的TS只会产生一个类似长线的图,我们想要一些不同的东西)
因此,我将尝试描述一种算法,将给定的图形转换为分层图形:
拓扑排序不适用于具有周期的图形,因此如果输入图形不是没有周期的有向图形,则必须找到一组可以删除(或可能反转)以创建循环的边缘图形(您稍后会将它们添加到分层图形中,但这会制动分层并使图形变得不那么漂亮:).由于找到可以删除的最小边缘集是NP完全(非常难) - 我认为你必须在这里做一些快捷方式,并且不一定找到最小边集,但是在合理的时间内完成.
将图形制作成图层,可以在此处进行许多优化,但我建议您保持简单.迭代所有图形的顶点,每次收集所有顶点,没有到图层的入边.在一些简单的情况下,这可能会产生类似于线的图形,但在UML图形的情况下它非常适合.
一个好的图形是具有最小数量的边缘相互交叉的图形,它听起来并不重要,但这一事实对图形的整体外观有很大贡献.决定交叉数的原因是每一层中边缘的排列顺序.但是,找到最小交叉数或找到最大无交叉边集是NP完全的:("所以再次这是典型的采用启发式方法,例如将每个顶点放置在一个位置,该位置通过查找前一级别上邻居位置的平均值或中位数确定,然后交换相邻对,只要这样可以改善交叉点的数量."
在算法的第一步中移除(或反转)的边缘返回到其原始位置.
你有它!一个很好的UML分层图.
希望我的评论在任何方面都有所帮助.
重要更新: 因为你说你正在" 寻找可信和/或官方来源的答案. "我附上了这个 来自graphviz(dot算法)的正式文档,"描述了用于绘制有向图的四遍算法.第一遍使用网络单纯形算法得到最佳秩分配.第二遍通过迭代启发式设置秩中的顶点顺序,该迭代启发式结合了新的权重函数和局部转置以减少交叉.第三遍通过构造和建立节点来找到节点的最佳坐标.排序辅助图.第四遍使样条绘制边缘.算法绘制好图纸并快速运行." http://www.graphviz.org/Documentation/TSE93.pdf
