- 1 -
中国科技论文在线
基于矩阵运算的图转换检测算法#
陈亮，陈军冰*
基金项目：Supported by the Hohai Univ. Natural Science Foundation under Grant NO. 2008432311;
National Science and Technology Infrastructure Program under Grant
作者简介：陈亮（1984-），男，硕士研究生，主要研究算法，软件重构等
（河海大学计算机与信息学院，江苏 南京 211100）
摘要：图转换系统（GTS）是一个基于在给定图产生式规则下的图转换，这里每作用一个规
则都是一个图转换的步骤。这样不同的规则之间会产生冲突，按照已有的方法，在人工的干
预下进行每一步的修正然后再复合。本文运用矩阵运算的方法，定义冲突矩阵，关联矩阵以
及规则链等概念，根据规则的复合和矩阵运算之间的联系，提出了一种自动实现的规则复合
的 GTS检测算法。
关键词： 图转换；矩阵运算；规则链；冲突矩阵；关联矩阵
中图分类号：TP311
Graph Transformation Detecting Algorithm Based on
Matrix Operations
Chen Liang, Chen Junbing
(Computer and Information College,Hohai University,Jiangsu Nanjing 211100)
Abstract: The graph transformation system is the rules based on the graphs production, where each
application of a graph rule leads to a graph transformation step. There is conflict between the different
rules. according to the existing methods,we must intervene every step and amend the conflict .In this
paper, we use the matrix operations and define the notions of conflict matrix, correlation matrix, the
chains of rules. According to the relations between the compound of rules and matrix operations, a
automatic graph transformation systems detecting algorithm is put forward.
Keywords: GraphTransformation;Matrix Operations; the Chains of Rules; Conflict Matrix; Correlation
Matrix
0 引言
图转换这一研究领域是计算机科学的一个分支，由于图是一种可以把复杂的问题直观地
表示出来的自然的方式，因而，它得到了广泛的应用。图已应用于计算机科学的几乎所有方
面。图转换系统是一个基于图产生式规则的图转换，这里每一个规则都是一个图转换的步骤。
从操作的角度[1]，从 G 到 H 的图转换记做 HG ⇒ ，这一转换通常包括以下主要步骤，如
下图 1 所示
图 1 图转换过程
1. 选择过程 p： L R⇒ ，L 作为左部，R 为右部，在 G 中 L 的象。
- 2 -
中国科技论文在线
2. 检查图产生式的应用条件。
3. 把 G 中属于 L 但不属于 R 的部分去除。如果 L 删除导致了边的悬空（dangling），
那么这一操作就被取消，或者悬空边也被同时删除。这一操作完成后所得图称为 D。
4. 把右部 R 与图 D 关联比较，属于 R 但不属于 L 的部分添加到 D，即得到图 E。
5. 如果图产生式 p 包括附加嵌入关系（additional embedding relation），那么就根据这
一关系进一步把右部 R 的部分嵌入关系到 E，即得到图 H。
这样就会产生不同间规则之间的冲突，人们提出了很多的检测和消解的方法，例如 Leen
Lambers ,Hartmut Ehrig 等提出的 Negative Application Condition (NAC) [2]和 Essential Critical
Pairs[3]冲突检测方法.也有一些方法是基于图转换系统的两种不确定性提出的，通过定义规则
的流程控制来把它们按一定顺序应用，或者通过使用外部控制结构（explicit control
construct）、优先级、层（layer）或者通过输入参数来规约部分匹配来限制匹配的选择。但
是这些方法有一个共同的特点，都是基于对每一步的人工干预，进行一定的冲突检测和消解
来实现。
1 冲突的分类
基于图转换[4]的模型重构[5，6]过程中，涉及到模型重构规则的并行应用问题[7]。正如进
程的并性运行导致对系统资源的占有与等待而引发进程死锁现象一样，由于模型重构过程中
重构规则的并行应用导致了重构规则之间产生冲突现象[8]（见图 1）。这些冲突将导致模型
坏味道（bad smell）。由于重构规则冲突及潜在冲突的存在，将影响模型重构的质量。因此，
研究重构冲突检测及消解是模型重构中的一个关键问题。
图2 重构规则Pull up Method与Move method之间产生冲突
模型重构规则之间的冲突关系可以通过图转换中的关键对[9]进行分析。一个关键对是一
对转换（P1,P2）,其中 p1(m1):G→H1 与 p2(m2):G→H2 冲突，这里 G 是最小图。也即，G
是左手边规则 p1 和 p2 的联结。它（关键对）能在所有可能方面通过重叠 L1 和 L2 被计算，
例如 L1 和 L2 交集中包含至少一条是被其中规则之一或在它们各自发生的事件上都可应用
于 G 的两个规则删除或改变。
关键对集合代表所有潜在冲突。即一个关键对（p1，p2）存在，当且仅当 p1 应用导致
- 3 -
中国科技论文在线
p2 不可应用，或者反之。如果两个规则应用至少满足上述情形之一，则两个规则应用是冲
突的。
共有三种规则应用产生冲突：（1）一个规则应用删除了一个图对象，该对象是另一个
规则应用的匹配。（2）一个规则应用产生了一个图对象，该对象增加的图结构被另一个规
则应用的否定应用条件（NAC）所禁止。（3）一个规则应用改变了另一个规则应用与之所
匹配的属性。[8]
给定两个图转换 t1 和 t2，如果 t1 先执行后，t2 不能执行，称为非对称冲突；如果 t1，
t2 不管是谁先执行都导致另一个转换不能执行，称为对称冲突。[10]
根据三种规则将冲突定义，将模型重构冲突类型分为三类：规则自身并行应用两次所产
生冲突，对称冲突，非对称冲突。每种冲突分别包含若干冲突情况，见表 1：
表 1：冲突类型
类 型 冲 突
Move Variable/ Move Method
Pull Up Variable/ Pull Up Method
Encapsulate Variable
Create Superclass
第一类：规则自身并行应用两
次所产生冲突
Rename Class/ Rename Variable/Rename Method
Move Variable 对 Pull Up Variable 冲突/Move Method 对
Pull Up Method
Move Variable 对 Encapsulate Variable/Pull Up Variable
对 Encapsulate Variable
Move Method 对 Encapsulate Variable/Pull Up Method 对
Encapsulate Variable
Create Superclass 与 Rename Class
第二类：对称冲突
Rename Variable 分别与 Move Variable 或 Pull Up
Variable/Rename Method 分别与 Move Method 或 Pull
Up Method
Create Superclass 对 Pull Up Variable
/Create Superclass 对 Pull Up Method
Rename Variable 对 Encapsulate Variable 第三类：非对称冲突
Encapsulate Variable 对 Rename Method
2 相关定义
定义 并行独立
两个图转换
1, 1
1
p m
H G⇐ 和 2, 2 2p mG H⇒ 是并行独立的，当
1 1 2 2 1 1 1 2 2 2( ) ( ) ( ( )) ( ( ))m L m L m l K m l K∩ ⊆ ∩
这个条件也可以表示成下列条件：
1 1 2 2 1 1 2 2 1 1 2 2: : : :h L D d h m h L D d h m∃ → = ∧∃ → =D D
- 4 -
中国科技论文在线
图 2：并行独立
定义 冲突
两个图转换
1, 1
1
p m
H G⇐ 和 2, 2 2p mG H⇒ 如果不是并行独立的，那么它们就是冲突的。备注：
如果满足条件 1 1 2 2 2 2 2( ) ( ) ( ( ))m L m L m l K∩ ⊄ 或 1 1 2 2 1 1 1( ) ( ) ( ( ))m L m L m l K∩ ⊄ 条件，那么
这种冲突就叫做删除使用冲突(delete-use-conflict)。
定义 图以及图映射
一个图 G=( , , ,E VG G s t )包含了一个边集 EG ，一个点集 VG 和两个映射 s， t :
E VG G→ ，对应到每一条边 Ee G∈ ，从源点 q=s(e) VG∈ 映射到目标点 z=t(e) VG∈ 。两个图
iG =( , ,, , ,i E i V i iG G s t ) ， (i=1 ， 2) 之 间 的 映 射 f: 1 2G G→ 是 一 个 映 射 对
,1 ,2 ,1 ,2( : , : )E E E V V Vf f G G f G G= → → ，并且满足 1 2V Ef s s f=D D 和 1 2V Ef t t f=D D 。如
果 Ef 和 Vf 是单射(injective)，那么图映射 f 也是单射。一个一一映射既是单射也是满射。
图中的一个包含关系 i : H G→ 是一个图映射，它指两个方面，即 : , :V Ei v v i e e6 6 。
如果存在这样一个包含关系，就说 H 是 G 的一个子图。若 1, 1, 2, 2,( ) ( )V V V V Vm L m L G∪ = 以
及 1, 1, 2, 2,( ) ( )E E E E Em L m L G∪ = ，就说 1 2,m m 是联合满射。一对联合满射( 1 2,m m ) 也称为图
L1。L2 的交叠。图转换 p 是从 G1*G2 的子图 G 到 G1(G2)的过程，包含 1, 2,: ( )V V V Vp G G G→
以及 1, 2,: ( )E E E Ep G G G→
定义 规则
一个图转换过程的规则 p: l rL K R←⎯⎯ ⎯⎯→ 包含规则名 p，以及一对图单射 l:
K L⎯⎯→ ， r: K R⎯⎯→ 。图 L，K，R 分别称作规则 p 的左部(lhs)，接口(interface)，右
部(rhs)， 若 l: K L⎯⎯→ 是一一映射，则规则 p 是非删除的(non-deleting)。当 l 是图包含关
系时，若 L=K 则规则 p 非删除。
定义 图转换
图像转换系统中的图转换是一个图 G，或一个图有向转换序列 1 ipi iG G− ⎯⎯→ ，pi 是系
统中的规则。
3 冲突检测
下面我们就运用现有的关键对分析（Critical Pair Analysis）算法检测结构重构的冲突。
该算法给定一个图转换规则集，首先计算一张表，该表显示每一个规则对之间的关键对数量。
需要计算所有规则之间的关键对，对每一个关键对分别判断三种类型冲突条件。该算法实际
是对关键对规则进行遍历，其计算效率不高。刘辉[12]借助图转换的冲突检测机制及关键对
- 5 -
中国科技论文在线
技术，利用检测转换规则与转换约束之间的关系，给出了重构冲突检测算法。该算法针对 4
条特性保持约束的转换规则[12]进行检测，实际上也是一个遍历算法。Leen Lambers 等 [13]
中给出对于两个非删除规则或一个删除一个非删除规则集关键对的一个有效的计算冲突关
键对方法。因为以下两个原因使这一方法可以更有效率，（1）如果两个规则是无删除的，
那么没有必要计算任何一个使 L1 和 L2 的重叠（m1，m2）。（2）如果其中一个规则是非
删除的，另一个规则是删除的，那么没有必要计算所有使 L1 和 L2 的重叠（m1，m2），直
接计算那些引出关键对的重叠就足够了。这个算法可免除对于非删除规则对交叠的计算。上
述算法都可实现模型重构规则的自动冲突检测。通过这种关键对（Critical Pair Analysis）的
算法，应用上面介绍的冲突条件，记每个规则为 ip ，如果 ip 与 jp 有冲突，则表格中第 i 行
第 j 列记作 1，如果 ip 与 jp 没有冲突则相应的记做 0，例如有 8 个规则的冲突检测结果如
下图 3 所示：
图 3 冲突结果图
根据上面的图 3 可以得到一个冲突检测的表格：
表 2：冲突表
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
将上面的表格看作8 8× 矩阵，称作冲突矩阵，记为矩阵 A
- 6 -
中国科技论文在线
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
A
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
4 问题描述
我们得到了冲突矩阵 A，它反映了在图转换中各个规则间的关系.现在我们来定义规则
间的关联矩阵B ，规则 ip 与 jp 有冲突，我就称规则 ip 与 jp 不相关联，此时 0ijb = ，反之，
我们称 ip 与 jp 相关联，此时 1ijb = ，这样就得到如下关联矩阵B
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1
B
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
在实际的规则作用中一系列的规则作用是按照给定的顺序进行的，我们将各个规则看作
各个规则的节点，这样就形成一个有向的规则链。记作 1i i jp p p+→ → →" ,通过矩阵的
运算可以知道规则节点 ip 到其它各个规则节点的长度为 l 的规则链是否存在，其中
0,1, 2,l n= "" 。假设给定了一序列的规则 ( 1,2, )kp k l= ""其中 ，其中规则链的最大长
度为 1l − （如果中间存在规则的重复作用，规则链的长度就有可能大于 1l − ，但是实际问
题中规则链的总长度是可以确定的，由于规则的作用顺序可以确定。为了讨论方便，下面都
讨论中间没有规则重复作用，有规则重复作用的也类似。）通过矩阵运算 ( )sB 其中 1s l≤ − ，
得到 ip 到 jp 长度为 s 的规则链存在，接着运算 ( 1)sB + ，而 ip 到 1jp + 长度为 1s + 的规则链不
存在，由此我们可以判断规则 ( 1,2, )kp k l= ""其中 按照给定的作用顺序是有冲突。不能
完成规则的一系列复合，也即是不能完成重构过程。
5 算法及证明
根据上面的分析及冲突矩阵可以得到如下表示的算法：
Step 1：输入：给定要复合的规则系列 1i i i k i lp p p p+ + +→ → →" ，规则链的长度记为
l
- 7 -
中国科技论文在线
Step 2: 根据冲突分类得到规则的冲突矩阵 A ,进而得到关联矩阵B
Step 3: For 0k = to l ;布尔矩阵运算： ( ) ( 1)k kB B B−= ∗ ；
Step 4 ：If ikb k≠ // 首先判断,如果前 1k + 个规则没有长度为 k 的规则链，则
2k + 个规则也不能复合。
Step 5：Return False；// 返回规则不能按照给定的顺序复合。
Step 6：End If // 结束给定规则的复合。
Step 7：If ikb k= ； // 前 1k + 个规则有长度为 k 的规则链。
Step 8 ：Continue
Step 9: If 1 1ikb k+ ≠ + ;转 Step 6 // 2k + 个规则没有长度为 1k + 的规则链，规则不能
按照给定的规则系列进行复合。
Step 10：转 Step 5 // 结束给定规则的复合。
算法中使用了如果规则链 1 1i i k j jp p p p p+ +→ → → →" " 之中 ip 到 jp 长度为 1l −
的规则链不存在，那么很显然重构就终止了，按照给定的复合顺序是不能接着进行重构的；
（1）如果这样的规则链存在，也即是 1 1i i k j jp p p p p+ +→ → → →" " 中 ip 到 jp 有长度
为 1l − 的规则链，接着进行下面的重构步骤，假如 1 1i i k j jp p p p p+ +→ → → →" " 之
中 ip 到 1jp + 长度为 l 的规则链不存在，但是 jp 与 1jp + 可以重构，由（1）可以知道 jp 与 jp
长度为 1l − 的规则链是存在，而 jp 与 1jp + 可以看成是长度为1的规则链，这样 ip 到 1jp + 长
度为 l 的规则链就构造出，这和布尔矩阵运算得到的结果是相互矛盾的。也就是 jp 与 1jp + 是
不能重构的。给定的重构规则是不能复合。
6 例子
给定三个作用的规则 1 2 3, ,p p p ，它们的冲突矩阵为M ：
0 1 0
1 0 1
0 1 0
M
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦
可以得到关联矩阵 N 为：
1 0 1
0 1 0
1 0 1
N
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦
给定的规则作用链为 1 3 2p p p→ → ，由矩阵运算得到：
- 8 -
中国科技论文在线
(1)
1 0 1
0 1 0
1 0 1
N
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦ ,
(2)
2 0 2
0 1 0
2 0 2
N
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦
由第一个矩阵的第一行第三列对应的元素为 1，可以知道 1 3p p→ 长度为 1l = 的规则链
是存在的，但是由于第二个矩阵的第一行第二列的应对元素为 0，可以知道 1 2p p→ 长度为
2l = 的规则链是不存在的，由此我们可以得出规则 1 2 3, ,p p p 按照给定的规则作用顺序
1 3 2p p p→ → 是不能进行规则复合的，不能进行图的重构。
7 结论及进一步工作
重构规则的复合以及冲突的检测，一直是重构模型研究的热点问题。人们也提出了很多
冲突检测的算法，例如 Negative Application Condition (NAC)，关键对算法等等。本文运用
矩阵的运算这个有力的工具，将规则的冲突用矩阵运算来表示。实际问题中在给定的规则系
列下进行模型的重构。将这个过程看作是规则链的作用，规则的复合。通过矩阵的运算可以
得出规则链之间的长度，从而判断出给定的重构过程的可执行性。
冲突检测只是模型重构的开始步骤，通过本文算法得到的冲突和不能执行的规则链，可
以在修改一定的条件下，让重构的过程能够进行，同时又可以保持模型的某些特性。模型特
性的保持也和冲突规则的作用有关，当我们知道了可以执行的规则链后，并且完成了模型的
重构过程，新的模型和以前的模型的特性方面的关系以及由新模型和给定了执行规则链的条
件下怎样得到初始模型，也即是模型的广义逆问题都急需进行研究。
[参考文献] (References)
[1] Hartmut Ehrig, Ulrike Prange ,Karsten Ehrig ,Fundamentals of Algebraic Graph Transformation, EATCS
Monographs in TCS, Springer 2006,
[2] Lambers L, Ehrig H, Orejas F. Conflict detection for graph transformation with negative application
conditions. In: Corradini A, Ehrig H, Montanari U, Ribeiro L, Rozenberg G, eds. Proc. of the Graph
Transformations, the 3rd Int’l Conf. (ICGT 2006). LNCS 4178, 2006. 61−76.
[3] Leen Lambers , Hartmut Ehrig, Efficient Detection of Conflicts in Graph-based Model Transformation .
[4] Andrea Corradini, Ugo Montanari, Francesca Rossi, Hartmut Ehrig, Reiko Heckel, and Michael L¨owe.
Algebraic approaches to graph transformation I: Basic concepts and double pushout approach. In G. Rozenberg,
editor, Handbook of Graph Grammars and Computing by Graph transformation, Volume 1: Foundations. World
Scientific, 1997.
[5] Mens, T. (2006). On the use of graph transformations for model refactoring. In: Generative and
Transformational Techniques in Software Engineering (pp. 219-257), LNCS 4143, Springer.
[6] Mens, T., Van Eetvelde, N., Demeyer, S., & Janssens, D. (2005). Formalizing refactorings with graph
transformations. Journal on Software Maintenance and Evolution 17(4), 247-276, Wiley.
[7] Annegret Habel, Berthold Hoffmann: Parallel Independence in Hierarchical Graph Transformation. ICGT
2004: 178-193.
[8] Taentzer TG, Runge O. Detecting structural refactoring conflicts using critical pair analysis. Electronic Notes
in Theoretical Computer Science, 2005,127(3):.
[9] Detlef pairs in term graph rewriting. In. Proc. Mathematical. Foundations of Computer
Science 1994. , volume 841 of. Lecture Notes in Computer. Springer-Verlag .London, UK.
[10] T. Mens, A formal foundation for object-oriented software evolution, PhD Thesis, Department of Computer
Science, Vrije Universiteit Brussel, September 1999.
