UML Layout

Developing a Layout Algorithm for UML diagrams

Developing a Layout Algorithm for UML diagrams


Presented to the Melbourne Patterns Group, Wednesday 6th April 2011 6:30 PM

The Problem: Untangling UML Diagrams

png your image


  • Nodes – these are the shapes/rectangles
  • Edges – these are the lines connecting the shapes


  • My UML tool is written in Python
  • Existing layout libraries for e.g. python PyGraphviz has no windows port so I wrote my own
  • Layout is reasonably hard to implement – academic papers are very complex and deal in a lot of math
  • DIRTY SECRET OF ACADEMIA - Most Layout algorithms only deal with ‘points’ and don’t take into account real width and height

Thus for any real world use (unless dealing with network and particle visualisation where each node is the same size/shape), it seemed to me that one needs to run an overlap removal algorithm after the layout to remove shape overlaps.

Overlap removal algorithm needs to minimise shape movement in order to respect the layout results

What I developed

  • I used a ‘spring layout’ adapted from java and javascript
  • I developed my own overlap removal algorithm
  • Developed a GUI sandbox test app for development

Overlap Removal - Before and After



after applying layout

after applying layout

Unit Testing

Extensive unit tests were created to keep on top of the layout algorithm results. A word document containing annotated screenshots for each test helped me enormously.

an overlap removal use case which became a unit test

an overlap removal use case which became a unit test

Layout / persistence format was created for creating layout scenarios

{'type':'node', 'id':'D25', 'x':6, 'y':7, 'width':159, 'height':106}
{'type':'node', 'id':'D13', 'x':6, 'y':119, 'width':119, 'height':73}
{'type':'node', 'id':'m1', 'x':170, 'y':9, 'width':139, 'height':92}

Unit Testing Brittleness Avoided

Loose tests using (e.g. I created a function called ensureYorder() etc) were created so that the tests were not too brittle. Slight variations in position are ignored.

View this unit test file at the Pynsource GitHub repository tests/ Here is an example unit test:

def _LoadScenario3(self):

def test3_5InsertedVerticallyTwoPushedDown(self):

    # move m1 to the left
    node = self.g.FindNodeById("m1")
    node.left, = (6, 4)

    d97 = self.g.FindNodeById("D97")
    oldD97pos = (d97.left,

    # assert m1 has been inserted vertically - two pushed down
    were_all_overlaps_removed = self.overlap_remover.RemoveOverlaps()
    self.assertEqual(2, self.overlap_remover.GetStats()["total_overlaps_found"])

    self.assertTrue(self._ensureYorder("m1", "D25", "D13"))
    self.assertTrue(self._ensureXorder("m1", "D97", "D98"))
    self.assertTrue(self._ensureXorder("D25", "D97", "D98"))
    self.assertTrue(self._ensureXorder("D13", "D97", "D98"))
    self.assertEqual(oldD97pos, (d97.left,  # ensure D97 hasn't been pushed

Running the tests:

An example test run

An example test run

Having a huge bank of unit tests helped in refactoring, too. Imagine testing all the necessary scenarios by hand!

The final Results were pretty good!

A UML diagram after overlap removal

A UML diagram after overlap removal

Design Patterns Used


  • Memento was used to remember graph layout positions and then compare mementos to see if anything had ‘changed’ and thus drop out of the Spring layout algorithm early
  • Memento was used to save/restore layouts in my test GUI – assigned to keys 0..9


Blackboard pattern used to run layout several times and figure out which was the best, cleanest result using multiple criteria. Each run is a ‘snapshot’

Snapshot 1 [6] LL  0   NN pre rm overlaps  5   LN  0   scale 1.6   bounds 23  (500, 473) <---
Snapshot 2 [4] LL  0   NN pre rm overlaps  5   LN  1   scale 1.4   bounds 30  (570, 537)
Snapshot 3 [5] LL  0   NN pre rm overlaps  6   LN  2   scale 2.0   bounds 17  (444, 393)
Snapshot 4 [2] LL  0   NN pre rm overlaps  4   LN  2   scale 1.4   bounds 34  (648, 537)
Snapshot 5 [3] LL  0   NN pre rm overlaps  5   LN  4   scale 2.0   bounds 21  (427, 508)
Snapshot 6 [1] LL  0   NN pre rm overlaps 10   LN  5   scale 2.0   bounds 18  (485, 379)

Python goodness helped in this ‘AI’ smartness

def sortfunc(d):
  # this does the thinking!
  return (d['LL'], d['LN'], d['bounds_area_simple'], -d['scale'], d['NN_pre_OR']) 


  • “Line over node” overlap was abandoned as it started to get really complex with a lot of trigonometry and perhaps this area needs a more academic approach
  • Non straight lines and line routing is probably the better direction
  • Adding an understanding of UML semantics is another direction to research, so that e.g. base classes are above derived classes etc.

Overlap Removal Server

In 2020 I needed to expose the overlap removal code as an API for javascript to use.

Here is that small research sub-project


  • Overlap removal code is Python, open source
  • Part of my python UML tool PyNSource: Reverse engineer python source code into UML - display UML as Ascii art or PlantUML diagrams in a proper diagramming visual workspace.

Slides on Scribd

UML Graph Layout - Andy Talk - March 2011

Slides as HTML

  • The problem of laying out UML
  • Spring Layout
  • Mapping layout to Real World
  • OGL
  • MVC
  • Overlap Removal
  • Unit tests and unit test diagrams
  • Memento Design Pattern
  • Blackboard Design Pattern & Injecting sorting function
  • Future..

Slides as Pdf download

View as pdf


Sample Images

png your image

png your image



after applying layout

after applying layout