A Heuristic for the Subgraph Isomorphism Problem in Executing PROGRES
A. Zündorf
The work reported here is part of the PROGRES (PROgrammed Graph
Rewriting Systems) project. PROGRES is a very high level multi
paradigm language for the specification of complex structured
data types and their operations. The data structures are
modelled as directed, attributed, node and edge labelled
graphs (diane graphs). The basic programming constructs of
PROGRES are graph rewriting rules (productions and tests)
and derived relations on nodes (paths and restrictions). These
basic operations may be combined to build partly imperative,
partly rule based, complex graph transformations by special
control structures which regard the nondeterministic nature
of graph rewriting rules.
In order to use PROGRES not only as a specification language but
also for building rapid prototypes and even for the derivation
of final implementations, we have to be able to execute PROGRES
specifications efficiently. The central problem in executing
a graph rewriting system is to match the left-hand sides of
the executed graph rewriting rules to their isomorphic images
within the current work graph. In this paper we propose a
heuristic solution for this subgraph isomorphism problem in
the execution of PROGRES.
Our heuristic is explained with the help of a logical
bootstrap. The relevant elements of the left-hand side of a
production are modelled as graphs. Graph rewriting rules are
used to analyze this graph and to generate an optimal sequence
of basic query actions that efficiently match the left-hand
side to the work graph. It is shown that our heuristic is
able to generate code for an insert operation of a (threaded)
sorted, binary tree that has logarithmic time complexity in
the size of the tree (graph).