VIATRA2/Benchmarks/Sierpinsky triangles Benchmark

Benchmark description

This benchmark was presented as one of the case study of the 2007 Agtive tool contest. The goal of this case study is to measure the performance of graph transformation tools constructing Sierpinski triangles. The Sierpinski triangle is a fractal named after Waclaw Sierpinski who described it in 1915. Originally constructed as a mathematical curve, this is one of the basic examples of self-similar sets, i.e. it is a mathematically generated pattern that can be reproduced at any magnification or reduction.

An algorithm for obtaining arbitrarily close approximations to the Sierpinski triangle is as follows:

Start with an equilateral triangle with a base parallel to the horizontal axis.
Shrink the triangle by 1
make two copies, and position the three shrunk triangles so that each triangle touches each of the two other triangles at a corner.
Repeat step 2 with each of the smaller triangles.

Metamodeling

From the programmers point of view, the most difficult part of implementing the Sierpinski triangle generator is to create the correct triangle ”finder mechanisms”. In our solution, we tried to adhere to the typing scheme found in the problem description by taking advantage of the multiple-inheritance support of the Viatra2 framework resulting the metamodel depicted in Fig. .

entity ( node );
entity (a);
entity (b);
entity (c);
entity (ac);
entity (ab);
entity (bc);
relation (e,node , node );
 
supertypeOf (node ,a);
supertypeOf (node ,b);
supertypeOf (node ,c);
supertypeOf (a,ab );
supertypeOf (a,ac );
supertypeOf (b,ab );
supertypeOf (b,bc );
supertypeOf (c,ac );
supertypeOf (c,bc );