层次图变换的比较

电子笔记在理论计算机科学50第3期（2001年）。GT-VMT 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html8页层次图变换概念的比较Giorgio Busatto和Berthold Ho mann1Fachbereich Mathematik/Informatik，UniversitatBremen Postfach 33 04 40，28334 Bremen乔治|hof g @informatik.uni-bremen. de1介绍统一建模语言是可视化语言在建模软件中的重要性不断增加的一个突出证据。众所周知，可视化语言的语法可以用图来表示，其语义可以通过图变换来指定[2]。由于软件模型可能很大，它们的图表示应该提供一个将图划分为嵌套包的概念。为此目的，已经提出了几个概念的分层图，他们在不同的方面，如包是否可以共享或不，以及边缘是否可以跨越包边界或不。变换只考虑了其中的一些，一个普遍接受的概念，层次图和它们的变换仍然是失踪。 为了填补这一空白，我们使用了层次图转换的概念[4]，它是通用的，即不致力于特定类型的图或图转换，并从底层图中复制包结构。现有的方法的H-图文法[16]，和层次超图变换[6]，然后通过将它们转换为一般的概念进行比较。这清楚地显示了它们的相似性和差异性，并表明类属概念可以模拟许多层次图的概念。空间只允许概述定义和结果，这将在全文中给出2通用层次图变换通用层次图变换[4]旨在研究图的结构化机制。该定义解释了底层图？ 这项工作得到了ESPRIT 图形转换应用工作组（ESPRIT Working GroupApplications ofGraph Transformation，ESPRIT）的部分支持。1第一作者得到了欧洲TMR网络图变换系统一般理论的资助。 （GetGrats）.c2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2GT-VMT 2001 { G. Busatto和B. 霍夫曼从它的包装结构，使这两个方面可以相互独立的研究。它也是通用的，因此它可以用来扩展任意概念的图转换与包的概念，或模拟现有的概念分层图转换。图表。一 个集合G定义一个图集合，如果每个G2 G都有一个骨架SG=（NG; EG; IG），其中NG和EG是节点和边的集合，IGEGNG是一个关联关系.具有骨架是将实体视为图的最低要求，并且它充当添加到其上的层次结构的接口。一个有向图G由不相交的节点集NG和边集EG组成，每条边都只与一个源节点和一个目标节点相连，并且每个节点（边）都标记在一个给定的集合上（分别为）的标签。显然，每个有向图G都提供了一个骨架;如果它有一个可区别的根r2NG，则它是有根的，使得对于所有的n2NG，在G中存在一条从r到n的路。（有根图用于包层次结构。）（U; P）上的二部图C|即 一个有向图，其中所有边的一端在M中，另一端在N中|是一个耦合图，如果它导出一个关联关系CP将U的每个节点分配给P的至少一个节点。一个耦合图C是紧的，如果它也导出一个对应关系CU将P的每个节点锚定在联合（耦合图用于连接包图和底层图。通用层次图。一 个一般的层次图是一个三元组H =（U; P; C），它有一个底层图U（任何类型的，只要它有一个骨架），一个根包图P，和一个节点上的二分耦合图C（NU[E U; NP）。如果C是紧耦合的，则H称为紧耦合，否则称为松耦合。请注意，H的组件的并集不是一个图，因为C使用U的边作为节点。基本的转化方法。图变换方法的概念已经在[1]中形式化，以便尽可能多地指定各种图变换的共同特征。（见[17]的方法调查。） 这里我们只考虑基本的图变换方法A=（G;R;）），其中G是一类图，R是一类规则，）是一个规则应用操作器，它将二进制规则关联到每个规则r2R。我们忽略了[1]中用于编程和规范的控制条件和图类表达式通用分层图转换。一种基本的层次图变换方法AH=（H;RHi）H）是通过将图Gu上的一种图变换方法An与根图上的两种图变换方法Ap和耦合图上的两种图变换方法Ac通过分量合成结合起来而构造的.如果它的组件接近同一个应用程序操作员，我们称之为AH同源。3HU PCGT-VMT 2001 { G. Busatto和B. 霍夫曼图类和规则类被定义为相应构件类的乘积，它们的语义也是按构件构造的。应用运算符定义为：）=f（（U;P;C）;（U0; P0;C0））2H HjU）U0; P）P0; C）C0g）Fig. 1. 一种层次图转换。图1描述了一个分层图转换步骤，其中，对于主机和结果图，使用带有选项卡的大矩形节点（包）来描述分层图，底层图具有小的方形节点，耦合图具有虚线边缘。(The省略了边与包的关联）。显示的操作涉及删除节点和锚定到该节点的包。基础主机图中与已删除包关联的右上方节点将移动到根包。3Pratt H-图文法在[16]中，层次图（所谓的H图）为编程语言语义的定义建模运行时数据结构，H图语法为它们建模操作。一个H-图包含一个全局节点集N，其中每个节点要么在一个给定的原子集A上被标记，要么它包含一个N上的有向图，从而产生一个层次结构。每个H-图文法产生式指定用新的H-图替换原子节点。原始H图中被替换节点的边被重定向到产生式右侧的两个特殊节点我们使用NLC图重写（参见例如，[8]）用于建模H-图文法。在这种方法中，主机图的诱导子图被匹配的规则的左手边的图，替换为右手边的副本，和新的连接边的全局连接指令集的控制下创建。H-图H通过将其分解为三个图而转化为层次图HG（H）：底层图U（H）包含H的所有节点和从层次的所有局部图收集的所有边;层次图P（H）包含一个根包，每个非原子节点包含一个包，并且包q嵌套在包q0中，如果对应的节点n和n04RprGT-VMT 2001 { G. Busatto和B. 霍夫曼嵌套在H中;耦合图C（H）包含来自P（H）的所有包，来自U（H）的所有节点和边，并将每个节点或边关联到其所属的包（其中H的根节点被分配给根包），并将每个包关联到其对应的节点。三个分量图的节点标签将原始标签编码为H和附加信息|由连接指令使用|确定节点是生产中的输入或输出节点还是正常节点。一个H-文法被转换成一组层次图规则|对于每个生产p，一个NLC规则三元组（p; p; p）|以及连接指令的全局集合C。产生式p（p）指定用图替换节点（包），而p指定用来自p和p的所有节点和包替换节点及其对应的包，并在它们之间插入必要的耦合边。给定这样一个层次规则r，我们考虑从层次图HG =（U（H）;P（H）; C（H））的特殊直接导出，其中p和p被应用于U（H）和C（H）中的相同节点，并且p和p被应用于P（H）和C（H）中的相同包。我们用（U（H）; P（H）;C（H））V表示这样的推导 （U0;P0;C0），我们称之为合并衍生步骤。本节的主要结果|其证明在全文中给出[3]|说，我们可以模拟推导的H-图文法的合并派生在相应的语法使用三元组的NLC规则。因此，翻译后的H-图语法规则的合并推导步骤忠实地模仿原始H-图语法推导作为NLC推导步骤的三元组。命题1设H和H0是两个给定的H-图，一个H-文法，p是的规则，r =（p;p; p）是p到一个层次图规则的转换。则H）H0iHG（H）V HG（H0）.4层次超图变换在[6]中，层次超图变换被定义为图编程的计算基础[14]。超图是nite，由节点和可以连接到任意数量节点的标记超边组成。在层次超图中，某些超边（称为框架）可能包含可能再次是层次超图的超图。一个层次超图H被转换为一般层次超图HG（H）=（U; P; C）如下：底层超图U递归地将所有顶层节点和超边与所有框架中包含的所有节点和超边不相交地联合起来。包图P是一棵树，它有一个根包，H中的每一个帧都有一个包，使得P中的边表示帧的直接嵌套。最后，耦合图C关联5R不汞（吨）态射递归地。一种层次超图变换规则t=GT-VMT 2001 { G. Busatto和B. 霍夫曼顶层节点和超边到包，以及直接包含在框架中的所有节点和超边到其包;此外，每个嵌套包对应于一个框架。很容易看出，一般层次图是层次超图i的转换，它在以下意义上是严格的：（i）其底层图是超图;（ii）其包图是树;（iii）每个底层节点和超边都与恰好一个包相关联;（iv）没有包交叉超边：每个超边y都连接到同一包的节点;（v）除了根包之外，每个嵌套包都对应于底层边。层次态射m：H！H0将H和H0的节点和超边映射到彼此上，使得标签、附件和帧被保留，并且H和H0中的对应帧的内容通过分层而相关pPI！R由两个层次态射组成，接口I在模式P和替换R中。(The射P必须是单射的。）变换步骤H（I）H0构造如下：将P匹配为宿主图H的包中的子图，并构造P与该子图之间的单射匹配态射m;从H移除m（P）直到m（p（I））以获得上下文图C;将R的副本添加到C并将m（p（I））与r（R）粘合以获得H0。2合并的一般超图变换。 每个层次态射m：H！ H0一一对应于一般层次超图HG（H）的分量之间的态射的三元组，H G（H0）. 一个层次的直方图变换规则t=Pp 我！R可以因此可以转化为底层图、包图和耦合图上的三重粘合规则 让hg（t）表示一般的层次规则，并且要求变换步骤HG（H） VHG（H0）被并行地进行，使得匹配态射在它们的耦合分量的节点中重叠。然后我们通过态射的对应性得到了这个平移的主要结果：命题2存在一个层次超图变换步骤H）tH0，存在一个一般层次超图变换步骤HG（H）VHG（H0）。5结论通用的层次图变换被证明是通用的，足以代表现有的层次图变换的方法。因此2 这是一种具有单射匹配的胶合图变换[7][13]。R汞（吨）6GT-VMT 2001 { G. Busatto和B. 霍夫曼解耦表示使得特别容易掌握本文中比较的方法的差异，表1中H-graph grammar[16]层次超图变换[6]基础图简单图超图层次结构有根图树耦合紧紧封装锚节点超边封装间边缘是的没有转型类NLC单射胶合表1层次图概念尽管是针对不同的应用程序开发的，但我们的分层图转换模型确实让人想起了三重图语法[18]，三重图语法也提供了某种合并，但与特定的图转换方法有关。相关工作研究了分层图的封装概念[12]（但没有变换的概念），以及（at）图上的视图构造[9]。为了证实我们的猜想，即实际上每一种层次图变换都可以用通用模型来模拟，将研究层次图变换的进一步方法，即变量层次图变换[6]、类型层次图变换[11]和Higraphs [15]此外，通用模型仍然需要在转换规则三元组的不同组件中的元素的相互关系方面进行重新定义。在我们的示例中，这没有问题，因为规则三元组是同构的（使用相同的转换方法），因此可以合并转换。引用[1] M. Andries，G. Engels，A. 哈贝尔湾 何曼，H.- J. Kreowski，S. 库斯克，D. Plump，A. 史昌湖rr和G. 泰泽。 图形变换与程序设计。 计算机编程科学，34：1{54，1999。[2] R. 巴尔多赫，M. Minas，A. 史昌湖rr和G. 泰泽。图变换在可视化语言中的应用。在Engels等人[10]，第3章，第105页{ 180.7GT-VMT 2001 { G. Busatto和B. 霍夫曼[3] G. Busatto和B.何曼。比较分层图变换的概念。技术报告，FachbereichMathematik-Informatik，不来梅大学，2001年。准备中[4] G. Busatto，H. Kreowski和S.库斯克一种抽象层次图数据模型。技术报告，法国数学信息大学2001年在不来梅在印刷中。[5] V. Claus，H. Ehrig和G.罗森伯格，编辑。图文法及其在计算机科学和生物学中的应用，计算机科学讲义第73期。斯普林格，1979年。[6] F.德鲁韦斯湾Ho mann和D.丰满。层次图变换。计算机与系统科学杂志，2001年。接受出版。[7] H.埃里希 图文法的代数理论导论。 在克劳斯等人[5]，第1页{69.[8] J. Engelfriet和G.罗森伯格节点替换图文法。在Rozenberg [17]，第1章，第1页{94.[9] G. Engels，H.埃里格河Heckel和G.坦策基于开放图变换系统的系统建模的视图基方法。在Engels等人[10]，第16章，第639页{668.[10] G. Engels，H. Ehrig，H.- J. Kreowski和G.罗森伯格，编辑。图文法与图变 换 计 算 手 册 ， 第 二 卷 ： 规 范 与 程 序 设 计 。 World Scienti c ，Singapore，1999.[11] G. Engels和R.海克尔图转换作为系统建模和演化的概念和形式框架。在usMontanari，J.罗林，以及E. Welz，editors，Automata，Languages，and Programming（ICALP 2000Proc.），第1853号，计算机科学讲义，第127页。斯普林格，2000年。[12] G. Engels和A. 史昌湖RR.封装层 次 图、图类型和Meta类型。以.Corradini和U.Montanari，编辑，Proc.JointRIGHGRAPH/SEMAGRAPHWorkshoponGraphRewritingandComputation ， 第 2 号 ， 电 子 笔 记 理 论 计 算 机 科 学 ，http://www.elsevier.nl/locate/entcs，1995年。爱思唯尔[13] A. 哈贝尔，J。微米的ller，和D. 丰满。 双推出图变换重访。In G. Engels和G. Rozenberg，编辑，图变换的理论和应用（TAGT'98），论文选集，计算机科学讲义第1764号，第103页。斯普林格，2000年。[14] B. Ho mann和M.米纳斯图语法和语义的通用模型。在ICALP Workshops2000 中 ， Proceedings in Informatics ， 第 443 页 ， 第 450 页 ， Waterloo ，Ontario，Canada，2000中的第8号。卡尔顿山[15] A. Poulovassilis和M. Levene.一个表示和操作复杂对象的嵌套图模型。ACMTransactions on Information Systems，12（1）：35{68，1994.8GT-VMT 2001 { G. Busatto和B. 霍夫曼[16] T. W.普拉特用层次图语法定义程序设计语言语义。在Claus等人[5]，第389页{400.[17] G. 罗森伯格编辑图文法与图变换计算手册World Scienti c，Singapore，1997.[18] A. 史昌湖RR. 用三重图文法设计图翻译器。在G. Tinhofer，编辑，Proc.WG94国际计算机科学中的图论概念研讨会，编号903在计算机科学讲义，第151页{163，Herrsching，1994. 史普林格出版社