Rule-Based Graph Programs Matching the Time Complexity of Imperative Algorithms
For researchers in graph transformation and programming languages, this work shows that rule-based graph programs can achieve competitive time complexity with imperative algorithms, addressing a key bottleneck in the field.
The paper presents rule-based graph programs in GP 2 that match the time complexity of imperative algorithms for connectivity checking, acyclicity checking, and single-source shortest paths (Bellman-Ford), achieving linear time for the first two on arbitrary graphs and O(nm) for the third, overcoming previous limitations on node degree and connectivity.
We report on recent advances in rule-based graph programming, which allow us to match the time complexity of some fundamental imperative graph algorithms. In general, achieving the time complexity of graph algorithms implemented in conventional languages using a rule-based graph-transformation language is challenging due to the cost of graph matching. Previous work demonstrated that with rooted rules, certain algorithms can be implemented in the graph programming language GP 2 such that their runtime matches the time complexity of imperative implementations. However, this required input graphs to have a bounded node degree and (for some algorithms) to be connected. In this paper, we overcome these limitations by enhancing the graph data structure generated by the GP 2 compiler and exploiting the new structure in programs. We present three case studies: the first program checks whether input graphs are connected, the second program checks whether input graphs are acyclic, and the third program solves the single-source shortest-paths problem for graphs with integer edge-weights. The first two programs run in linear time on (possibly disconnected) input graphs with arbitrary node degrees. The third program runs in time $O(nm)$ on arbitrary input graphs, matching the time complexity of imperative implementations of the Bellman-Ford algorithm. For each program, we formally prove its correctness and time complexity, and provide runtime experiments on various graph classes.