Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

## An algorithm for placing and drawing UML classes

If you are planning on taking the graphing approach to displaying your UML diagram, as opposed to the drag'n'drop method, then the following algorithm may be of interest to you.

The first problem of a graph is to allocate enough space for the graph to hold all of your UML classes. Of course, you could decide to allocate a 10x10 grid and hope that there won't be more than 100 classes; however, a) there could be more than 100 classes, and b) there could be significantly less than 100 spaces (waste of space).

So what you really want is a grid (i.e., graph) that can grow with the number UML classes. What you want is the following:

1 = 1x1
2 = 1x2
3,4 = 2x2
5,6 = 2x3
7,8,9 = 3x3
10,11,12 = 3x4
13,14,15,16 = 4x4
.
.

Of course, over time, the number of vacancies in the grid increase, but it is a small sacrifice that one needs to make to facilitate drawing the UML classes later. I've found it easier to work with a grid, as opposed to layouts of a different shape/configuration.

Before I move onto the drawing part of UML, here's the code needed to accomplish generating the above grid:

```generateGrid: anInteger
"generates a grid to hold the UMLClasses on display"

| result grid output index |
grid := UMLGrid new.
result := ((anInteger sqrt) rounded) raisedTo: 2.

result >= anInteger ifTrue: [
result := (result sqrt) rounded.
grid := UMLGrid new: (result @ result).
] ifFalse: [
result := (result sqrt) rounded.
grid := UMLGrid new: (result @ (result+1)).
].
^grid.
```

Do not worry about the UMLGrid class, it is but a matrix representation of the grid using OrderedCollections.

Now onto the drawing part of the algorithm. Here you want to accomplish a) placing each UML class into an appropriate location in the grid, b) determining a good spacing for the classes (no overlapping, and enough space for relationship lines), and of course c) draw the UML class and it's relationship lines.

Here is how you could go about each part:

a) Find an appropriate location for each UML class depends firstly on how many relationships the class has, and secondly on the neighbors and their number of relationships. You want to give classes with the highest number of relationships the locations in the grid with the most surrounding cells (usually, the middle of the grid). So start with the class with the highest number of relationship and place it into the center of the grid, then you move onto its neighbor with the highest number of relationships and place it into an adjacent cell with the maximum number of free neighbor cells. This turns out to be a nice recursive algorithm which should find a place of all of the connected UML classes (of course, you need to remember to keep track of all the placed UML classes, so that you won't place a class twice). Lastly, fill in any classes that may not have been placed.

b) Spacing depends on the maximum width and height of the drawn UML classes. I recommend taking your UML classes and parse them into a formatted string using ComposedText. ComposedText will allow you to determine useful information, such as height, width, number of lines, etc. The simplest way to go about spacing is to make each cell as wide as the greatest width of a class, and as tall as the greatest height of a class. Then add a buffer to each cell to accommondate for the relationship lines.

c) Again, having the UML classes parsed into ComposedText helps, since you can now easily draw borders (Rectangle) around the UML classes. Divider lines between the class name, attributes, and methods is also easy so long as you know the number of attributes in the class. Drawing the relationship lines between all the classes is also simple, since we have a decided to go with a grid. Using SegementedLine, draw a line from the corner or edge adjacent to the neighbor with whom the class has a relationship. For example, if ClassA depends on ClassB and ClassC, where ClassB is located to the top-right of ClassA, and ClassC is located to the left of ClassA; then, draw a line from the top right corner of classA to the bottom left corner of ClassB, and draw a line from the left edge of ClassA to the right edge of ClassC.

What you should end up with is a nicely spaced and arranged UML diagram, which will not need drag'n'drop to minimize relationship lines that are crossed or UML classes that overlap. I hope this will be of some help.