# Bx Examples Repository

# Title: ListToTree

## Version: 0.1

## Type: Sketch

## Overview

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.

## Models

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

## Consistency

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]

## Discussion

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]

## Author(s)

Anthony Anjorin, Sebastian ThÃ¶ne

## Reviewer(s)

## Comments

## 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: