Contraction of Unconnected Diagrams using Least Cost Parsing

Abstract

A free-hand diagram editor allows the user to place diagram components on the pane without any restrictions. This increase in flexibility often comes at the cost of editing performance, though. In particular it is tedious to manually establish the spatial relations between diagram components that are required by the visual language. Even worse are certain graph-like languages where it is a quite annoying task to explicitly link the node components.

In this paper diagram contraction is proposed for solving these issues. The editor user can just roughly arrange a set of diagram components. On request the editor automatically creates a correct diagram from these components while preserving their layout as far as possible. Moreover, for several languages diagram contraction corresponds to linking node components appropriately. Such auto-linking is considered useful. It even has been integrated into first commercial modeling tools.

The proposed approach can be applied to visual languages that are specified by means of hypergraph grammars. For syntax analysis an error-tolerant hypergraph parser is used, which computes a cost function by attribute evaluation. That way, unfavorable derivation (sub-)trees can be excluded at an early stage, and combinatorial explosion is mostly prevented.