GPaR 1.0x

GPaR is a parallel graph rewriting software implemented in C++ with a graphical user interface. This freeware tool has been developed by Grenoble University.

GPaR main goal is to rewrite a graph denoted g into a graph g' by using, simultaneously, rewriting rules.
GPaR deals with overlapping matches and thus can be used for a large variety of rewriting problems including cellular automata or L-systems.
To tackle this problem of overlapping matches, an extended definition of graph is used. Usually, a graph is defined by an order pair (V,E) where V is the set of vertices and E a set of edges. Here, two types of vertices are identified: V=N ∪ P where N is a set of attributed nodes and P the set of attributed ports. Ports have a central role in ensuring the effective connection between the remaining parts of g in g' and the new parts. The methods used in GPaR are based on the theoretical results of "Parallel graph rewriting with overlapping rules" of Rachid Echahed and Aude Maignan ( CoRR, abs/1701.06790, 2017).

Formally, we define a general structure called pregraph :
A pregraph H is a tuple H= (N_H, P_H, PN_H, PP_H, Att_H, att_H) such that:

N_H is a finite set of nodes and P_H is a finite set of ports,
PN_H is a relation PN_H ⊆ P_H × N_H,
PP_H is a symmetric binary relation on ports, PP_H ⊆P_H × P_H,
Att_H is a structure of attributes,
att_H is a function att_H: P_H ⊎ N_H → 2^Att_H

In this context, a graph, g, corresponds to a pregraph g=(N, P, PN, PP, Att, att) such that:

PN is a relation ⊆ P × N which associates at most one node to every port.
PP is a symmetric binary relation which associates at most one port to another port.

For a system of rewriting rules R = {l_i → r_i, i = 1 . . . n}, the left-hand sides l_i and the right-hand sides r_i must be graphs. GPaR rewrites the graph g into the graph g' by firing, simultaneously, the rules of R whose left-hand sides match subgraphs of g. Two parallel rewrite relations have been implemented in GPaR:

full parallel rewrite relation: g is rewritten in g' using all the possible matches (including eventual permutations of the same set of nodes and ports).
parallel rewrite relation up to automorphisms: If a set of matches is obtained from one rewrite rule on a same set of nodes and ports then only one match of this set is used during the rewriting process. Confluence results can be found in the paper cited above.

Once the initial graph g, the rules and the rewrite relation are defined, GPaR proceeds sequentially to the following tasks :

It selects all the subgraphs of g whose elements match one of the pattern l_i,
If the parallel rewrite relation "is up to automorphism" then it reduces the set of matches to the set of matches up to automorphism;
It replaces all the matches of all the l_i by a variant of r_i. The states of nodes and port are computed according to the rules. A pregraph has been created.
It merges ports and edges accordingly to the rewriting modulo approach.

GPaR is a standalone software whose graphical user interface is inherited from the Qt library. It is based on Boost Graph Library to match subgraphs thanks to the BGL vf2 subgraph isomorphism algorithm routine (see Herb Sutter and Andrei Alexandrescu Boost c++ libraries).
It also uses a mathematical expression library based on Fast c++ math expression parser and evaluator to manage the rewriting rule definitions and graph state definition.
GPar is composed of several windows which are

the environment window to define the global constants and the global functions of the problem,
the graph state window to define the attributes of the components of the problem,
the initial graph window to define the initial graph g,
the rules window to define the system of rewriting rules R.
Finally, the run window and the movie graph windows are dedicated to the computation of the defined system and the graph results visualization.