Traverse DAGs with Xtend

Like OCL, Xtend (a sublanguage as part of the Xpand project for model queries) provides some really powerful collection operations. These operations allow to easily retrieve elements from arbitrary models, i.e. graphs. Searching a single element in a graph is often very simple with these operation. However, when a collection is to be returned (which is not stored in some attribute), this might be a little bit more complicated, especially if the order matters. In the following, I have assembled some examples showing how to traverse a directed acyclic graph (DAG) with some common traversal strategies:

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

Actually, traversing a connection in counter-direction is not really possible. What I mean by that is, that the query is to return the element of the non-navigable end of the connection. E.g., for a given directed connection x->y, x is to be returned for a given y.

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.