Tutorial

Configuration

Environment managment

Graph managment

Rules managment

Execution managment

Introduction

This introduction consists in explaining how to use GPaR by developing a concrete project. we consider the problem of adaptive mesh refinement for curve approximation. Adaptive mesh refinement consists in creating iteratively new partitions of the considered space. Individual grid cells is selected for refinement if some conditions are satisfied. In this tutorial, triangle refinement is considered and the aim is to localize implicit functions defined by an equation depending on two variables x and y, namely f(x,y)=0. The attribute AN=(cN,xN,yN) on nodes N consists in the xy-coordinates of N, xN and yN and a boolean cN equal to f(xN,yN)≤ 0: There is no needs of attributes on ports. By default the position of the ports is computed automatically. The refinement must be applied only on the triangles containing implicit functions of f(x,y)=0. A triangle will be decomposed into 4 triangles if the three c-attributes of the nodes defining the triangle are not equal. This constraint gives two rewriting rules depicted below.


Mesh refinement rules

In this drawing, big dots correspond to nodes and squares correspond to ports. The purple parts correspond to the environment parts. They allow to reconnect the new parts (in green) in the rewriting graph. The red parts correspond to the cut components. The environment part of the right-hand side must be included in the environment part of the left-hand side. It corresponds to the part needed to reconnect the new part in the rewritten graph. The environment part of the right-hand side cannot be removed by the action of an other rule, whereas the environment part of the left-hand side can be removed by the action of an other rule. In these specific example, nodes α, β and γ of the left-hand side are useful to compute the attributes of the new nodes U, V and W. For both rules :
xU= (xα+xβ)/2, yU= (yα+yβ)/2, cU==(f(xU,yW) ≤ 0).
xV= (xγ+xβ)/2, yV= (yγ+yβ)/2, cV==(f(xV,yV) ≤ 0),
xW= (xα+xγ)/2, yW= (yα+yγ)/2, cW==(f(xW,yW) ≤ 0).

Step by step, we will see how this problem can be modeled and implemented in GPaR. Successively, we will fill in

Finally, the run window and the visualization windows are dedicated to the computation of the defined system and the graph results visualization.

Once GPaR is launched, the following window appears:

Main window

Create your project by click on icon , or select Project in the menu of the main window and select New Project. See the project management subsection for more explanations.

To configure the option of the soft, the preferences window can de edited by clicking on Edit->Preferences item. See the preferences section.

Environment definition

To define the bivariate function f, click on the global environment button . The following window appears:

environment window


To add f as a global function, click on the ... button in the Global Functions area to make appear the Functions Window:

functions window


To declare the function, it is necessary to define:
  • its name: f
  • its parameters : 2 const reals called x and y
  • its return type which is a real
  • its body of instructions: for the tutorial f corresponds to the heart function and is defined by (x^2+y^2)^3-x^2*y^3
For more explanations on the declaration of functions, see the Environment Managment section.

Attributes definition

The next step consists in defining the attributes of the elements of the graph which can be either a node, a port or an edge. Click on the button to define the attributes of the elements of the graph.

state of the elements of the graph

In this window, select the graph element type whose state has to be defined and set the name, type, cardinality and default value of the new attribute. By default, positions of ports and nodes are already defined as attributes. Thus, in our example, we only have to add the node attribute c. The boxes have been filled in the following way :

  • element type: nodes,
  • name: c,
  • type: boolean,
  • multiplicity: 1 and
  • default value: false.
To add the variable in the environment of the node attribute, click on the add button . The Update Graph button allows to save all the modifications made in the graph state window, otherwise all the modifications are not taken into account. For more explanation about the graph state window, see the Attribute managment subsection.

Rules definition

The next step is to define the rewriting rule. To do so, click on the button to show the rule window.

rules settings window
The purpose of this window is, for each rule of the system, to
  • define the left-hand side and the right-hand side of each rules,
  • define the parallel rewrite relations which will be apply between full parallel rewrite relation and parallel rewrite relation up to automorphisms
  • define, if needed, which nodes and ports attributes will be taken into account for the matches.
  • define, if needed, the mapping rule
For more explanations on these actions, see the Rule Managment section.
The first row indicates the rule index of the rule printed in the window. The 4 buttons are :
  • add to add a new default rule
  • duplicate to add a copy of the current rule
  • delete to delete the current rule
  • clear to set the rule to the default one.
