List To Tree

Bx Examples Repository

Title: ListToTree

Version: 0.1

Type: Sketch


This example is a flattening transformation of a binary tree to a linked list.
The interesting aspect of the transformation is that the flattening process is largely left open, i.e., it is underspecified and many possible lists are consistent to the same binary tree.


The diagram below depicts a concrete binary tree to the left and one possible consistent list to the right.
A binary tree has a root element BinaryTree containing a single Node.
Nodes in the tree can have no children, a left child, a right child, or both left and right children.
A list consists of ListNodes, each with a single next node (apart from the tail of the list, which has no next node) and a single previous node (apart from the head of the list, which has no previous node).



The binary tree is used to induce a partial order on all nodes in the following manner: the direct children of a node are "less than" their parent.
Note that the nodes in the tree and the list are named to reflect this.

A list is consistent to a given binary tree iff it does not violate this partial order (see the example above).

Consistency Restoration

Properties [optional section]

Variants [optional section]


As this example can be expressed quite naturally with TGGs, it is a kind of "hello world" for TGGs, showing how graph transformations are naturally non-deterministic (running the transformation repeatedly gives almost always a different but consistent list/tree).

References [optional section]


Anthony Anjorin, Sebastian Thöne



Artefacts [optional section]

A virtual machine hosted on Share is available with a workspace containing both (Ecore) metamodels, the concrete example used above, and a TGG formalizing the consistency relation as a set of rules:
