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

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

点,也可称为产生式内部结点.为了图转换操作的可执行性,vCGG 规定:同一个产生式两端的虚结点集之间需存
在一个双射,并且对应的结点拥有相等的标号与坐标.此外,为了图嵌入过程中不产生歧义,同一个图中的每一
个虚结点具有唯一的标号,可以用唯一的整数表示.例如,图 5 是一个合法的 vCGG 产生式,其中,虚线圆框代表虚
结点,实线圆框代表实结点.

Fig.5 vCGG production
图 5 vCGG 产生式
由图 5 可见:产生式左图与右图之间存在一个双射,并且对应结点具有相同的标号“1”、标号“2”以及相等的
坐标(1,3),(1,1).
定义 2.3. 图 G 与图 Q 是同构关系,记作 G≈Q,其中,G 和 Q 之间存在两个双射:f NN :G.N↔Q.N 和 f EE :G.E↔Q.E,
并满足以下条件.
. ) ∨
′ f
• ∀ (( ∈n n G N ( ∈ n . ) ⇒ Q N ( f NL ( )∈ n v ) ∨ L ( ′ f NL ( f NN ( ))∈ n v ) ∨ L ( f NL ( ) = n NL ( f NN ( ))))n ,其中,f NL 和 f ′ 分
NL
别是 G 和 Q 的结点标号映射;
• ∀ 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
在判定一对图是否满足同构条件时,虚结点比实结点具有更高的抽象程度,可以匹配任意标号的结点.图 6
是一个 vCGG 中图同构的例子,其中,所有结点和边在满足双射关系的.其中,实结点“stat”和对应结点必须具有
相同的标号,而虚结点“1”、虚结点“2”可以匹配任何标号的结点(图 6 中为“begin”“end”).

Fig.6 Theisomorphic graphs in vCGG
图 6 vCGG 中具有同构关系的图
定义 2.4. 如果图 Q 是一个给定主图 G 的子图,图 G L|R 是一个产生式的左图或右图,图 Q 是图 G L|R 在主图 G
中的图柄,记作 Q∈Redex(G,G L|R ),当且仅当:存在两个双射:f NN :Q.N↔G L|R .N 和 f EE :Q.E↔G L|R .E,并满足以下条件.
(1) vcCGG
• Q≈G L|R ;
(( ∈
• ∀ nn . Q N ∧ (( f ′ NL ( f NN ( ))n ∈ L r )) ⇒ ( ( )d n = s d s ( f NN ( )))n ∧ ( ( )d n = e d e ( f NN ( ))))n ,其中,d e (n)和 d s (n)是结
点 n 在主图中的出入度;
• ∀ n 1 ,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 和
NC
G L|R 的结点坐标映射.
(2) vdCGG
• Q≈G L|R ;