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= (NH, PH, PNH, PPH, AttH, attH) such that: In this context, a graph, g, corresponds to a pregraph g=(N, P, PN, PP, Att, att) such that: For a system of rewriting rules R = {li → ri, i = 1 . . . n}, the left-hand sides li and the right-hand sides ri 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: Once the initial graph g, the rules and the rewrite relation are defined, GPaR proceeds sequentially to the following tasks :
  1. It selects all the subgraphs of g whose elements match one of the pattern li,
  2. If the parallel rewrite relation "is up to automorphism" then it reduces the set of matches to the set of matches up to automorphism;
  3. It replaces all the matches of all the li by a variant of ri. The states of nodes and port are computed according to the rules. A pregraph has been created.
  4. 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