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).