So, in our case, to add a rule, click first on the add button.
The option parallel rewrite relation up to automorphisms must be chosen in order to prevent several matches on each triangles. In this example, at most one match is applied per triangle.
To define the graphs which corresponds to a rule, click on the ... button. The Rule Graph Window appears

Rule Graph Window
By default the drawing area is locked to avoid unwanted changes. To unlock the drawing area, click on the unlock button in the menu panel under the tool bar.
To add a vertex ( a node or a port) , put the mouse's pointer on the point on the drawing area where you want to create the vertex and click on the right button of the mouse to make appear the popup menu:
.
Select the wanted item to add a vertex either in the left-hand side or in the right-hand side of the rule. Note that the two parts of the rule are defined in a single frame. The nodes and ports of the environment part which occurs in both the right and the left hand sides are considered as parts of the left-hand side with a specific label (see below for further explanations). All vertices have an Id which are defined automatically by GPaR. If a vertex of Id i belongs to the left-hand side, its label will be P_i, whereas if a vertex of Id i belongs to the right-hand side, its label will be T_i.
To create an edge between two vertices, put the mouse's pointer on one of the two vertices and click on the right button of the mouse to make appear the popup menu :
.
Select the wanted item and maintain the button pushed.
  • add edge to node : to add an edge from the existing source vertex to an other node created at the point where the mouse button is released.
  • add edge to port : to add an edge from the existing source vertex to an other port created at the point where the mouse button is released.
  • add edge : to add an edge between 2 existing vertices, release the mouse button on the target vertex
  • delete vertex : to delete the selected vertex (node or port).

Note that a correct graph is a graph which verifies:
  • a node can only be connected to ports
  • a port can only be connected to at most one node and at most one port

If an edge is added between 2 nodes, 2 ports are automatically created. If the connection is impossible, an error message appears.

To define the rewriting rules, create first the triangle of the left-hand side. In this tutorial, the nodes of the triangle are named P_0, P_1, P_4 and the ports are named P_2, P_3, P_5, P_6, P_7, P_8. Graphically, the nodes are represented by dotes and the ports by squares. The size of those objects can be modified by using the menu panel under the tool bar. The color of the left-hand side is purple but again, this specification can be modified in the preference menu. Now create the right-hand side by creating the nodes T_0, T_1, T_2 and the ports T_3, T_4, T_5, T_6, T_7, T_8, T_9, T_10, T_11, T_12, T_13, T_14. The subgraph supported by those vertices is represented in green. To connect the purple graph with the green graph which corresponds to the new part of the right-hand side of the rewriting rule, the edges (T_9,P_3), (T_10,P_2), (T_11,P_7), (T_12,P_8), (T_13,P_5), (T_14,P_6) have to be added.
But if we do so, an error message will appear indicating that the graph is no longer valid. It's due to the fact that if we add the connection (T_9,P_3) , the port P_3 will have 2 port-port connections !
First we have to signal that the port-port connections (P_2,P_3), (P_5,P_6) and (P_7,P_8) have to be removed. To do this action, put the pointer of the mouse in the edge, click on the mouse's right button and select the item add trigger cut action of the popup menu which appears to indicate that this connection has to be removed. (Note that this action is different from delete edge which is the action to delete the edge from the pattern graph to find.). The edges (P_2,P_3), (P_5,P_6) and (P_7,P_8) become red to validate the fact that the action is taken into account.
After this, you can add the edges (T_9,P_3), (T_10,P_2), (T_11,P_7), (T_12,P_8), (T_13,P_5) and (T_14,P_6) which are colored in blue.
The color of the ports P_2, P_3, P_5, P_6, P_7 and P_8 become automatically black. That means that those ports belong to the right-hand side and of the rule must be kept during the execution of the rules. This implies that if the port is supposed to be removed by applying another rule, the program will stop because of incompatibility rules at execution. The user can remove this trigger action by selecting the item delete keep trigger action from the popup menu which appears by clicking on the right button of the mouse whose pointer is on the port P_2, for instance. That implicates that if the port P_2 must be deleted by applying another rule , the program will continue without error but the connection (T_9, P_3) could not be created !

The state of the new node in green has to be defined. If no specification is given, the positions of new nodes would be (0,0,0) and the other attributes would get the default value. The states of new elements can depend on the states of the elements of the left-hand side. In our case, T_0 must be situated midway between P_1 and P_4, T_1 must be situated midway between P_0 and P_4, and T_2 must be situated midway between P_0 and P_1. Moreover, the state c_T_0, c_T_1 and c_T_2 must be set to true if the value of f at its coordinates is negative.
For instance, the coordinates of the node T_0 must be at the middle of the segment [P_1,P_4] :
put the mouse pointer on the node T_0 and select the edit vertex after clicking on the right button of the mouse to make appear the popup menu or click twice on the node T_0.
The following window appears:

