Graph Layout Support for Model-Driven Engineering

Miro Spönemann

• Publisher: Books on Demand
• Year: 2015
• Print ISBN: 9783734772689
• eBook ISBN: 9783738660777
• Edition: 1
• Topic: Computer Science
• Subtopic: Information Technology
• Index: Computer Science

Automatic layout is an important tool for the efficient use of graphical models in a model-driven engineering (MDE) context. Since the 1980s, research on graph layout methods has led to a multitude of different approaches, and several free software libraries for graph layout are available. However, today's practically relevant MDE tools hardly reflect this diversity. This thesis aims to support the use of automatic graph layout in such tools.A special focus is on the requirements of data flow models, where constraints on the positioning of ports and the routing of hyperedges pose additional challenges. These constraints are approached with extensions of the layer-based graph layout method. Furthermore, we discuss an infrastructure for managing collections of layout algorithms, allowing to flexibly specify layout configurations. These concepts are implemented in an open-source project based on Eclipse, an extensible platform that is well-known as a Java IDE and also hosts a large number of MDE tools. The presented contributions allow to integrate high-quality automatic layout into these tools with low effort.

Chapter 1

Introduction

There is a striking contrast between the abundance of research results in the field of graph layout methods and the current state of graphical modeling tools, where only a tiny fraction of these results are adopted. This thesis aims to bridge this gap on three separate levels: specialized layout algorithms, configuration management, and software infrastructure. The goal is to increase the productivity of software engineering processes by improving the practical handling of models.

A model is an artifact that represents other artifacts with a purpose [Tha13]. In the field of computer science, usually this purpose is to facilitate the understanding of systems through abstraction. Many models are made with no formal basis, relying on the intuition and the knowledge background of their users. The model-driven engineering (MDE) approach¹ is based on formal models, leading to the notion of modeling languages [Sch06, SV06, FR07]. The concepts behind modeling languages are very similar to those of programming languages: they have an abstract syntax that determines the structure, a concrete syntax defining the actual representation, and a formal or informal semantics defining the meaning. There are general-purpose languages, e. g. following open standards such as the Unified Modeling Language (UML), or domain-specific languages (DSLs) designed for particular applications. A concrete syntax can be either one-dimensional, i. e. text, or two-dimensional (sometimes three-dimensional), in which case it is called a graphical representation. The main strength of MDE is the ability to automatically transform models from one representation to another, allowing to build models of a high abstraction level and then to generate models of a lower abstraction level. This is analogous to compilers, which generate low-level machine code from high-level programming languages.

A major advantage of graphical representations is that they allow to directly visualize relationships, whereas in text indirections through name references are often necessary. For this reason it is not surprising that the majority of graphical languages can be mathematically abstracted with graphs, i.e. collections of objects (nodes) and their relationships (edges). The concrete syntax of a textual language often prescribes the order of elements though its grammar. The elements of a graph, in contrast, can be arranged more or less arbitrarily on the two-dimensional plane. Some application domains limit this freedom in order to ensure a consistent appearance of model instances, e. g. requiring edges to point from left to right, but even then the problem of finding a suitable arrangement is much more complex compared to text.

A good graph layout must be readable, meaning that it must support the persons working with it in quickly understanding the underlying model. Readability depends on a variety of factors, named aesthetic criteria [Pur97, WPCM02, BRSG07]. From the beginning of the 1980s, a large number of research groups have sought for methods to optimize these criteria, a research field known as graph drawing [DETT99, KW01, Tam13]. Many different algorithmic approaches have been developed through these efforts, with different priorities on aesthetic criteria and application constraints. Among these, for instance, are methods for minimizing the number of edge crossings [Wei01], maintaining layout stability for dynamically changing graphs [Bra01], and considering special requirements of widespread notations such as UML class diagrams [See97, EGK+04a].

Automatic graph layout has the potential to boost the productivity of model-driven engineering as a key enabler of efficient model creation and exploration concepts [FvH10a, FvH10b]. A layout algorithm can relieve users from the time-consuming task of manually arranging graphical models, allowing them to focus on the semantic aspects of their system under development. Furthermore, graphical representations can be generated fully automatically [SSvH12a, SSvH13], e. g. from the results of model transformations or from textual notations. This includes the dynamic creation of optimized views for the efficient browsing of large collections of existing models [FvHK+14].

Looking at the modeling tools that have been in use during the past decade, however, one realizes that the state of the practice is quite far from fully exploiting the potential of automatic layout. Some tools offer only assistance for the horizontal or vertical alignment of selected nodes, e. g. Simulink² or SCADE³, and others include layout algorithms of rather low quality, e. g. the Eclipse Graphical Modeling Framework (GMF)⁴ or Ptolemy⁵ (a better algorithm has been built into the Ptolemy editor as a result of this thesis, see Section 5.1). I identified several possible reasons for this discrepancy between the scientific work and its realization in MDE environments.

P1

Users are skeptical about the quality of automatically generated layouts. This is similar to how automatic code generation was seen with concerns in the early days of MDE [Sel03].

P2

Domain-specific layout constraints are not adequately addressed by the established methods. In particular, constraints on the positioning of ports (connection points of edges) are hardly considered.

P3

Graph layout algorithms are complex and thus their implementation requires considerable effort. For the same reason, commercial graph layout libraries are quite expensive.

P4

The integration of graph layout libraries written in C or C++, e.g. Graphviz [GN00] or OGDF [CGJ+13], into other platforms such as Eclipse is an intricate task.

P5

Users are quickly overwhelmed by the multitude of graph layout methods and their configuration parameters. The usage of many parameters requires a detailed understanding of the underlying methods.

These problems are even more evident in the context of domain-specific languages, where the focus is often on light-weight modeling approaches with frameworks such as Xtext.⁶ Domain-specific notations require domainspecific layouts, i. e. a suitable layout algorithm must be found and configured. This task, however, is not well supported by today’s modeling platforms.

Figure 1.1. The approach of this thesis is structured in three layers: modeling applications with graphical viewers or editors (front-ends), a collection of specialized layout algorithms (back-ends), and a meta layout framework for controlling the algorithms.

1.1 Contributions of This Thesis

I propose a threefold approach to support the usage of automatic graph layout in modeling applications (see Figure 1.1).

1. Specialized layout algorithms address frequently occurring requirements in order to meet the needs of typical modeling applications. These algorithms are the back-ends of the layout infrastructure.
   
   
2. Layout algorithms are selected and configured in a process named meta layout. Configurations can be specified by tool developers, adapted by tool users, or determined automatically.
   
   
3. Viewers or editors for graphical model representations, the front-ends in the terminology used here, are connected to the layout infrastructure. These connections must be as generic as possible in order to allow simple and light-weight integrations.

The goal is to provide a large number of high-quality back-ends for use in a large number of front-ends. I believe that Problem P1, i. e. the widespread skepticism on the usefulness of automatic layout, can only be properly addressed if the overall quality of the layout infrastructure is convincing. This premise has to be considered in all three layers of the proposed approach. An outline of the concrete contributions of this thesis is given in the following.

Layer-based layout (Chapter 2). The layer-based graph layout approach is extended in order to support some domain-specific constraints (Problem P2). The main extension concerns port constraints, which ...

Table of contents

• About this Series
• Zusammenfassung
• Abstract
• Table of Contents
• Acronyms
• 1 Introduction
• I Layout Algorithms
• II From Theory to Practice
• Appendix
• Bibliography
• Copyright