Andy Bulka

March 2011

Melbourne Patterns Group

www.andypatterns.com

Problem ʹ Untangling UML

Topics

y Spring Layout

y Mapping layout to Real World

y OGL

y MVC

y Overlap Removal

y Unit tests and unit test diagrams

y Memento Design Pattern

y Blackboard Design Pattern

y injecting sorting function

y Future...

Terms

y Nodes Ȃ these are the shapes/rectangles

y Edges Ȃ these are the lines connecting the shapes

Summary 1

y My UML tool is written in Python

y Existing layout libraries for e.g. python PyGraphviz has

no windows port so I wrote my own

y Layout is reasonably hard to implement Ȃ academic

papers are very complex and deal in a lot of math

y DIRTY SECRET OF ACADEMIA - Layout algorithms

only deal with Ǯpointsǯ and donǯt take into account real

width and height

Summary 2

y Thus you must run an overlap removal algorithm after

the layout to remove shape overlaps for any real world

use (unless dealing with network and particle

visualisation where each node is the same size/shape)

y Overlap removal algorithm needs to minimise shape

movement in order to respect the layout results

What I developed

y I used a Ǯspring layoutǯ adapted from java and

javascript

y I developed my own overlap removal algorithm

y Developed a GUI sandbox test app for development

Overlap Removal - Before and After

Unit Testing

y 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.

Unit Testing

y 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

y Loose tests using (e.g. I created ǮensureYorder ()ǯ etc) were

created so that the tests were not too brittle. Slight variations in

position are ignored.

def test3_5InsertedVerticallyTwoPushedDown(self):

self._LoadScenario3()

# move m1 to the left

node = self.g.FindNodeById('m1')

node.left, node.top = (6, 4)

# assert m1 has been inserted vertically - two pushed down

were_all_overlaps_removed = self.overlap_remover.RemoveOverlaps()

self.assertTrue(were_all_overlaps_removed)

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'))

Tests helped in refactoring

Final Results were pretty good!

Design Patterns Used - Memento

y 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

y Memento was used to save/restore layouts in my test

GUI Ȃ assigned to keys 0..9

Design Patterns Used - Blackboard

y 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)

def sortfunc(d):

# this does the thinking!

return (d['LL'], d['LN'], d['bounds_area_simple'], -d['scale'], d['NN_pre_OR'])

y Python goodness helped in this ǮAIǯ smartness

Future

y ǲ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

y Non straight lines and line routing is probably the

better direction

y Adding an understanding of UML semantics is

another direction to research, so that e.g. base classes

are above derived classes etc.

Code and Links

y Code is python, open source

y Part of my python UML tool PyNSource - link

Reverse engineer python source code into UML - display UML as Ascii art

or in a proper diagramming visual workspace. You can also generate

java and delphi skeleton code from the python, for the purpose of

importing that into other UML tools.

y See

http://www.andypatterns.com/index.php/products/pynsource/

y Contact

andy@andypatterns.com