Positioning classes in a UML diagram

Question

I am creating a tool to display a Python project in the form of a UML diagram (+ display some code error detection using the GUI)

I am looking at some project using Pyreverse and I have all the data I need to draw a UML diagram. The problem is positioning class fields on canvas

To begin with, I decided to use the already implemented power algorithm to determine the position of classes, it works well here https://github.com/jvorcak/gpylint/blob/master/screenshots/gpylint.png and here is the code (Python, but it’s easy to understand even for programmers not Python)

There is one example, it is great for displaying graphs, but if I want to display UML, I would like to have some improvements, for example, if 2 classes extend one superclass, I would expect them to be at the same level in the graph, as in the graph generated point program

Could you advise me on an algorithm how to do this? Or at least give me some ideas?

Answer 1

It seems that the main improvement that you are missing is turning your chart into a multi-level chart. This is not an easy task, but it is doable . (The quality of the result may vary depending on the amount of time and thought invested in the process).

The main idea is to do some sort of topological sorting on the graph, to break it into layers, perform some measures in it, and then draw the graph. (you can find python code to create a real topological sort on the Internet ( example ), but the real TS just creates a long line graph and we want something a little different)

So, I will try to describe the algorithm for converting a given graph to a multilevel graph:

• Topological sorting does not work on graphs with loops, so if the input graph is no longer a directed graph without loops, you will need to find a set of edges that you can delete (or possibly cancel) to create a loop graph (you will add them to multi-level schedule, but this will slow down the stratification and make the schedule less attractive :). Since finding the smallest possible set of edges that you can remove is NP-complete (very difficult) - I think you will need to make a few shortcuts here and not necessarily find the minimum set of edges, but do it in a reasonable amount of time.

• Brake the chart into layers, there are many optimizations that can be done here, but I suggest you make it simple. iterate over all vertices of the graph and each time collect all the vertices without incoming edges on the layer. This can lead to line graphing in some simple cases, but it is well suited for UML graphs.

• A good graph is one that has the least number of edges intersecting each other . This does not really matter, but this fact contributes greatly to the overall look of the chart. what determines the number of intersections is the order of the edges in each layer. But again, searching for the minimum number of intersections or searching for the maximum crossing set of edges NP-complete: ("so again this is typical for resorting to heuristics, for example, placing each vertex in a position determined by finding the average or median position of its neighbors at the previous level and then replace adjacent pairs if that improves the number of transitions. "

• The edges deleted (or reversed) in the first step of the algorithm are returned to their original position.

And here it is! A nice layered graph for your UML.

• If my explanations were not clear enough, try reading the Wikipedia article on Multilevel Graphic Drawing again or ask me any questions, and I will try to answer.
• Remember that this is an algorithm for the general case, and parties can be optimized to better cope with a specific case.
• If you want more ideas for the features of your UML tool, take a look at the wonderful work Jetbrains does for its IntelliJ UML tool.

Hope my comments here are helpful.

Important update: since you stated that you are "Look for a response drawing from reliable and / or official sources." I am attaching This is the Formal documentation from graphviz (the point algorithm), which "describes a four-pass algorithm for drawing oriented graphs. The first pass receives optimal rank assignment using the simplex network algorithm. The second pass establishes the order of vertices in the ranks using iterative heuristics including a new weight function and local transpositions to reduce intersections. The third pass determines the optimal coordinates for nodes by constructing and ranking the auxiliary graph ka. The fourth pass makes splines for drawing edges. The algorithm makes good drawings and works fast. " http://www.graphviz.org/Documentation/TSE93.pdf

Answer 2

The limited layout of connected components is a non-trivial problem that could be better using existing solution tools. You mentioned Graphviz , but I don't think you will find a simple algorithm for the Python port. A better solution would be to use pydot to interact with Graphviz and let it handle the layout.

The stream would look something like this:

• Creating data for a UML diagram
• Convert to point language with pydot
• Graphviz layout model that displays point language, including layout
• Parsing the layout with pydot
• Python Mapping

Graphviz handles the layout, but the entire display is still in Python to allow any custom behavior you want to support.

Answer 3

By providing your own blahdiblah-based answer , you really can use the proposed workflow to successfully create your UML diagrams.

But it looks like the garden path is right for your decision, which does not seem desirable for the design of your application. In particular, we want to reduce the number of theoretical moving parts needed to operate.

Instead of pyreverse , I recommend exploring the alternatives mentioned in this thread . In particular, a tool like Epydoc can better suit your needs both for reducing dependencies and for it ( MIT ).

No matter which path you choose, good luck with your application.

Answer 4

im not a python programmer, but functionally I can offer you something.

• You should have a line counter that you will have with each class

• Keep a class level number that helps you organize classes based on the no level.

Answer 5

If you want to show classes in an orderly way (parents on top, children below), you must keep track of the "weight" of each class. What I mean by weight is the number of "parents."

For example, if B inherits from A, B.weight = 1 and A.weight = 0. And if C inherits from B, C.weight = 2. If you represent this as a string, class A will be printed in line 0, B in line 1 and line 2. In general, all classes of the same "weight" will be printed on the same virtual line.

Of course, only a basic idea, the positioning element will be more complex than this if you want to support complex objects (multi-heritance, etc.).

Answer 6

You are unlikely to get good results from real projects that were not developed by UML-first. This is a lesson we learned about 10 years ago using the first java-uml round-trip (TogetherJ) tools. In text mode, it's too easy to get away with code that cannot be beautifully drawn. Smalltalk's dynamic browser-based representations are much more effective at getting a feel for the code than the UML tools currently provide.

For the layout, just take a look at all the work done in CAD for electronics, especially printed circuit boards (printed circuit boards). There are good placement and routing algorithms. One of the things that I have not seen in an automatic UML tool has the right to process many subclasses where you want the layout to change from one line of classes below the parent to a double line, and the lower nodes are shifted by half by node.