ECEASST Rooted Graph Programs

Abstract: We present an approach for programming with graph transformation rules in which programs can be as efficient as programs in imperative languages. The ba-sic idea is to equip rules and host graphs with distinguished nodes, so-called roots, and to match roots in rules with roots in host graphs. This enables graph transforma-tion rules to be matched in constant time, provided that host graphs have a bounded node degree (which in practice is often the case). Hence, for example, programs with a linear bound on the number of rule applications run in truly linear time. We demonstrate the feasibility of this approach with a case study in graph colouring