Linear-Time Graph Programs without Preconditions

Ziad Ismaili Alaoui, Detlef Plump · 2025

Read Linear-Time Graph Programs without Preconditions by Ziad Ismaili Alaoui, Detlef Plump (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20465.txt.

Introduction

Ziad Ismaili Alaoui and Detlef Plump show that rule based graph programs can run in linear time without demanding tidy input graphs, in a paper from 2025. Graph rewriting is elegant, but matching rules to a graph usually costs too much for fast algorithms. Earlier fast versions needed inputs that were connected with few links per node.

The team improved the data structure produced by their compiler and used the new layout in programs. Three programs were tested: finding cycles, numbering connected parts, and breadth first search. Each ran in linear time on tangled or split graphs with any link counts. Timing tests on many graph families backed the claim.

Catalog record

CREATORZiad Ismaili Alaoui, Detlef Plump
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20465

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Linear-Time Graph Programs without Preconditions Ziad Ismaili Alaoui, Detlef Plump Abstract We report on a recent breakthrough in rule-based graph programming, which allows us to reach the time complexity of imperative linear-time algorithms. In general, achieving the complexity of graph algorithms in conventional languages using graph transformation rules is challenging due to the 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 retain the structure of input graphs, achieving linear runtime required input graphs to be connected and of bounded node degree. In this paper, we overcome these preconditions by enhancing the graph data structure generated by the GP 2 compiler and exploiting the new structure in programs. We present three case studies, a cycle detection program, a program for numbering the connected components of a graph, and a breadth-first search program. Each of these programs runs in linear time on both connected and disconnected input graphs with arbitrary node degrees. We give empirical evidence for the linear time complexity by using timings for various classes of input graphs. 1 Introduction Designing and implementing languages for rule-based graph rewriting, such as GReAT [ 2 ] , GROOVE [ 11 ] , GrGen.Net [ 12 ] , Henshin [ 16 ] , and PORGY [ 10 ] , poses significant performance challenges. Typically, programs written in these languages do not achieve the same runtime efficiency as those written in conventional imperative languages such as C or Java. The primary obstacle is the cost of graph matching, where matching the left-hand graph L of a rule within a host graph G generally requires time |G|^{|L|} , with |X| denoting the size of graph X . (Since L is fixed, this is a polynomial.) As a consequence, standard imperative graph algorithms running in linear time (see, for example, [ 8 , 15 ] ) may exhibit non-linear, polynomial runtimes when recast as rule-based graph programs. To address this issue, the graph programming language GP 2 [ 14 ] supports rooted graph transformation rules, initially proposed by Dörr [ 9 ] . This approach involves designating certain nodes as roots and matching them with roots in the host graphs. Consequently, only the neighbourhoods of host graph roots need to be searched for matches, which can often be done in constant time under mild conditions. The GP 2 compiler [ 4 ] maintains a list of pointers to roots in the host graph, facilitating constant-time access to roots if their number remains bounded throughout the program’s execution. In [ 5 ] , fast rules were identified as a class of rooted rules that can be applied in constant time, provided host graphs contain a bounded number of roots and have a bounded node degree. The first linear-time graph problem implemented by a GP 2 program was 2-colouring. In [ 5 , 4 ] , it is shown that this program colours connected graphs of bounded node degree in linear time. Since then, the GP 2 compiler has received some major improvements, particularly related to the runtime graph data structure used by the compiled programs [ 7 ] . These improvements made a linear-time worst-case performance possible for a wider class of programs, in some cases even on input graph classes of unbounded degree. See [ 6 ] for an overview. Despite this progress, programs that retain the structure of input graphs, such as the aforementioned 2-colouring program, have until now required non-linear runtimes on disconnected graphs. The problem is that, after a connected component is visited, the number of failed attempts to match a non-visited node in a different connected component may increase. Consequently, in disconnected graph classes, this number may grow quadratically in the graph size, leading to a quadratic program runtime. In connected graph classes, this undesirable behaviour is ruled out because all nodes are reachable from a single undirected depth-first search. In this paper, we present two updates to the GP 2 compiler, one being introduced in [ 3 ] , which allow lifting the preconditions that host graphs must be connected and have a bounded node degree. In short, the solution is to improve the graph data structure generated by the compiler. Nodes are now stored in separate linked lists based on their marks (red, green, blue, grey or unmarked), and each node comes with a two-dimensional array of linked lists storing all incident edges based on their marks (red, green, blue, dashed or unmarked) and orientation (incoming, outgoing or looping). This enables the matching algorithm to find in constant time a node with a specific mark or an edge with a specific mark and orientation. For instance, if a red node is needed, a single access to the list of red nodes will either locate such a node or confirm its absence. Similarly, if an outgoing green edge is required, a single access to the corresponding linked list will either find such an edge or determine that none exists. In addition to the new graph data structure, a programming technique is needed to take advantage of the improved storage. In a case study, we demonstrate how to recognize acyclic graphs in linear time with the new graph representation. Our program admits both connected and disconnected input graphs with arbitrary node degrees. It either detects that a graph is cyclic or returns an acyclic graph that is isomorphic to the input graph up to marking. Then, we discuss two more programs relying on the improved compiler: one numbering the connected components of a graph, and another performing a breadth-first search. For both programs, we give empirical evidence that they run in linear time on different classes of input graphs. 2 The Problem with Graph Classes of Unbounded Degree The current section and the next explain the problem caused by classes of input graphs with an unbounded node degree, and how the updated compiler overcomes this problem. We include this material from [ 3 ] for the benefit of the reader. For a description of the GP 2 programming language, we refer to [ 6 ] . Previously, non-destructive GP 2 programs based on depth-first-search ran in linear time on graph classes of bounded node degree but in non-linear time on graph classes of unbounded degree [ 6 ] . For example, consider the program is-connected in Figure 1 which checks whether a graph is connected. 1 1 1 Node labels such as x are written inside nodes, whereas small integers below nodes are their identifiers. Nodes without identifiers on the left-hand side are to be deleted; nodes without identifiers on the right-hand side are to be added. Nodes with the same identifier on each side are to be kept. Input graphs are arbitrary GP 2 host graphs with grey nodes and unmarked edges. The program fails on a graph if and only if the graph is disconnected. Rule init picks an arbitrary grey node as a root (if the input graph is non-empty) and then the loop DFS! performs a depth-first search of the connected component of the node chosen by init . The rule forward marks each newly

Read the complete text