论文标题
基于规则的快速图形程序
Fast Rule-Based Graph Programs
论文作者
论文摘要
在基于规则的语言中有效地实现图形算法是具有挑战性的，因为图模式匹配是昂贵的。在本文中，我们介绍了GP 2中图形算法的许多线性时间实现，GP 2是一种基于图形转换规则的实验编程语言，旨在促进程序分析和验证。我们专注于两类基于规则的图形程序：缩减图形程序，这些程序检查某些图形属性，并使用深度优先搜索来测试某些属性或执行操作，例如产生2色或拓扑排序。第一个类型的程序以线性时间运行，而在第二类类型的程序上没有任何约束，而有界度的输入图需要在线性时间内运行。实现线性时间复杂性至关重要的是GP 2中所谓的根本规则，在许多情况下，可以在恒定时间内匹配。对于我们的每个程序，我们都证明了正确性和复杂性，并且还为其运行时间提供了经验证据。
Implementing graph algorithms efficiently in a rule-based language is challenging because graph pattern matching is expensive. In this paper, we present a number of linear-time implementations of graph algorithms in GP 2, an experimental programming language based on graph transformation rules which aims to facilitate program analysis and verification. We focus on two classes of rule-based graph programs: graph reduction programs which check some graph property, and programs using a depth-first search to test some property or perform an operation such as producing a 2-colouring or a topological sorting. Programs of the first type run in linear time without any constraints on input graphs while programs of the second type require input graphs of bounded degree to run in linear time. Essential for achieving the linear time complexity are so-called rooted rules in GP 2, which, in many situations, can be matched in constant time. For each of our programs, we prove both correctness and complexity, and also give empirical evidence for their run time.
