Graph Grammar Formalism with Multigranularity for Spatial Graphs
Graph Grammar Formalism with Multigranularity for Spatial Graphs
复制标题
DOI：
10.1007/s10849-023-09406-0
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Yufeng Liu;Fan Yang;Jian Liu
中科院分区：
文献类型：
--
作者：
Yufeng Liu;Fan Yang;Jian Liu
传统的支持空间的语法在指定图的空间语义方面缺乏灵活性。本文描述了一种新的空间图的多粒度坐标图语法（mgCGG）。mgCGG基于坐标图语法（CGG），将坐标分为物理坐标和语法坐标两类，其中物理坐标是现实世界中常见的坐标，语法坐标描述空间语义的限制。在mgCGG的推导和约简中，基于语法坐标对节点间的空间匹配条件进行评估，并通过指定的粒度得到语法坐标。通过调整粒度，可以获得空间语义的定性和定量分析，包括它们之间的过渡状态。在此基础上，设计了一种时间复杂度为多项式的索引搜索算法。最后给出了绘制流程图的运行示例，说明了mgCGG的实际应用。通过与相关的支持空间语法的详细比较，发现mgCGG在语义处理机制、容错、索引搜索算法和实际应用四个关键方面具有良好的性能——提供了一种灵活而统一的方式来指定空间图，并在非空间和空间语法之间架起了桥梁。
Traditional spatial enabled grammars lack flexibility in specifying the spatial semantics of graphs. This paper describes a new graph grammar formalism called the multigranularity Coordinate Graph Grammar (mgCGG) for spatial graphs. Based on the Coordinate Graph Grammar (CGG), the mgCGG divides coordinates into two categories, physical coordinates and grammatical coordinates, where physical coordinates are the common coordinates in the real world, and grammatical coordinates describe the restrictions on the spatial semantics. In the derivation and reduction of the mgCGG, the spatial matching conditions between nodes are evaluated on the basis of the grammatical coordinates, which can be obtained by the specified granularities. By adjusting the granularities, both qualitative and quantitative analyses for spatial semantics can be obtained, including the transition states between them. In addition, a new redex searching algorithm with polynomial time complexity is designed for the mgCGG. A running example of drawing a flowchart is given to illustrate a practical application of the mgCGG. Through a detailed comparison with related spatial-enabled grammars, it is found that the mgCGG has good performance in four critical aspects—the semantics processing mechanism, fault-tolerance, redex searching algorithm, and practical application—providing a flexible yet uniform way to specify spatial graphs and building a bridge between nonspatial and spatial grammars.