
<h1>Henshin Example: Grid &amp; Comb Pattern</h1>

<p>
<small><i>contributed by Dmitry Zakharov and Christian Krause</i></small>
</p>

<p>
This example is taken from the technical report 
<a href="http://www.cs.bme.hu/~gervarro/publication/TUB-TR-05-EE17.pdf">Benchmarking for Graph Transformation</a> 
by Varr&oacute; 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).
</p>

<p>
<a href="examples/combpattern/structures.png"><img width="600" src="examples/combpattern/structures.png" /></a>
</p>

<p>
The transformation and the source code can be found
<a href="http://git.eclipse.org/c/henshin/org.eclipse.emft.henshin.git/tree/plugins/org.eclipse.emf.henshin.examples/src/org/eclipse/emf/henshin/examples/combpattern">here</a>. All benchmarks were run on a Intel(R) Xeon(R) CPU @ 2.50GHz with 8GB of main memory using Henshin 0.9.2.
</p>

<h2>Generation of a sparse grid</h2>
<p>
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 unit<i>buildGrid</i> which takes the two parameters <i>width</i> and <i>height</i> as input (both integers), and returns the constructed sparse grid using the parameter <i>grid</i>. 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 <i>startColumn</i> once, and <i>extendColumn</i> height-2 times.
</p>

<p>
<a href="examples/combpattern/grid-sparse-rules.png"><img width="600" src="examples/combpattern/grid-sparse-rules.png" /></a>
</p>

<p>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.</p>

<table>
<tbody>
<tr><th>&nbsp;Size&nbsp;</th><th>&nbsp;Nodes&nbsp;</th><th>&nbsp;Generation time&nbsp;</th></tr>
<tr><td> 20 </td><td> 400 </td><td> 163ms </td></tr>
<tr><td> 40 </td><td> 1.600 </td><td> 328ms </td></tr>
<tr><td> 60 </td><td> 3.600 </td><td> 382ms </td></tr>
<tr><td> 80 </td><td> 6.400 </td><td> 532ms </td></tr>
<tr><td> 100 </td><td> 10.000 </td><td> 935ms </td></tr>
<tr><td> 120 </td><td> 14.400 </td><td> 1.723ms </td></tr>	
<tr><td> 140 </td><td> 19.600 </td><td> 2.838ms </td></tr>
<tr><td> 160 </td><td> 25.600 </td><td> 4.882ms </td></tr>
<tr><td> 180 </td><td> 32.400 </td><td> 7.113ms </td></tr>
<tr><td> 200 </td><td> 40.000 </td><td> 12.118ms </td></tr>
</tbody>
</table>


<h2>Generation of a full grid</h2>
<p>
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 unit<i>buildGrid</i>. 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.

</p>

<p>
<a href="examples/combpattern/grid-full-rules.png"><img width="700" src="examples/combpattern/grid-full-rules.png" /></a>
</p>

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

</p>

<table>
<tbody>
<tr><th>&nbsp;Size&nbsp;</th><th>&nbsp;Nodes&nbsp;</th><th>&nbsp;Generation time&nbsp;</th></tr>
<tr><td> 10 </td><td> 100 </td><td> 54ms </td></tr>
<tr><td> 20 </td><td> 400 </td><td> 208ms </td></tr>
<tr><td> 30 </td><td> 900 </td><td> 217ms </td></tr>
<tr><td> 40 </td><td> 1.600 </td><td> 437ms </td></tr>
<tr><td> 50 </td><td> 2.500 </td><td> 877ms </td></tr>
<tr><td> 60 </td><td> 3.600 </td><td> 1.561ms </td></tr>	
<tr><td> 70 </td><td> 4.900 </td><td> 2.615ms </td></tr>
<tr><td> 80 </td><td> 6.400 </td><td> 4.162ms </td></tr>
<tr><td> 90 </td><td> 8.100 </td><td> 6.278ms </td></tr>
<tr><td> 100 </td><td> 10.000 </td><td> 9.238ms </td></tr>
</tbody>
</table>


<h2>Generating and matching the comb pattern</h2>
<p>
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 <i>combPattern</i>. The iterated unit <i>buildCombPattern</i> extends this basic rule by invoking the HO-rule <i>extendCombPattern</i> width-1 times. The rule <i>extendCombPattern</i> matches and transforms the rule <i>combPattern</i> (this is the higher-order part of the transformation). Note that the rule <i>extendCombPattern</i> 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.
</p>

<p>
<a href="examples/combpattern/comb-rules.png"><img width="700" src="examples/combpattern/comb-rules.png" /></a>
</p>

<p>
The following table shows the matching time for the comb pattern for the sparse and the full grid.
</p>

<p>
<b>Matching in the sparse grid (no matches)</b>
</p>

<table>
<tbody>
<tr><th>&nbsp;Grid size&nbsp;</th><th>&nbsp;Pattern width&nbsp;</th><th>&nbsp;Matching time&nbsp;</th></tr>
<tr><td> 200 </td><td> 20 </td><td> 49ms </td></tr>
<tr><td> 200 </td><td> 40 </td><td> 49ms </td></tr>
<tr><td> 200 </td><td> 60 </td><td> 52ms </td></tr>
<tr><td> 200 </td><td> 80 </td><td> 53ms </td></tr>
<tr><td> 200 </td><td> 100 </td><td> 55ms </td></tr>
<tr><td> 200 </td><td> 120 </td><td> 58ms </td></tr>	
<tr><td> 200 </td><td> 140 </td><td> 60ms </td></tr>
<tr><td> 200 </td><td> 160 </td><td> 65ms </td></tr>
<tr><td> 200 </td><td> 180 </td><td> 68ms </td></tr>
<tr><td> 200 </td><td> 200 </td><td> 71ms </td></tr>
</tbody>
</table>

<p>
<b>Matching in the full grid</b>
</p>

<table>
<tbody>
<tr><th>&nbsp;Grid size&nbsp;</th><th>&nbsp;Pattern width&nbsp;</th><th>&nbsp;Matches&nbsp;</th><th>&nbsp;Matching time&nbsp;</th></tr>
<tr><td> 100 </td><td> 10 </td><td> 9.009 </td><td> 620ms </td></tr>
<tr><td> 100 </td><td> 20 </td><td> 8.019 </td><td> 759ms </td></tr>
<tr><td> 100 </td><td> 30 </td><td> 7.029 </td><td> 538ms </td></tr>
<tr><td> 100 </td><td> 40 </td><td> 6.039 </td><td> 673ms </td></tr>
<tr><td> 100 </td><td> 50 </td><td> 5.049 </td><td> 777ms </td></tr>
<tr><td> 100 </td><td> 60 </td><td> 4.059 </td><td> 837ms </td></tr>	
<tr><td> 100 </td><td> 70 </td><td> 3.069 </td><td> 863ms </td></tr>
<tr><td> 100 </td><td> 80 </td><td> 2.079 </td><td> 909ms </td></tr>
<tr><td> 100 </td><td> 90 </td><td> 1.089 </td><td> 855ms </td></tr>
<tr><td> 100 </td><td> 100 </td><td> 99 </td><td> 806ms </td></tr>
</tbody>
</table>