1) unsorted search traversing directed connections

2) depth-first search traversing directed connections

3) breadth-first search traversing directed connections

4) traverse a directed connection in counter-direction

5) unsorted search, traversing directed connections in counter-direction

6) depth-first search traversing directed connections in counter-direction

7) breadth-first search traversing directed connections in counter-direction

### Example: a type hierarchy.

For the examples, I use a "real" world example: a type hierarchy. Our (very simple) model looks like that (in pseudo Java code):Type { String name; Collection<Type> super; }Let's also assume a container in which all types are stored, e.g.

Collection<Type> allTypes;In OCL, you can even retrieve all types by a simple query, however we often have some type of container defined in our model anyway (and we use Xtend here ;-) ).

For testing the code, I have defined a concrete example. The following type hierarchy visualizes some type instances, the super types attributes are drawn as connections: That is, we have a base type

`A`

. `B`

, `C`

, and `D`

are direct subtypes of `A`

. `E`

is a subtype of `B`

. `F`

is a subtype of `B`

and `C`

(we allow multi inheritance ;-) ), and so on. *Preliminary remarks:*

- I haven't looked into any algorithm book to find the best algorithm (what ever "best" means). The solutions below are simply the one I implemented when I needed it, without much thinking about the algorithm. If you know a better solution, please let me know!
- I'm using
`create`

extensions for simplicity and performance reasons here. If you have small (or mid sized) models, I'd assume this would be ok. - Although Xtend is quite similar to OCL, the algorithms will probably not work with OCL, as OCL is side effect free (and I modify collections in the algorithms, which will not work that way with OCL).

### Super type queries (or: traverse directed connection)

Since we store the super types in the model, the easiest query is to retrieve the direct super types of a type. E.g., `A.super`

returns an empty list; `F.super`

returns `B, C`

. Now, lets calculate the transitive closure of super types. This is very easy with Xtend:

**1) Transitive closure of super types, unsorted:**

create Set[Type] superTypesTransitive(Type type): this.addAll(type.supers) -> this.addAll(type.supers.superTypesTransitive());

We use a set in order to avoid duplicates, which would be added in case of multi-inheritance. This solution is straight forward. If you are not used to OCL syntax, you may be a little bit confused by the implicit syntax for the `collect`

operation: `type.supers.superTypesTransitive()`

returns `superTypesTransitive()`

for all `type.supers`

elements.

`J.superTypesTransitive()`

will return `F,B,C,A`

, just as expected. (J.superTypesTransitive() is just more OO-like way for writing superTypesTransitive(J). Frankly, I don't know if this is better readable, but it definitely looks cooler ;-)). The returned collection is not ordered, and often enough this is sufficient. However, sometimes we need the collection to be ordered. There are two often used strategies for traversing a tree or DAG: depth first search and breadth first search. We will implement both.

**2) Transitive closure of super types with depth first search order:**

create List[Type] superTypesTransitiveDFS(Type type): type.supers.forAll(s| this.add(s)-> this.addAll(s.superTypesTransitiveDFS().reject(e|this.contains(e))) !=null);

As we need a sorted collection, we have to use a list instead of a set. However, we have to reject duplicates in our code now. Since Xtend does not provide a loop statement, I have used the collection operation `forAll`

here. Since the forAll operation expects a boolean expression inside, the `!=null`

part "casts" our chained expression into a boolean expressions. If you know of a nicer solution, please let me know.

`J.superTypesTransitiveDFS()`

will return `F,B,A,C`

.

**3) Transitive closure of super types with breadth first search order:**

create List[Type] superTypesTransitiveBFS(Type type): let todo = new java::util::ArrayList : todo.addAll(type.supers) -> bfsSuper(this, todo); private Void bfsSuper(List[Type] result, List[Type] todo): if todo.isEmpty then Void else result.add(todo.first()) -> todo.addAll(todo.first().supers.reject(e|todo.contains(e) || result.contains(e))) -> todo.remove(todo.first()) -> bfsSuper(result, todo);

The breadth first search is a little bit more complicated, as we need a helper list, and a helper method. Note that we cannot create an Xtend type of `List`

here, instead we have to use the Java `ArrayList`

, which is available when we use the JavaBeans Metamodel in the project's Xpand/Xtend settings.

`J.superTypesTransitiveBFS()`

will return `F,B,C,A`

.

### Sub type queries (or: traverse connections in counter direction)

So, we have three different queries for super types. Now we want to write the very same queries for sub types. Unfortunately, the sub type information is not directly stored in the model but must be derived instead. First, we write a simple query for the direct sub types:

**4) Computes direct sub types (navigate in counter-direction):**

create Set[Type] subTypes(Type type, Collection[Type] allTypes): this.addAll(allTypes.select(k|k.supers.contains(type)));

This solution relies on the afore described queries. Frankly, I needed some time to figure it out (as I'm more an imperative and OO guy ;-) ) and I was really surprised how short (one line) it is. If you have to write that with Java, you will need a lot more lines. So, if you ever wondered why to use a special transformation language -- this is at least one argument.

Now, let's compute the transitive closure:

**5) Transitive closure of sub types, unsorted:**

create Set[Type] subTypesTransitive(Type type, Collection[Type] allTypes): this.addAll(allTypes.select(k|k.superTypesTransitive().contains(type)));

Note that this query does not rely on the subTypes extension, but only on the super type queries. Since we use a `Set`

, we do not have to take care of duplicates. Again: A Java solution would be much longer.

`A.superTypesTransitive(allTypes)`

will return `B,C,E,G,H,I,J,D,F`

Now, let's implement the depth first search for sub types:

**6) Transitive closure of sub types with depth first search order:**

create List[Type] subTypesTransitiveDFS(Type type, Collection[Type] allTypes): type.subTypes(allTypes).forAll(s| this.add(s)-> this.addAll(s.subTypesTransitiveDFS(allTypes).reject(e|this.contains(e))) !=null);

Since we have implemented an extension for subTypes, the solution is quite similar to the super kind depth first search algorithm.

`A.subTypesTransitiveDFS(allTypes)`

will return `B,E,F,I,J,C,D,G,H`

. Note that we cannot simply use the unsorted solution with a list instead of a set, as this will not result in a depth first search order (in our case, it would return something like `B,C,D,E,F,I,J,G,H`

). The same is true for superTypesTransitiveDFS, by the way. Last but not least the breadth first search for sub types.

**7) Transitive closure of sub types with breadth first search order:**

create List[Type] subTypesTransitiveBFS(Type type, Collection[Type] allTypes): let todo = new java::util::ArrayList : todo.addAll(type.subTypes(allTypes)) -> bfsSub(this, todo, allTypes); private Void bfsSub(List[Type] result, List[Type] todo, Collection[Type] allTypes): if todo.isEmpty then Void else result.add(todo.first()) -> todo.addAll( todo.first().subTypes(allTypes). reject(e|todo.contains(e) || result.contains(e))) -> todo.remove(todo.first()) -> bfsSub(result, todo, allTypes);

This algorithm also resembles the one for super types. By the way: I didn't find the `let`

expression explained in the documentation of Xtend (however, some examples use it). Did I miss it or is there really more OCL in Xtend as told in the docs?

`A.subTypesTransitiveBFS(allKinds)`

will return `B,C,D,E,F,G,H,I,J`

, which is easily validated as this is the order of the types as shown in the little figure.

## No comments:

Post a Comment