vertex window

In this window, appear from top to bottom:
  • identity number of the node which can only be changed if the new id does not exist in the graph
  • Coordinates of the node
  • default state environment value
  • trigger actions
  • list of edges connected to the node

The trigger action corresponds to the function which has to be applied on state. In this tutorial, we want to return the boolean value corresponding to true if the implicit function at the point is negative. it can be translated as follow: return [f(T_0[0],T_0[1])<=0];
T_0 is the point of the new part with id 0, T_0[i] is the i-coordinate value of the point.
To set the coordinates of T_0, select T_0 on the combo box selection after trigger action, and set the point to the middle of segment [P_1,P_4], translated as follow: return [0.5*(P_1+P_4)];
For more explanations on setting rules on state of window see the state managment subsection.
For more explanations on the syntax of algebraic formula, see the math formula parser subsection.
Proceed in the same way for the nodes T_1 and T_2. Remark that the state of the vertices of the left-hand side can also be modified. In this case the compatibility of the state vertices is checked during the reconstruction of the rewritten graph. If a attribute vertex has 2 different values, a error message appear.
Having decided on the rule and the states of new elements, we must decide the conditions of matches. This has to be done in the Rules Window.
  • In the box node attributes to be matched, node attributes which have to be taken into account for the matches have to be added.
  • In the box port attributes to be matched, port attributes which have to be taken into account for the matches have to be added.
  • In the box mapping constraints, We can define constraints involving states of elements of the rewriting rule. In that case, matches are considered only if the constraints are satisfy.
At this step, we can model our rewriting system in two ways:
  • The first model consists in defining 2 different rules which look like quiet the same. They are all based on the rule defined previously, the only difference between the two rules is that :
    • for the first rule, c_P_0==T, c_P_1==F and c_P_2==T.
    • for the second rule, c_P_0==T, c_P_1==F and c_P_2==F.
    Moreover, the attributes c is added in the box node attributes to be matched.
  • The second model consists in having only one rule. To select only the triangles whose nodes have different c-state, we have to add a mapping constraint. It can be defined as follows :
    var isValid:=(c_P_0!=c_P_1);
    isValid:=isValid or (c_P_1 != c_P_4);
    isValid:=isValid or (c_P_0 != c_P_4);
    return [isValid];
Once the rules are defined, the initial graph has to be defined by clicking on the button of the main window.

Initial Graph definition

We would like to generate a grid in the rectangle [-2,2] × [-2,2] of the 2D-plane. We can do it by hands but we can use the generate grid item of the edit menu of the graph window:

grid generator window

Choose the isosceles triangular mesh to obtain the following grid:

grid generator window

The initial value of the state of the graph's element can be setting by double clicked on the graph element. Its graph element window appears and it is easy to set the value of the attributes of the state. Here, we see in red the nodes whose the c attribute is true and in purple, the nodes whose c attribute is false.
It is possible to show the value of the state of a graph element (node, port or edge) by selecting the corresponding state we want to show.
Here we have selected the c attribute of node, the id of ports and edges.
For more explanations on this window, see the graph managment section.

Execution process

The parallel application of a set of rules rewrite an initial graph named g0 into a new graph named g1 in one step. In the example of mesh refinement, several parallel iterations are needed in order to obtain a precise approximation of the implicit curve of f(x,y)=0. At the second iteration, g1 is rewritten into g2, etc) To perform the parallel graph rewriting process on the initial graph, click on the execute button, the Run Window appears.

run window

  • Iterations done indicates the number of iterations t 0 done or the initial iteration number for a restoring process.
  • Iterations number indicates the number t of iterations which is required by the user.
  • The check boxes Print log and debug mode enable to print the debug messages in a log text file in order to detect why and where the process failed.
  • The Show log button allows to see the log file on a text window.
  • The Re-start button performs the computation from the initial graph g0 until gt.
  • The Run button run the process from gt0 to gt.
When the work is finished, the result window appears:

Results visualization

movie window

The movie window enables to see the graph evolution over the iterations. It is possible to print the value of the state of nodes, ports or edges by selecting the states to show from the bar and to choose the width for vertices and edges representation as line or disk from the bar .
It is also possible to show (or mask) nodes, ports or edges and to adjust the delay between two iterations in seconds from the tool bar .
For more explanations, see the Execution managment section.