Auto-completion for Diagram Editors Basedn on Graph Grammers

Steffen Mazanek,Sonja Maier, Mark Minas Universitat der Bundeswehr, Germany

Summary:
The syntax or a particular visual language can be defined by means of a graph grammar. In an usual way of diagram editors,a diagram template is chosen and then empty texts are filled accordingly. However, the purpose of this paper is not selecting pre-defined template from editor but to enable editor to auto-complete diagram according to diagrams grammar.

For a given graph H and Hyper-Edge Replacement Grammar (HRG) G, H is first parsed into hyper-edges and nodes. A completion of H with respect to G is graph H' that again belongs to language G. To form H' there could be 2 types of modifications:
1.Inserting a new edge into H,
2. Connecting nodes of H.

Auto-completion of graphs are done as follows:
1. A spatial relationship hyper-graph(SRHG) is formed by neighbourhood relations within graph.
2. Sending this information to parser. Parser connects edges and forms a new graph.
3. If user asks for assistance and indicates desired size of completion.
4. It computes all possible graph completions up to the used defined size.
5. Selected graph is send to step 1.

The graph parser used in this paper is uses dynamic-programming techniques similar to Coke, Youngger and Kasami algorithm. In order to layout the graphs an constraint satisfactory problem technique is used.

Discussion:

Although paper accomplishes its target to complete graph, their proposition is not a very smart way of doing it. While taking assistance, offering all possible graphs is not very intelligent. Also, in order to add another node to the graph, user has to specify nodes to add. I don't think that this paper is relevant to topic of auto-completion because of these reasons.