GEF (Graph Editing Framework) is a library of Java classes for editing diagrams and graphs. It is used by ArgoUML for UML diagrams. For my SoC project I will implement a graph layout algorithm to automatically position the nodes and link bends of a graph in a way that is particularly suited to UML class diagrams.
The algorithm will be a combination of the well-known Sugiyama algorithm with some orthogonal drawing techniques. A UML class diagram has two main types of links - the inheritance relationships and the associations. The inheritance relationships form a hierarchical structure. In computing a layout I will use the Sugiyama algorithm to draw the classes involved in the inheritance relationships. The algorithm has four steps; it temporarily removes any directed cycles by reversing a small number of links, places the nodes on horizontal levels so that all links are directed similarly, permutes the nodes on each level to minimize the number of link crossings, and balances the layout. Then I will add in the remaining classes and the association links while preserving the basic structure. UML class diagrams have additional requirements that are not handled by generic graph layout algorithms, for example, the nodes do not have fixed size and the association links are labelled in a very particular manner. See [1] for a much more detailed description of the entire algorithm.
Contributions
My contributions will be:
- An implementation of the Sugiyama algorithm for drawing general directed graphs.
- A combination of this algorithm with some other additions specifically tailored for UML class diagrams (see [1]).
- A demo application.
An implementation of the Sugiyama algorithm with the additions described in [1] is a first-step to drawing UML class diagrams in ArgoUML. There are more advanced methods for the individual steps which may be looked at in the future. For example, it may be desirable to restrict the width of the drawing so that it 'fits' on a computer screen thus allowing a user to see everything by simply scrolling up and down.
References
[1] J. Seemann, Extending the Sugiyama Algorithm for Drawing UML Class Diagrams: Towards Automatic Layout of Object-Oriented Software Diagrams, Proceedings of Graph Drawing, 5th International Symposium, GD '97, Rome, Italy, September, 1997
Update: This was accepted :-)
