Description

The graph programming language GP [1] allows to solve graph problems at a high level of abstraction, based on nondeterministic applications of graph transformation rules. The nondeterminism, however, makes graph matching a costly operation which may cause poor execution times for graph programs.

To make graph programs fast, the PhD thesis [2], the paper [3] and the monograph [4] propose a technique which removes much of the nondeterminism in graph matching: viz. to contol the matching process by a unique root node in each rule and in the host graph. This allows constant-time graph matching on graphs of bounded node degree. The purpose of this project is to carry out a case study which tries out this technique on some selected graph algorithms. The running time of the resulting programs shall be determined theoretically - assuming a suitable implementation of GP - and compared practically with that of conventional GP programs using the current GP implementation [5].

References

1. D. Plump: The Graph Programming Language GP. In Proc. Algebraic Informatics (CAI 2009), volume 5725 of Lecture Notes in Computer Science, pages 99-122. © Springer-Verlag, 2009
2. M. Dodds: Graph Transformation and Pointer Structures. PhD thesis, The University of York, 2008.
3. M. Dodds and D. Plump: Graph Transformation in Constant Time. Proc. International Conference on Graph Transformation (ICGT 2006), Lecture Notes in Computer Science 4178, pages 367-382. © Springer-Verlag, 2006

Additional Resources

1. The paper