GrGen: A Fast SPO-Based Graph Rewriting Tool
GrGen: A Fast SPO-Based Graph Rewriting Tool
复制标题
DOI：
10.1007/11841883_27
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
Rubino Geiß;G. V. Batz;Daniel Grund;Sebastian Hack;A. Szalkowski
中科院分区：
文献类型：
--
作者：
Rubino Geiß;G. V. Batz;Daniel Grund;Sebastian Hack;A. Szalkowski
图重写是一种功能强大的技术，需要进行图模式匹配，这是一个NP完全问题。我们presentGrGen，一个生成式编程系统的图形重写，它适用于启发式优化。根据Varro的基准测试，它至少比我们已知的任何其他工具快一个数量级。我们的图重写工具实现了良好的单推出方法。我们定义的搜索计划的概念来表示不同的匹配策略，并配备这些搜索计划的成本模型，考虑到目前的主机图。选择一个好的搜索计划的任务，然后被视为一个优化问题。为了便于使用，GrGen功能的表达规范语言和生成程序代码与方便的接口。
Graph rewriting is a powerful technique that requires graph pattern matching, which is an NP-complete problem. We presentGrGen, a generative programming system for graph rewriting, which applies heuristic optimizations. According to Varró’s benchmark it is at least one order of magnitude faster than any other tool known to us.Our graph rewriting tool implements the well-founded single-pushout approach. We define the notion of search plans to represent different matching strategies and equip these search plans with a cost model, taking the present host graph into account. The task of selecting a good search plan is then viewed as an optimization problem.For the ease of use,GrGenfeatures an expressive specification language and generates program code with a convenient interface.