GPaR sofware
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^{AttH} such that ∀ x ∈ N_{H} ⊎ P_{H}, card(att_{H}(x)) is finite.
- 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.
- 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.
- 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.