Henshin Example: Grid & Comb Pattern

contributed by Dmitry Zakharov and Christian Krause

This example is taken from the technical report Benchmarking for Graph Transformation by Varró et al. This example consists of the following parts: construction of a sparse and a full grid, construction of a comb pattern using a higher-order (HO) transformation, and matching the comb pattern in the generated sparse and full grids. The involved structures are shown below (images taken from the TR).

The transformation and the source code can be found here. All benchmarks were run on a Intel(R) Xeon(R) CPU @ 2.50GHz with 8GB of main memory using Henshin 0.9.2.

Generation of a sparse grid

In this part, a sparse grid structure is constructed that consists of a number of columns which are not interconnected. The transformation rules and units are shown below. The main unit unit for constructing the grid is the sequential unitbuildGrid which takes the two parameters width and height as input (both integers), and returns the constructed sparse grid using the parameter grid. The construction works as follows: create width/2 many columns (each consisting of two vertical lines of nodes), where each column is built up step-wise by invoking startColumn once, and extendColumn height-2 times.

The following table shows the run time of the Henshin interpreter for different sizes of the sparse grid, where we used the same values for the width and the height.

 Size  Nodes  Generation time 
20 400 163ms
40 1.600 328ms
60 3.600 382ms
80 6.400 532ms
100 10.000 935ms
120 14.400 1.723ms
140 19.600 2.838ms
160 25.600 4.882ms
180 32.400 7.113ms
200 40.000 12.118ms

Generation of a full grid

Now our goal is to construct a full grid. The transformation rules and units are shown below. The main unit unit for constructing the grid is again the sequential unitbuildGrid. The construction of the full grid is different to the construction of the sparse grid. First, we create an initial grid with two nodes that are vertically connected. Second, we build up the first vertical line of nodes. Then, we step-wise add new columns to the grid, each starting from the top and working all the way down.

The following table shows the run time of the Henshin interpreter for different sizes of the full grid. The construction time is longer than for the sparse grid (note the different sizes). The reason for this is that in the construction of the sparse grid, the next nodes are passed to the rules which already provide a partial match. For the full grid, no node parameters are passed and negative application conditions are used to ensure that the correct position in the grid is used. This more involved matching process takes more time.

 Size  Nodes  Generation time 
10 100 54ms
20 400 208ms
30 900 217ms
40 1.600 437ms
50 2.500 877ms
60 3.600 1.561ms
70 4.900 2.615ms
80 6.400 4.162ms
90 8.100 6.278ms
100 10.000 9.238ms

Generating and matching the comb pattern

Now we want to construct the comb pattern with varying width. For this we use the transformation units and rules shown below. The comb pattern of width 1 is directly modeled using the rule combPattern. The iterated unit buildCombPattern extends this basic rule by invoking the HO-rule extendCombPattern width-1 times. The rule extendCombPattern matches and transforms the rule combPattern (this is the higher-order part of the transformation). Note that the rule extendCombPattern is therefore defined over the Henshin and the Ecore meta-model. If you want to define a high-order transformation, make sure that you import the runtime versions of both models.

The following table shows the matching time for the comb pattern for the sparse and the full grid.

Matching in the sparse grid (no matches)

 Grid size  Pattern width  Matching time 
200 20 49ms
200 40 49ms
200 60 52ms
200 80 53ms
200 100 55ms
200 120 58ms
200 140 60ms
200 160 65ms
200 180 68ms
200 200 71ms

Matching in the full grid

 Grid size  Pattern width  Matches  Matching time 
100 10 9.009 620ms
100 20 8.019 759ms
100 30 7.029 538ms
100 40 6.039 673ms
100 50 5.049 777ms
100 60 4.059 837ms
100 70 3.069 863ms
100 80 2.079 909ms
100 90 1.089 855ms
100 100 99 806ms