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).