图与图变换系统的通用交换格式的开发

28《理论计算机科学电子札记》44卷第4期（2001年）网址：http://www.elsevier.nl/locate/entcs/volume44.html13页图与图变换系统加布里埃莱·坦策柏林第一大学摘要图形和图形转换系统的通用交换格式的开发是欧盟工作组APPLIGRAPH（图形转换应用）的一项持续倡议。作者报告了这种格式讨论的现状。这些格式是基于可扩展标记语言XML开发的，用于交换任意类型的文档。图是计算机科学各个领域的基本结构。图形的通用格式支持软件开发人员构建工具wrt的交互。图布局、图算法、图转换、再工程等。此外，在图转换社区内，工具构建者甚至可以从图转换系统的公共交换格式中1介绍图是一种非常通用的数据结构，用于计算机科学和其他科学的各个领域。为了支持各种基于图形的工具之间的互操作性这些格式是基于可扩展标记语言XML开发的，用于交换任意类型的文档。基于XML的图形交换格式的第一个概要以及这种格式的详细动机已经在[4]中给出。2000年9月，在Paderborn召开了关于图形和图形转换系统的通用交换格式的第一次会议（在APPLIGRAPH内），由G.恩格斯和作者。参与者是 G 。 布 萨 托 湾 博 赫 伦 河 德 普 克河 Heckel ， B.Ho Bertmann ，P.Knirsch，M. 马茨M. 米纳斯山口 Rodgers，A. Schürr，G. Valiente，D. Varro，A. 我和A.1电子邮件：{gabi@cs.tu-berlin.de}2000年1月，出版社dbyElsevierScienceB。 V. 在CCBY-NC-ND许可下开放访问。坦策29Zundorf2. 在这次会议上，提出了五项不同的执行形式建议。其中大部分是关于图和图转换系统的。所有这些都基于DTD（文档类型定义），它以类似语法的方式描述XML文档的抽象语法。给定DTD，可以根据有效性检查XML文档，即如果它是正确的WRT。它的DTD。在APPLIGRAPH会议期间，讨论了图形和图形转换系统的两个常见逻辑模型。这些逻辑模型比DTD稍微抽象一点，并建立在UML类图上。这些逻辑模型的版本将在后面的3.1和4.1节中讨论，它们是基于会议的结果，并进一步讨论了GXL模型。请记住，目前关于共同格式的建议仍在审议中，将举行进一步的会议以最终商定共同格式。这一倡议可以被看作是与其他定义共同的基于XML的交换格式建模和规范技术，如UML是XMI [13]，Petri网，基于规则的系统等Petri网，PNML（Petri网标记语言）已被提出作为标准交换格式[5]。2XML技术可扩展标记语言XML [14]的主要目的是为文档提供结构化的交换设施，并打算作为ASCII的替代品。XML描述的文档具有树状结构，由包含解析或未解析数据的某些实体组成。XML最初被设计用于存储文本文档，现在它越来越多地用于在软件工具之间交换定义良好的数据结构。从这个意义上说，我们希望使用XML来交换图结构和图转换系统。2.1XML语言概念XML文档具有逻辑结构和物理结构。由于在物理上分布在多个实体上，逻辑结构必须形成一个树形结构，其中所有树元素都被适当地嵌套。每个元素由一个开始标签、结束标签、一组子标签（或一个空标签）和一组的属性。标记被括在尖括号中，每个结束标记的名称对应于其开始标记的名称，但带有一个前导斜杠。其他属性在元素的开始标记中描述，并显示为2帕德博恩大学：R. Depke，G.恩格斯河Heckel，Techn. Univ. of Berlin：M. Matz，G.泰恩策大学 不来梅：G. 布萨托湾 Hoglobmann，P. Knirsch，RWTHAach：B. 伯伦大学Erlangen ：M. 米 纳 斯大学Budapest：D. 瓦罗大学BWMunchen ：A. Schuürr， Univ.Koblenz：A.温特，肯特大学：P.罗杰斯，加泰罗尼亚理工大学：G。Valiente坦策30名称-值对的列表。比较3.3节中的示例XML文档的摘录。一 个 XML 文 档 是 有 效 的 ， 如 果 它 有 一 个 相 关 的 文 档 类 型 定 义（DTD），它描述了文档的抽象语法，如果文档的其余部分是根据这个DTD结构化的。DTD为一类文档提供语法标记.语法由元素、其属性、实体或符号的标记声明组成DTD的示例见第3.2和4.2小节。它是计算机科学各个领域的一项持续活动，并进一步为某些类别的文档结构定义DTD对已经定义的XML应用程序和行业倡议蒂韦斯是 给定地点：http://www.oasis-open.org/cover/xml.html#applications。与DTD类似，XML Schema [15]的目的是定义一类文档，事实上XMLSchema提供的功能超出了DTD所提供的功能。XML Schema的规范仍在进行中。可以假设DTD 在标准化之后将被转换成XML 模式。XMLSchema的以下特性值得一提：每个元素的唯一命名空间，可以扩展、限制和重新定义的类型，以及抽象元素和类型。在XML模式标准化之后，我们打算将迄今为止为图和图转换系统开发的DTD和逻辑模型转换为XML模式。第一种方法可以在[11]中找到。2.2支持技术和工具在为某个文档类型开发DTD之前，单独设计文档结构可能很有用，特别是在不存储文本文档而是存储数据或对象结构的情况下。 在这里，首先使用可视化技术（如UML类图[10]），然后将其转换为DTD是有帮助的。图1和图3给出了UML类模型的例子。翻译主要是自动完成XML解析器有两种常见的应用程序编程接口（API）：DOM（文档对象模型）[2]定义了格式良好的DOM模型理想地用作文档的抽象语法结构，适当的文本或图形表示的基础。XML解析器感兴趣的另一个API是使用的SAX（Simple API for XML）[8用于基于事件的XML文档解析。现在有几个基于XML的解析器实现了SAX和DOM接口，参见Xerces [12]。XML解析器还支持根据特定的DTD验证文档，类似地，最初支持XML Schema。坦策313GXL：一种用于交换图形的XML格式图是非常通用的数据结构，出现在计算机科学的各个领域。但是有很多不同的图模型，取决于它们的应用环境。考虑到图用于图的布局、图的转换和再工程，交换格式应该能够处理有向图和无向图、超图、层次图、图类型和属性。在下面的讨论中，图的具体布局并不起作用，因为已经有标记语言SVG（可缩放矢量图形）[9]用于此目的。此外，还有另一种基于XML的图形交换格式GraphXML [3]，用于图形绘制和可视化。此外，我们将不详细讨论图属性。这样一个通用的数据结构几乎可以归因于一切。GXL（图形交换语言）的第一个大纲以及这种格式的详细动机已经在[4]中给出3.1逻辑图模型在为图开发XML DTD之前，我们使用UML类图讨论底层的逻辑图模型。比较图1中的图的UML类模型。该模型是[4]中GXL模型相应模型的简化和略微修改一个GXLDoc-图形包含一组图形，其中每个图形都有一组图形元素。图形元素可以是节点、边或关系，能够存储超边。边和关系都可以被定向，由它们共同的超类LocalConnection表示。此外，允许有悬挂边的部分图，因为允许从和到的关联的重数 关系具有存储角色名称和方向并指向图形元素的链接。这样，边上边或超边是可能的。我们的设计决策之一是将边与关系区分开来，这增加了简单图的XML文档的可读性，尽管边可能被视为具有两个链接“from”和“to”的特殊关系图和图元素是TypedElement，这意味着存在类型图，其中图元素用作节点、边和关系的类型。类型图也可能存储在另一个GXL文档中，因此它必须保持相应的指针（Type）。每个图形元素都是一个属性元素，它可以有一组属性。 每个属性都有名称、类型和值。 该值可以是可能位于另一文档中的原始值、容器或复合值。层次图可以用几种方式存储：通过细化图元素，通过属性或特殊边。复杂属性值可以再次是一个图，这样可以描述分层图。这里在不同的复合节点中，图之间不可能有边。存储层次图的另一种可能性是特殊的细化边坦策320.. 1个hasType1类型0..1Attr企业简介10.. 1文档图表引导10..1从0..1到ref{ordered}0..1边类引导LocalConnection作用引导GraphElement链路TypedElement类型GXL文档关系节点NamedElement属性元素名称ID值0..1Fig. 1. 图的逻辑模型(to通过边的成员种类来区分）。在这种情况下，具有节点之间的边和复合节点的层次图可以被非常一般地描述。存储分层图的另一种可能性是允许图再次成为图元素。这个解决方案是相当有限制性的，因为它不允许通过边丛来细化边。但将这种可能性纳入模型中以增加简单层次图的可读性似乎是一个好主意。3.2GXLXML文档是树，将图存储在树中意味着将其二维结构线性化。这种翻译或多或少是自动的。下面给出了对应于图1中模型的DTD的基本部分。在这里，模型的每个具体类都产生一个元素。 类成员和关联定义了这个元素的属性列表（ATTLIST）。关联产生指向另一个元素的某个ID的属性条目，即IDREF。这种引用的类型不能在DTD中表示，因此附加的注释解释了需要哪些类型聚合被转换为子元素关系。注意，与逻辑模型不同，子元素可以在DTD中排序。抽象类不会被转换为元素，但它们的成员、关联和聚合会作为属性和子元素添加到从继承类生成的所有元素<！ELEMENT GXL文档（图 *）><！ELEMENT图形（属性 *，（节点|边缘|关系）*）>坦策33<！ATTLIST图表IDID #必填名称NMTOKEN#隐含输入IDREF #IMPLIED！-- 类型|Graph--> directed（true|“true”><！ELEMENT节点 （属性 *，图表 *）><！ATTLIST节点IDID #必填键入IDREF#IMPLIED>！-- 类型--><！ELEMENTEdge（Attr*，Graph*）><！ATTLIST边缘IDID #隐含类型IDREF#暗示<！-- 类型-->从IDREF #隐 含！-- 节 点|边缘|Relation--> toIDREF #IMPLIED<！-- 节点|边缘|关系-->种类（ 精炼|正常）#隐含定向（true| false）#IMPLIED><！ELEMENT关系（属性 *，（链接|图表）*）><！ATTLIST关系IDID #隐含输入IDREF#IMPLIED！-- 类型-->引导(true|false)#IMPLIED><！ELEMENT Link（Attr*）><！ATTLIST链接refIDREF #必填！--节点|边缘|Relation--> roleNMTOKEN #IMPLIED定向（true| false）#IMPLIED><！ELEMENTAttr（Attr*，价值？）>的<！ATTLIST属性nameNMTOKEN#必填输入IDREF #IMPLIED！-- Type-->kindNMTOKEN#IMPLIED>3.3GXL图形示例在图2中，给出了一个示例图，它包含了一个图可以具有的几乎所有结构特征。节点A被细化为内部绘制的图形部分这个节点。存在关系（超边）f和g，其中f的一条链指向g。边a是局部的，它没有目标。边c和d是相同节点C和D之间的平行边，边e是环。边b位于简单节点和复合节点之间GXL文档的一节坦策34FBBG一一eDC dC图二. 的采样图对应于图2中的图表和前面小节中给出的DTD的示例如下所示。<图id=“G”><节点id=“A”>/节点><图id =“sub-A”><节点id=“C”>/节点><节点id=“D”>/节点>/Edge>/Edge>/Edge><节点id=“B”>/节点>/Edge>/Edge><关系id=“f”>/Link>/Link><关系id=“g”>/Link>4GTXL：图形转换系统交换的XML格式在GXL作为图形交换格式的基础上，我们考虑了图形转换系统的交换。这种格式在下文中被称为GTXL，在图变换社区内不仅对图而且对图变换系统的图规则、控制结构等进行互换是有意义的。到目前为止，可用的图形转换工具主要侧重于不同的方面。对于图形转换，支持方便的解释、规则和转换的分析或代码生成，但不是由同一个工具。通用交换格式坦策35图形转换工具支持的图形转换可以帮助与几个工具进行协作。4.1图变换系统与GXL类似，GTXL也首先创建逻辑模型。比较图3。一个GTS（图转换系统）由一组图，一组操作和一个类型（图）组成。如果图的基数为1，则给出一个图文法。存储更多的图形可能有助于保存中间结果或定义可能的结果。操作可以被分组在OpGroup中，OpGroup是再次作为操作的某个控制结构，例如，规则可以被分组在本身是操作的转换单元[1]中。每个操作都可以有一个参数列表，其中每个参数都包含一个名称和一个ptype。一个特殊的操作是由两个RuleGraphs和一个Mapping组成的规则。一个规则图不仅包含一个图，而且还包含一组条件，这些条件可以用作前置条件或后置条件。这些条件可以是包含属性或GraphConditions上的布尔表达式的AttrConditions。每个GraphCondition都包含一个Mapping和一个RuleGraph，这样GraphCondition就可以嵌套。每个映射都由一组在两个GraphElement之间运行的MapElements组成。规则可以有一个额外的嵌入部分，其中指定了将右侧规则图嵌入到上下文图中。考虑到各种图变换方法，它们在规则的定义上存在很大我们的目的是提供一种足够通用的规则语法所有这些方法的共同之处是通过三个图部分来指定规则：一个要删除，一个要保留，一个要创建。这些由两个规则图和它们之间的映射描述。第一个图中所有未映射的部分都将被删除。保留所有映射的部分，并创建第二个规则图中没有映射的一些图变换方法支持负应用条件。这类条件可以被描述为图条件，其具有从对应规则的左手侧到另一个图的映射，该另一个图包含表达不允许的内容的附加图部分。此外，逻辑模型允许嵌套图条件，使得含义是可能的。这取决于读者来比较这个图转换系统的逻辑模型的第一个版本与主要的图转换方法。有几个概念还没有定义，即控制结构、嵌入和表达式。完善这些概念将是我们接下来的任务之一。坦策360.. 1类{ordered}210..11参数名称ptype类型11到 1表达映射属性条件种GraphCondition条件类型嵌入图GTS类型ID名称属性元素NamedElement操作规则规则图控制结构操作组月1地图元素GraphElement图三. 图变换系统4.2GTXL从给定的逻辑模型生成DTD的过程在3.2节中有简短下面的GTXL的DTD提取是以相同的方式生成的。<！元素GTS（属性 *，（图形|规则|OpGroup）*）><！GTS会员IDID#必填名称NMTOKEN #隐含键入IDREF #IMPLIED>！--类型--><！ELEMENT OpGroup EMPTY<！ELEMENT规则（RuleGraph，RuleGraph，Mapping，Parameter*，Embedding？，Attr*）><！ATTLIST规则IDID#REQUIREDnameNMTOKEN #IMPLIED><！ELEMENT Mapping（Attr*， MapElem*）><！ATTLIST映射IDID#REQUIREDnameNMTOKEN#IMPLIED><！ELEMENT Map元素空><！联系我们从IDREF #必填<！-- 节点|边缘|Relation--> toIDREF #REQUIRED><！-- 节点|边缘|关系--><！ELEMENT规则图（图，（AttrCondition |GraphCondition）*）>坦策37<！ATTLIST规则图IDID#REQUIREDnameNMTOKEN #IMPLIED><！ELEMENT GraphCondition（Attr*， RuleGraph，Mapping）><！ATTLIST GraphConditionidID#REQUIREDnameNMTOKEN#ImplicitkindNMTOKEN#Implicit><！ELEMENTAttrCondition（表达式）><！ATTLIST AttrConditionIDID所需数量名称NMTOKEN#暗示种NMTOKEN#暗示><！ELEMENT表达式（#PCDATA）><！ELEMENT Embedding（#PCDATA）><！ELEMENT参数（空）><！ATTLIST参数nameNMTOKEN#必填输入 IDREF#必填<！-- 类型|节点|边缘|关系|联系我们ptype（in|出来|inout）#必填>GTXL旨在用作所有主要图形转换方法的交换格式，图转换系统的主要概念是规则。尽管将GTXL的格式定义与人工智能领域开发的规则标记语言（RuleML）[7]进行比较会很有趣。4.3一个示例图形转换系统在图4中，给出了一个非常简单的图形转换系统作为示例。 它是一个有一个开始图和一条规则的图文法。如果源节点通过超边界连接到另一个节点，则该规则将创建一条带有新目标节点的新边。将删除超边和另一个节点。此外，该规则包含一个否定的应用条件，如果一个环边被附加到源节点，则该条件禁止应用该规则下面显示了与给定的图语法和前面小节中给出的DTD相对应的GTXL部分坦策38无回路DDFeGGEHB一CABCStartGraph GG =（StartGraph，{ Rule1 }）Rule1：见图4。 样本图转换系统<节点id=“A”>/节点><节点id=“B”>/节点><节点id=“C”>/节点>/Edge>/Edge><关系id=“c”>/Link>/Link><规则id=“r”name=“Rule1”><图id=“l”directed=“true”><节点id=“D”>/节点><节点id=“E”>/节点><关系id=“d”>/Link>/Link><节点id=“H”>/节点>/Edge><映射id=“m”>坦策39/MapElem><节点id=“F”>/节点><节点id=“G”>/节点>/Edge><映射id=“m”>/MapElem>5结论为图形和图形转换系统寻找一种通用的基于XML的交换格式是欧盟工作组APPLIGRAPH的一项持续计划。目前，我们正在讨论常用的逻辑模型，并计划在2001年3月确定该格式的核心。已经在几个基于图的工具中实现了该格式的初步版本，以获得XML技术的经验。此外，新的基于XML的格式可以用作新的存储格式的图形和图形转换系统，这是人类可读的。我们希望我们确定的通用格式很快将得到各种基于图形的工具的支持，并大大提高它们的互操作性引用[1] M. Andries，G. Engels，A.哈贝尔湾Ho Bertmann，H.- J. Kreowski，S. 库斯克，D. Plump，A. Sch？r，andG. 泰泽。 图形转换用于具体化和编程。计算机程序设计科学，34：1 -54，1999。[2] 文档对象模型（DOM）第2级核心规范。网址：http：//www.w3.org/TR/DOM-Level- 2.[3] GraphXML。可在www.example.com上查阅http://www.cwi.nl/InfoVisu/GraphXML。[4] R. Holt，A. 是的，我知道。 很好。GXL：以标准的Exchange格式。在Proc.7th Working Conference on Reverse Engineering（WCRE 2000） ，第162IEEE计算机协会。坦策40[5] M. Jüngel，E. 金德勒和M. 我们是。这是一种语言。InS. Philippi，editor，Altain menundWerkzeugefur？rPetrinetze（AWPN），Koblenz，June2000，2000.可在www.example.com上查阅http://www.informatik.hu-berlin。de/top/pnml.[6] G. 罗森伯格编辑图文法与图变换计算手册。世界科学，1997年。[7] 规 则 标 记 语 言 （ RuleML ） 。 可 在 www.example.com 上 查 阅http://www.dfki.uni-kl。de/ruleml.[8] SAX2.0 ： XML 的 简 单 API 。 可 从 以 下 网 址 获 得 ：http://www.megginson.com/SAX。[9] 可缩放矢量图形。 可在www.example.com上查阅http://www.w3.org/TR/SVG。[10] 统一建模语言 可在www.example.com上http://www.omg。org/uml.[11] D. Varro和A.帕塔里查 图转换系统的XML模式描述。技术报告，布达佩斯技术和经济大学，2000年。[12] 薛西斯 可在www.example.com上查阅http://xml.apache.org/。[13] XML元数据交换。可查阅：http://www.oasis-open.org/cover/xmi.html。[14] 可扩展标记语言（XML）。 可在www.example.com上查阅http://www.w3c.org/xml。[15] XML架构第0部分：入门。可在http://www.w3.org/TR/xmlschema-0上查阅。