Fast Graph Programs

G. Campbell, J. Romo, D. Plump

Project Report, Department of Computer Science, University of York, 49 pages, 2018. | PDF | BIB

This report summarizes the technical results of an undergraduate project carried out over 10 weeks by Graham Campbell and Jack Romo. The project was supervised by Dr. Detlef Plump and funded by a Vacation Bursary of the Engineering and Physical Sciences Research Council (EPSRC).

The project’s aim was to demonstrate with case studies that rule-based graph programs in the language GP 2 can be made fast by using so-called root nodes. The basic idea is that by equipping both rules and host graphs with roots that correspond to each other, the non-determinism in rule matching can be greatly reduced.

As a “warm-up”, the first case study shows that rooted graph programs can simulate finite automata and deterministic pushdown automata in a natural way. The transition diagrams of such automata are directed graphs anyway and program execution proceeds by moving the root, which represents the current state, along the transitions in the diagram.

In the second case study, topological sorting on acyclic graphs is implemented by a rooted GP 2 program that encodes a depth-first traversal strategy. Benchmarking on input graphs of up to 200,000 nodes shows that this program runs in linear time on acyclic graphs of bounded node degree (under some mild assumptions such as connectedness and a unique node of indegree 0). This is a novel result in the field of rule-based graph transformation.

The third case study represents red-black trees as GP 2 graphs and presents a rooted graph program that generates a red-black tree for n integers in time O(n log n). Again, this result is novel and has been empirically confirmed on input graphs of up to 100,000 nodes.

Finally, this report describes some initial attempts to refine unrooted graph programs to faster rooted programs. For this, the problem of reversing all edges in an input graph is considered. Rooted graph programs are presented that accomplish edge reversal on lists, trees and forests in linear time. In contrast, the corresponding unrooted programs have a quadratic running time.

Nifty tech tag lists from Wouter Beeftink