Henshin's Grid & Comb Pattern addresses a graph transformation benchmark 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. 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.
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.
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|
Matching in the full grid
|Grid size||Pattern width||Matches||Matching time|
contributed by Dmitry Zakharov and Christian Krause