Page 7 - 《软件学报》2021年第12期

刘禹锋 等:vCGG:一种基于虚结点的空间图文法形式框架 3671

坐标的基础上定义离散坐标的概念,使用两个子框架 cCGG(continuous coordinate graph grammar)和 dCGG
(discrete coordinate graph grammar),为分别空间语义提供定量与定性描述粒度.以下给出 CGG 中的基本概念.
定义 1.1. G=(N,E)是一个定义在标号集 L 上的空间语义图,当且仅当:
• N 是一个结点集,并且可以进一步被分为两个子集合:终结点集 N T 和非终结点集 N NT ;
• E⊆N×N 是一个有向边集.
为了方便语法语义操作,CGG 定义了以下几个函数.
• f NL :N→L 是一个从结点 n∈N 到标号 l∈L 的映射,即 f NL (n)=n.l;
• f NC :N→R×R 是一个从结点 n∈N 到坐标 c∈R×R 的映射;
• f EN s : E → N 是一个从有向边 e∈E 到它的起始结点的映射;
• f EN e : E → N 是一个从有向边 e∈E 到它的结束结点的映射.
定义 1.2. 给定一个空间语义图 G,结点 n∈G.N 的离散坐标是(r x ,r y ),当且仅当:
• r x 和 r y 分别是 f NC (n).x 和 f NC (n).y 在 G.N 中所有结点坐标值中的反向排名数值.
对于一个给定的图,结点的离散坐标抽象自连续坐标,表示结点的横坐标与纵坐标在当前图所有结点中的
反向排名,反映了该结点在图中的相对空间位置.例如,图 1 是一个空间图连续坐标的离散化过程,结点 a 横坐标
与纵坐标在图中所有的结点中反向排名为 2,3,因此,结点 a 在当前图中的离散坐标为(2,3).

Fig.1 Mapping between continuous coordinates and discrete coordinates
图 1 连续坐标与离散坐标之间的映射
定义 1.3. 图 G 与图 Q 是同构关系,记作 G≈Q,其中,G 和 Q 之间存在两个双射:f NN :G.N↔Q.N 和 f EE :G.E↔Q.E,
并满足以下条件.
• ∀ n (((n G∈ . ) (N ∨ n Q∈ . ))N ⇒ ( f NL ( )n = f ′ NL ( f NN ( ))))n ,其中,f NL 和 f ′ 分别是 G 和 Q 的结点标号映射;
NL
• ∀ e (((e G∈ . ) (E ∨ e Q∈ . ))E ⇒ ( f ( f ( ))e = f ( f ( ))) (e ∧ f ( f ( ))e = f ( f ( ))))e .
NN EN s EN s EE NN EN e EN e EE
满足同构关系的两个图有着一一对应的结点和边,其中,对应结点拥有相同的标号,并且对应边的起始结点
和结束结点也需符合该对应关系.
定义 1.4. 图 Q 是一个包含悬边的图 G 的核图,记作 Q = Cor ()G ,当且仅当:
(.QN = G . ) ( .N ∧ Q E = ( .GE GE− . )) ( .Q L∧ = GL
. ) .
定义 1.5. 如果图 Q 是一个给定主图 G 的子图并可能带有悬边,并且图 G | L R 是一个产生式的左图或右图,
图 Q 是图 G | L R 在主图 G 中的图柄,记作 Q∈ Redex (,G G | L R ) ,当且仅当:存在两个双射: f NN :.QN ↔ G | L R .N 和 f EE :
. QE ↔ G | LR .E ,并满足以下条件.
• Cor ()Q ≈ Cor (G | L R ) ;
• ∀ ( nn Q∈ .N ⇒ ( ( )d n = s d s ( f NN ( ))) ( ( )n ∧ d n = e d e ( f NN ( ))))n ;
∀
• cCGG: n n 2 ( ,n n ∈ 1 2 . Q N ⇒ ( f NC ( )n − 1 f NC ( )n = 2 f ′ NC ( f NN ( ))n 1 − f ′ NC ( f NN ( ))))n 2 ,其中,f NC 和 f ′ 分别是 Q
,
1
NC
和 G | L R 的结点坐标映射;
• dCGG:∀n(n∈Q.N⇒(n.c d =(f NN (n).c d ))),其中,c d 是 Q 或 G | L R 中结点的离散坐标.
在 CGG 中,图柄不仅要求与某个产生式图形成同构关系,还需满足空间上的语义匹配要求.根据不同的粒
度描述选择,子框架 cCGG 要求产生式图 G | L R 中任意两个结点和它们在图柄 Q 中对应的结点具有完全相等的