Roughly sketch your diagrams

In recent posts I have already demonstrated the power of diagram completion.

In the paper I have presented at this year's LED workshop, I have shown how diagram completion can be used in order to facilitate a completely novel(?) approach to diagram editing. It is enough to just roughly sketch your diagram. You do not need to hit the mark quite precisely anymore as required in traditional diagram editors. Rather the completion engine computes all ways, how the diagram can be put together. Thereafter, the completion causing minimal change to the layout of existing diagram components is selected automatically! I am quite sure that this feature can boost the accessibility of diagram editors.

Example:

This figure shows how tedious the manual correction of a roughly sketched diagram can be. At least three complex mouse dragging operations are necessary here. The completion engine would yield two results for this example, the diagrams A and B given in the upper row. However, it is quite clear which diagram the editor user would prefer: the one with minimal changes to his components, namely A. A shortcut that automatically applies completion A could greatly improve editing performance.

However: This approach is only possible as long as there are not too many possible compositions of the fragements. For instance, n disconnected NSD statements can be put together in n! ways. As a consequence, the user would have to invoke the completion engine every few steps. Even so, this kind of assistance is still useful.

• S. Mazanek, S. Maier, M. Minas. Exploiting the Layout Engine to Assess Diagram Completions. Proc. of the 2nd International Workshop on Layout of (Software) Engineering Diagrams (LED 2008), 2008. Electronic Communications of the EASST.

Visual Week up and running

The Visual Week in Herrsching, Germany is already up and running. Yesterday the Workshops Layout of (Software) Engineering Diagrams and Sketch tools for diagramming took place. I attended LED where I gave a talk with the title "Exploiting the Layout Engine to Assess Diagram Completions" (paper and slides). But I also really enjoyed the other talks that covered a wide range of topics from industry projects to sophisticated graph layout approaches. A highlight was the 3D UML Heuristic Challenge. We have been divided in several groups and had to solve given tasks. My group had to think about the differences in 2D and 3D usability heuristics and, subsequently, evaluate a given tool using the heuristics we just developed.

Today the ACM SoftVis conference has started and a graduate consortium took place (many exciting new ideas!).

Usability

In this post I briefly discuss usability. First of all, I have to say that there is so much research that it is nearly impossible to write a short blog post about this topic. For instance, Jakob Nielsen, a popular usability expert, writes about usability for years. So I will just give you a quick impression by introducing the GOMS approach, which I found very straightforward and easy to apply. I especially use it to evaluate the task performance of my approach to diagram completion.

GOMS is an acronym for Goals, Operators, Methods, and Selection rules. The approach, however, is much easier than these terms suggest. The key idea is, that you write down all operations that have to be performed in order to achieve a given goal. Depending on its kind a predetermined execution time is attached to each of these operations. For instance, a keystroke takes 0.28 seconds for an average user, pointing with the mouse to an object on the screen lasts round about 1.1 seconds. There are several more kinds of actions and appropriate average times (determined on an empirical base). Summing up the times for all necessary operations finally yields the task execution time. Once you have this time you can compare different user interfaces, you can evaluate changes to the user interface and so on. It's that easy.

Note that in the context of the Visual Week (15.-21.09.08 in Herrsching am Ammersee, Germany) there will be a tutorial on another popular usability approach called Cognitive Dimensions. Here, usability is evaluated on a much higher level. To quote from the tutorial website (accessed 19 July 2008):
The Cognitive Dimensions of Notations (CDs) framework is the world's leading approach to understanding the usability of programming tools. It provides an analytic framework and design vocabulary that can be used to evaluate and improve, not only programming languages, but a wide variety of environments and notations for design, problem-solving, and creative work.

Currently I apply usability evaluation methods to my approach on diagram completion. In my talk "Exploiting the Layout Engine to Assess Diagram Completions" to be held at the layout workshop LED 2008 (satellite event of VL/HCC 2008) I will present a first improvement: in certain situations a special shortcut can more than double the task performance (to speak in terms of GOMS). Stay tuned!

Further reading:

• Stuart Card, Thomas P. Moran and Allen Newell: The Psychology of Human Computer Interaction. 1983.


