Speeding up Graph Programs

This thesis presents an improvement in rule-based graph programming which enables the design of graph programs that achieve the time complexity of imperative linear-time algorithms. Achieving such complexity in conventional languages using graph transformation rules is challenging due to the high cost of graph matching. Previous work demonstrated that with rooted rules, certain algorithms can be executed in linear time using the graph programming language GP 2. However, for non-destructive algorithms that preserve the structure of input graphs, achieving linear runtime required input graphs to be both connected and of bounded node degree. In this thesis, we overcome these limitations by enhancing the graph data structure generated by the GP 2 compiler and exploiting this new structure within the programs. We present four case studies: a program that checks graph’s connectedness, a program that two-colours a graph, a cycle detection program, and a program that computes the shortest weighted distances from a single source to all other nodes in a weighted graph. The first three programs run in linear time on both connected and disconnected input graphs with arbitrary node degrees. The fourth program achieves a time complexity comparable to that of conventional implementations in imperative programming languages. For each program, we provide a formal analysis of its correctness and complexity, supplemented by empirical benchmarking.