• GOMS Model Work, comprehensive website about GOMS maintained by David E. Kieras.

RTA 2008

I am just back from the RTA 2008 (Rewriting Techniques and Applications) conference in Linz. My talk has been on Wednesday and was about Functional-logic Graph Parser Combinators. I already have written on this blog about graph parser combinators, but this purely functional approach had several problems we solved using functional-logic programming techniques. In particular, the new framework can be used as a back-end for my approach to diagram completion.

Hagenberg, the conference location, is a nice little village 20km away from Linz. It has a romantic, medieval castle in which the conference took place. Furthermore, an important branch of the FH Oberösterreich is located here.

From the talks I attended I especially liked the invited one by Thomas Hillenbrand about the theorem prover Waldmeister which is known to be very fast and powerful. Recently, the popular computer algebra system Mathematica even incorporated the Waldmeister approach to equational theorem proving into its tool suite.

Although I do not know much about automatic theorem proving there have been some impressive facts I remember from the talk. First of all, it is still very important to think about the most efficient data structures for a particular application. In theorem proving execution time and memory usage are really a big issue, so every little improvement of the data structures might make a decisive difference. And second, there is no all-in-one algorithm suitable for every application domain. Thus, it is important to provide a flexible framework that can be parameterized by the users. In Waldmeister one has to choose among several weighting functions from which each one is superior for some special domains. Finally, automatic theorem proving has advanced a lot in the last years. Even for some "real proofs" there is a good chance that they can be found without much manual investigation.

Logic gates

In previous posts I already have discussed several visual languages like VEX, Trees or ER diagrams. These languages have in common that all of them are used by computer scientists. Of course, visual languages also exist in other domains (in fact, visual notations are much older than computers).

In this post I show an editor for a language mainly used by electrical engineers: Logic gates. This is a visual notation for logic expressions that can be used in the domain of circuit design. Expression languages normally are context-free (although often some kind of sharing is used that cannot be described in a context-free way).

Again my approach to diagram completion is applicable, so we get a powerful editor for logical expressions. Here is a screencast demonstrating its use:



I also provide this screencast at an extra site, if this one is two small. You can also download this logic editor as an executable jar (however, keep in mind that this is still a research prototype).

Finally, let me admit that in the last time the most posts have been related to my own approach. I hope you forgive me this way too restricted focus. I will soon attend ICGT and VL/HCC conferences and the LED workshop, where I surely get inspiration for other interesting topics. You might also consider suggesting topics you are interested in for discussion. Of course, if you want to write something about a fancy tool, I gladly publish your description here as a guest contribution.

Course on Visual Languages

I already have written several posts about our previous course on graph and model transformation conducted in autumn last year and the practical afterwards. Next autumn we will hold another course, this time directly on visual languages. We will discuss approaches to language definition like extended positional grammars, constraint multiset grammars, hyperedge replacement grammars, and, of course, metamodels. I look forward to report on these approaches here soon.

Similar courses and practicals have been conducted at several universities in the past (e.g. at Universität Bremen (Berthold Hoffmann), CAU Kiel (Hauke Fuhrmann), RWTH Aachen (Manfred Nagl), Philipps-Universität Marburg (Gabriele Taentzer)). I would appreciate very much any comments on the lessons learned while conducting these courses.

Trees

Trees are a central data structure in computer science. A lot of visual languages have a tree-like structure, for instance class hierarchies with single inheritance, family trees or organizational charts. In contrast to the language of all graphs the sublanguage of trees can be described in a context-free way with a hyperedge replacement grammar:



However, this straightforward definition is problematic: A given tree might have a lot of derivations, i.e., the grammar is highly ambiguous. It is simply not clear in which order sibling nodes have to be derived. Therefore, it might be a better idea to encode this order in the grammar explicitly:



An example tree then is represented as follows:



Since my approach to diagram completion is applicable to all visual languages that can be defined with hyperedge replacement grammars, a powerful tree editor with completion can be realized easily. Here is a screencast demonstrating its use:



I also provide this screencast at an extra site, if this one is two small. You can also download this tree editor as an executable jar (however, keep in mind that this is still a research prototype).