vCGG:一種基于虛結點的空間圖文法形式框架*

2021-02-25 12:15劉禹鋒

軟件學報 2021年12期

劉禹鋒,楊帆

(南京財經大學信息工程學院,江蘇南京 210046)

作為一種豐富的信息描述手段,可視化語言(可視化圖)是軟件系統概念設計階段中重要的人機交互工具,例如數據庫系統概念設計階段的 E-R(entity-relationship)圖、面向對象系統中的 UML(unified modeling language)圖以及描述離散并行系統的Petri 網.可視化語言研究的重點之一是如何使用有效而又規范的方式去描述各種不同類型的可視化語言.一部分研究者嘗試使用一維字符文法描述可視化語言,然而,由于圖的二維性以及非線性特點,字符文法在描述可視化語言時有著表達能力不足以及直觀性較差等問題.基于形式語言理論,圖文法是一種使用產生式(圖重寫規則)進行圖語言定義與分析的二維化形式化工具.使用圖文法對各種可視化語言語法結構的描述、操縱和分析,具有直觀明了和簡便的優點.至今,圖文法已被廣泛地應用于各種可視化語言的配置與分析中,例如圖語言定義與轉換[1]、圖模型的動態分析[2].不僅如此,圖文法還被廣泛地應用于軟件系統建模[3,4]、信息可視化[5]、模式識別[6-8]等領域.

作為二維或三維空間上最重要的特征之一,空間語義信息在可視化語言的空間拓撲結構描述以及空間知識呈現上是不可或缺的關鍵因素之一.然而,大多數圖文法在面向空間語義處理需求時存在諸多困難之處.Stiny和Gips 從描述空間元素形狀的角度出發,提出了形狀文法SG(shape grammar)[9,10].SG 將形狀定義為一系列空間元素的有限排列,例如線段、點、矩形.SG 的文法直觀易懂,可以被廣泛地應用于建筑圖像分析[11]、繪圖設計[12]等領域.根據事先定義的規則,SG 可以通過迭代地使用形狀替換操作來生成各種各樣的設計.然而,由于只支持單方向的工作流,SG 更側重于完成不同類型圖形的生成繪制工作,而在圖形分析處理能力上有所欠缺.Kong 等人[13,14]在上下文相關圖文法RGG(reserved graph grammar)[15]形式框架中加入了空間信息處理機制,提出了一種空間圖文法——SGG(spatial graph grammar).SGG 對空間語義信息采用定性研究方法進行描述,包括6 種拓撲關系、4 種方向關系、順序距離關系以及7 種對齊關系.基于定性分析方法,SGG 可以較為直觀靈活地分析各種可視化語言的語法與語義結構,在網頁描述及模式驗證[16,17]領域取得了較好的應用效果.然而,SGG 也有存在一些不足之處:首先,由于對空間語義信息缺少定量描述能力,SGG 在對空間關系進行配置時缺乏相應的精準性;其次,SGG 中使用額外的語義函數描述空間語義關系,并通過執行操作代碼實現語義變換,較大程度地增加了SGG 在實際應用中的復雜性.針對SG 與SGG 文法框架的局限性,本文作者在前期研究中提出了一種坐標圖文法框架——CGG(coordinate graph grammar)[18],將空間語義信息的定量和定性描述機制整合在一個理論框架內,并利用圖形元素之間的坐標關系設計了相對低時間開銷的圖柄查找算法,為空間語義信息提供了相對靈活的配置方案.表1 給出了CGG 與SG、SGG 這兩種具有代表性的空間文法框架的對比,CGG 在保持SG 和SGG優點的同時彌補了兩者的不足,為空間語義配置提供了一個更全面的形式化框架.目前,CGG 已被應用在UML類圖定義與布局[19]、流程圖生成與檢測[18]等實際案例中.然而,CGG 是在EGG(edge based graph grammar)[20]的理論框架的基礎上加入空間語義機制而構建的圖文法形式框架,因此,EGG 的部分缺陷延伸到了CGG 中:首先,CGG 中懸邊圖的概念不符合圖論中點邊圖的定義,使得圖柄結構的規范性有所欠缺;其次,在CGG 的歸約操作中,懸邊的匹配需要考慮圖柄排列問題,導致大量冗余圖柄的出現,在一定程度上增加了歸約執行步數,也導致大量無效歸約的產生;最后,CGG 產生式中使用懸邊描述上下文信息,通過減少上下文信息的匹配提高文法的抽象程度,卻在某種程度上影響了文法的直觀性以及表達能力.針對上述問題,本文在前期研究的基礎上,通過定義虛結點的概念,構建一個新的空間圖文法框架vCGG(virtual node based coordinate graph grammar).該框架在文法中保留上下文結點的同時,維持CGG 產生式的抽象能力,從而為圖的空間語義提供更加直觀而全面的形式化描述與分析手段.

Table 1 Comparison among SG,SGG and CGG[18]表1 CGG 與SG、SGG 的對比[18]

本文第1 節介紹CGG 的理論框架.第2 節在CGG 基礎上構建一個新的空間圖文法框架vCGG,包括框架的基本概念與文法操作.第3 節對vCGG 與幾種具有代表性的空間圖文法進行對比分析.第4 節給出總結及展望.

1 CGG 形式框架

1.1 基本概念

CGG 是在上下文相關圖文法EGG 中引入空間語義機制擴展而來的空間圖文法形式框架,通過在傳統連續坐標的基礎上定義離散坐標的概念,使用兩個子框架cCGG(continuous coordinate graph grammar)和dCGG (discrete coordinate graph grammar),為分別空間語義提供定量與定性描述粒度.以下給出CGG 中的基本概念.

定義1.1.G=(N,E)是一個定義在標號集L上的空間語義圖,當且僅當:

?N是一個結點集,并且可以進一步被分為兩個子集合:終結點集NT和非終結點集NNT;

?E?N×N是一個有向邊集.

為了方便語法語義操作,CGG 定義了以下幾個函數.

?fNL:N→L是一個從結點n∈N到標號l∈L的映射,即fNL(n)=n.l;

?fNC:N→R×R是一個從結點n∈N到坐標c∈R×R的映射;

定義1.2.給定一個空間語義圖G,結點n∈G.N的離散坐標是(rx,ry),當且僅當:

?rx和ry分別是fNC(n).x和fNC(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之間存在兩個雙射:fNN:G.N?Q.N和fEE:G.E?Q.E,并滿足以下條件.

滿足同構關系的兩個圖有著一一對應的結點和邊,其中,對應結點擁有相同的標號,并且對應邊的起始結點和結束結點也需符合該對應關系.

定義1.4.圖Q是一個包含懸邊的圖的核圖,記作Q=,當且僅當:

定義1.5.如果圖Q是一個給定主圖G的子圖并可能帶有懸邊,并且圖是一個產生式的左圖或右圖,圖Q是圖在主圖G中的圖柄,記作,當且僅當:存在兩個雙射:fNN:Q.N?.N和fEE:Q.E?.E,并滿足以下條件.

在CGG 中,圖柄不僅要求與某個產生式圖形成同構關系,還需滿足空間上的語義匹配要求.根據不同的粒度描述選擇,子框架cCGG 要求產生式圖中任意兩個結點和它們在圖柄Q中對應的結點具有完全相等的坐標差值;而dCGG 要求產生式圖和圖柄Q具有等價的空間拓撲結構,即中任意一個結點和它在圖柄Q中對應的結點具有完全相等的離散坐標值.

在圖文法的推導或歸約工作流中,在根據一個產生式圖找到其在主圖中的圖柄后,便可以對圖柄執行圖轉換操作.根據不同的配置粒度,cCGG 和dCGG 中圖轉換操作的具體步驟如下.

1) 根據當前產生式生成一個產生式實例;

? cCGG:將圖柄中的任意結點n與其在產生式圖中的對應節點n′的坐標差值,即n.c-n′.c,作為偏移量平移產生式的另一端;

3) 從主圖中刪除圖柄;

圖2 是一個CGG 中R-application 的例子,其中,圖2(a)是一個給定主圖,圖2(b)和圖2(c)分別是一個cCGG產生式和dCGG 產生式.對于cCGG 產生式,產生式實例的左圖使用偏移量(0,1.5)進行平移,該偏移量是圖2(a)中虛線框內所示圖柄與產生式右圖之間匹配結點的坐標差值.而對于dCGG 產生式,首先在產生式右圖中選擇具有最大“Y”坐標值的結點“stat1”,然后將圖柄中的對應結點與結點“stat1”的坐標差值(-1,0)作為偏移量,平移產生式左圖.在該例中,使用cCGG 產生式和dCGG 產生式對圖柄進行R-application 操作,得到的是兩個不同的主圖,如圖2(d)、圖2(e)所示.

Fig.2 An example of CGG R-application圖2 CGG 中R-application 實例

1.2 框架缺陷

由于延續了EGG 的懸邊機制,CGG 存在一個較為明顯的表達能力上的缺陷——Lcf圖語言問題[21].如圖3所示,圖語言Lcf是由一對“fork”,“join”結點以及它們之間的任意數量(不小于2)“stat”分支組成的一類流程圖.對于這一類圖語言,無法通過有限數量的EGG 或CGG 產生式描述所有可能情形下的Lcf圖.其原因在于:如果要描述任意一個Lcf,由于“stat”分支的數量是未知的,無法在產生式設計階段窮舉所有分支,從而無法在產生式中確定“fork”與“join”結點所連接的懸邊數量.Lcf圖語言問題可以通過定義額外的通配懸邊加以解決,然而通配懸邊的處理在一定程度上增加了產生式以及文法操作的復雜性.相比之下,圖文法LGG 和RGG 則不存在這個問題.在產生式設計階段,LGG 可以將出入邊數量未知的結點(例如“fork”和“join”結點)作為上下文結點,在匹配時不需要考慮上下文結點的出入度;RGG 使用雙層結構結點中標記的頂點來關聯上下文,在匹配時不需要考慮頂點所連接邊的數量.

Fig.3 An example of the graphical language Lcf圖3 一個圖語言Lcf 的例子

懸邊機制帶來的另一個問題是懸邊映射問題.在EGG 和CGG 的工作流中,當一個主圖子圖與產生式圖符合圖柄匹配條件時,若產生式圖中存在一個結點連接了兩條及兩條以上同方向的懸邊,需根據這些懸邊在主圖中不同映射情況生成多個圖柄進行處理[20].如圖4 所示,左側主圖虛線框內的子圖與產生式p1 與p2 的右圖之間均滿足圖柄匹配條件.由于產生式p1 的右圖結點“stat”連接了兩條同方向的懸邊“1”、懸邊“2”,兩條懸邊與主圖中對應結點“stat”所連接的邊(stat,a-branch),(stat,b-branch)之間存在兩種雙射,而在不同雙射情況下進行R- application 會產生兩種具有不同結構的主圖,因此,兩種雙射情況下的圖柄應當被視為不同的圖柄.這種規定可以保證圖轉換結果的唯一性,然而該規定在一些場景下并不是必要的.例如:對于圖4 中的產生式p2,在任意一種雙射情況下對主圖進行R-application 所產生的新主圖均具有相同的結構.原因在于:懸邊“1”、懸邊“2”在產生式p2 的左圖中只與一個結點“stat2”相連接,在進行子圖替換的過程中,主圖的余圖只能與該結點進行連接,因而不會出現兩種圖轉換結果.在這種情況下,如果按照上述規定進行歸約,則容易因圖柄集規模擴大而導致多余回溯的出現,產生不必要的分析時間開銷.

2 vCGG 形式框架

2.1 基本概念

針對空間圖文法存在的問題,本章在繼承CGG 形式框架空間語義機制的前提下構建新的空間圖文法框架vCGG,該框架引入虛結點作為上下文結點,描述圖柄與產生式之間語法結構與空間語義上的關系,在保留文法抽象性的同時,增加文法的表達能力與分析效率.由于CGG 使用兩個子框架dCGG 與cCGG 分別處理定性與定量空間語義關系,vCGG 根據空間語義的不同粒度描述分為vdCGG(virtual-node based discrete coordinate graph grammar)與vcCGG(virtual-node based continuous coordinate graph grammar),以下是vCGG 形式框架中基本概念的定義.

Fig.4 Examples of dangling-edges mapping problem圖4 懸邊映射問題的例子

定義2.1.G=(N,E)是一個定義在標號集L上的空間語義圖,當且僅當:

?L=Lv∪Lr,Lv∩Lr=?,其中,Lv是虛結點的標號集,Lr是實結點的標號集;

?Lr=LT∪LNT,LT∩LNT=?,其中,LT是終結點的標號集,LNT是非終結點的標號集;

?N是一個結點集并且可以被分為兩個子集合:虛結點集Nv、實結點集Nr,其中,實結點集Nr可以進一步分為終結點集NT和非終結點集NNT;

?E?N×N是一個有向邊集.

為了方便于語法語義操作,CGG 定義了以下幾個函數.

?fNL:N→L是一個從結點n∈N到標號l∈L的映射,即fNL(n)=n.l;

?fNC:N→R×R是一個從結點n∈N到坐標c∈R×R的映射;

? :EN→ 是一個從有向邊e∈E到它的起始結點的映射;

在vCGG 中,圖中包含的結點根據分配的標號被分成了兩類:虛結點和實結點,其中,實結點可以進一步地分為終結點與非終結點.實結點的標號集定義與CGG 相同,而虛結點的標號主要用于區分不同虛結點標記,不包含其他語義信息,因此,主圖中虛結點在通常情況下其標號集為空,即主圖的所有結點都是實結點.虛結點的主要作用是描述主圖與產生式的語法結構與空間語義關系,下面給出vCGG 產生式的定義.

定義2.2.產生式是兩個圖GL和GR組成的形如GL:=GR的表達式,在GL和GR之間存在一個雙射fNN:GL.Nv?GR.Nv,并滿足以下條件.

vCGG 將虛結點引入產生式結構中.在一個產生式圖中,虛結點表示上下文結點,而實結點代表非上下文結點,也可稱為產生式內部結點.為了圖轉換操作的可執行性,vCGG 規定:同一個產生式兩端的虛結點集之間需存在一個雙射,并且對應的結點擁有相等的標號與坐標.此外,為了圖嵌入過程中不產生歧義,同一個圖中的每一個虛結點具有唯一的標號,可以用唯一的整數表示.例如,圖5 是一個合法的vCGG 產生式,其中,虛線圓框代表虛結點,實線圓框代表實結點.

Fig.5 vCGG production圖5 vCGG 產生式

由圖5 可見:產生式左圖與右圖之間存在一個雙射,并且對應結點具有相同的標號“1”、標號“2”以及相等的坐標(1,3),(1,1).

定義2.3.圖G與圖Q是同構關系,記作G≈Q,其中,G和Q之間存在兩個雙射:fNN:G.N?Q.N和fEE:G.E?Q.E,并滿足以下條件.

在判定一對圖是否滿足同構條件時,虛結點比實結點具有更高的抽象程度,可以匹配任意標號的結點.圖6是一個vCGG 中圖同構的例子,其中,所有結點和邊在滿足雙射關系的.其中,實結點“stat”和對應結點必須具有相同的標號,而虛結點“1”、虛結點“2”可以匹配任何標號的結點(圖6 中為“begin”“end”).

Fig.6 Theisomorphic graphs in vCGG圖6 vCGG 中具有同構關系的圖

其中,fNL和是Q和GL|R的結點標號映射,fNC和分別是Q和GL|R的結點坐標映射.

基于不同的空間語義描述粒度,vCGG 兩個子框架vcCGG 與vdCGG 的圖柄定義有所不同.在滿足同構關系的前提下,vcCGG 要求圖柄和產生式圖需要滿足坐標關系的完全匹配,產生式圖中任意兩個結點與它們在主圖中對應結點具有相等的坐標差,即產生式圖通過平移可以與圖柄完全重合.與vcCGG 相比,vdCGG 空間語義匹配條件按照虛結點和實結點分為兩個層次:在第1 層,圖柄和產生式圖的對應結點需要在各自空間內部具有相等的離散坐標;在第2 層,虛節點之間的定量坐標關系需要和對應主圖結點完全一致,即所有虛結點可以同時通過平移與其在圖柄中的對應結點完全重合.匹配要求的劃分使vCGG 既能對產生式內部結點提供定性與定量的拓撲關系描述,也能維持上下文結點的一致性.例如:圖7(a)是一個主圖,若根據圖7(b)中產生式右圖在主圖中查找圖柄時,在vcCGG 和vdCGG 中的任何一個子框架下,該產生式右圖都符合圖柄的匹配條件;而當在主圖中查找圖7(b)中產生式右圖的圖柄時,在vcCGG 框架下產生式右圖與主圖的任何一個子圖都不符合坐標匹配條件,而在vdCGG 框架下則可以成功查找到所需圖柄.此外,vCGG 要求圖柄中實結點在主圖中的出入度與產生式圖中對應結點完全相等,保證了圖柄中所有與產生式圖中實結點對應的結點在主圖中只能與虛結點對應的結點相連接,在圖轉換過程中避免了懸邊的出現.

Fig.7 The redex matching in vCGG圖7 vCGG 中的圖柄匹配

2.2 文法操作

圖文法的主要工作流是圖推導與歸約,分別面向實際應用中圖的生成與分析需求.推導與歸約工作流的基本構成要素是圖轉換操作.圖轉換操作根據其執行方向可以分為 L-application 與 R-application,其中,L- application 是指用產生式右圖替換左圖在主圖中圖柄的操作,而R-application 用產生式左圖替換右圖在主圖中圖柄.L/R application 中的一個重要問題是如何避免轉換后的新主圖中產生懸邊,即嵌入問題.在vCGG 中,由于在產生式使用虛結點作為上下文結點,可以使用粘合的方式解決嵌入問題.根據不同的配置粒度要求,vcCGG 和vdCGG 中L/R application 的具體步驟如下.

1) 根據當前產生式生成一個產生式實例;

2) 平移產生式實例的右圖或左圖GR|L.

? vcCGG:將圖柄中的任意結點n與其在產生式圖GL|R中的對應節點n′的坐標差值,即n.c-n′.c,作為偏移量平移產生式的另一端GR|L;

? vdCGG:首先,在產生式圖GL|R中選擇任意一個虛結點n′,將圖柄中的對應結點n與n′的坐標差值n.c-n′.c作為偏移量平移另一個產生式圖GR|L;

3) 從主圖中刪除圖柄中所有的邊以及與GL|R中實結點匹配的結點;

4) 按照產生式圖GL|R的虛節點與圖柄結點的映射關系,粘合產生式圖GR|L的虛結點與圖柄中對應結點,并在主圖中去除該虛標號.

vCGG 圖轉換的操作繼承了CGG 中的坐標映射機制,即產生式局部坐標與主圖全局坐標的映射關系,區別在于:vdCGG 基于虛結點而計算獲得坐標偏移量,而dCGG 的偏移量是基于最大“Y”值的結點而計算得出.相比之下,vdCGG 偏移量的可解釋性更好,產生式設計人員的學習曲線較為平緩.圖8 描述了使用圖7 中的產生式p1和p2 對圖7(a)中的主圖分別進行R-application 生成的新主圖,其中,圖8(a)是使用圖7(a)中產生式p1 在vcCGG框架下生成的新主圖,圖8(b)是使用產生式p2 按照vdCGG 的R-application 步驟生成的主圖.

Fig.8 New host graphs generated by the productions in Fig.7圖8 使用圖7 中產生式進行R-application 生成的新主圖

2.3 vCGG及其語言定義

定義2.5.vCGG 是一個四元組(λ,L,P,S),其中,

? λ是一個初始圖;

?L=Lv∪Lr,Lv∩Lr=?,其中,Lv是虛結點的標號集,Lr是實結點的標號集;

?Lr=LT∪LNT,LT∩LNT=?,其中,LT是終結點的標號集,LNT是非終結點的標號集;

?P是一個產生式集;

?S是一個由若干正實數組成的標尺集,并且滿足關系:S?R+.

為了避免產生式的冗余,vCGG 的形式化定義中繼承了CGG 的標尺集概念.類似于地圖標尺,標尺集中的每一個正實數代表著主圖對產生式的坐標比例.標尺的引入,可以有效地減少產生式的數量,尤其是那些結構完全相同而互相之間坐標成比例關系的產生式.每個產生式集P中的產生式都可以通過坐標與標尺的相乘得到多個實際使用的產生式,因此,標尺集所包含正實數的數量對一個文法的實際表達能力有著重要的影響.

定義2.6.對于vCGG 的任意一個文法vcgg,其語言Γ(vcgg)是一個由空間語義圖組成的集合:

圖文法的語言是由初始圖經過推導操作生成的只含有終結點的圖的集合.對一個只含有終結點的圖進行歸約操作的過程,可以判斷該圖是否屬于相應文法所定義的語言.vCGG 的推導工作流生成的是一個包含空間語義配置的圖,而歸約工作流可以在判斷給定圖的結構語法的合法性的同時,分析該圖的空間語義模型.

3 與已有文法的對比

本節對新構建的vCGG 框架與幾種具有代表性的框架SGG、SG、CGG 進行對比,其中,SGG 對空間語義采用定性描述,SG 根據文法定義的定量空間關系繪制圖形,CGG 使用離散坐標和連續坐標為空間語義提供基于不同粒度的配置.為了獲得全面而系統的比較結論,本節從形式化框架、文法表達能力、分析效率、以及文法應用這4 個維度對這幾種框架進行對比分析.

3.1 形式化框架

直觀性是衡量一個圖文法形式框架的關鍵特性之一,而上下文深度是評價文法框架直觀性的一個重要依據.上下文深度是指產生式圖中內部結點到上下文結點的最短路徑長度,具體值等于最短路徑中結點(不包含起始結點)和邊數量之和的二分之一.上下文深度大于等于1 的文法稱為顯式文法,而小于1 的文法稱為隱式文法.一般而言,顯式文法的直觀性高于隱式文法,而顯式文法的不足在于上下文結點描述的復雜性,在很多應用場景下較難使用有限的上下文結點描述所有可能出現的上下文信息.例如:LGG 使用通配符描述上下文信息,當通配符數量較大時,產生式構造變得過于復雜而難以設計.對幾種框架的上下文深度進行對比,如圖9 所示:SGG 將上下文信息以頂點形式內嵌在結點的雙層結構中,上下文深度為0;CGG 繼承了EGG 的懸邊機制,采用懸邊表示上下文連接,因此上下文深度為0.5;SG 在形式上沒有對上下文信息進行描述,上下文深度為空;vCGG 在產生式中引入了虛結點,上下文深度為1,并且虛結點在圖柄查找過程中不需要匹配其標號語義信息,因此不需要考慮虛結點除空間坐標之外的語義信息,相比LGG 具有更高的抽象性,產生式結構也更為簡潔而易于設計.此外,與前身CGG 相比,由于不再需要定義懸邊圖作為圖柄,vCGG 中圖的形式與定義更加符合圖論的規范標準.

Fig.9 Comparison between the productions of SGG,SG,CGG and vCGG圖9 SGG、SG、CGG、vCGG 產生式比較

形式化框架比較的另一個重點是子圖嵌入問題的解決方法,大致可以分為兩種:一種是使用嵌入規則進行圖轉換操作,具體方法是在主圖中首先刪除圖柄,之后根據嵌入規則將產生式圖嵌入主圖中;另一種方法使用結點粘合的方式,首先在主圖中刪除圖柄中除了與上下文結點匹配的結點之外的部分,再根據產生式兩端上下文結點的雙射關系進行結點粘合.總體而言:嵌入規則方法的形式上更加靈活,例如,用戶可以通過修改嵌入規則改變嵌入前邊的方向;粘合方法的規范性更好,可以確保文法操作中不會出現懸邊.相比之下,SG、SGG、CGG都是使用嵌入規則的方式進行子圖嵌入操作,而vCGG 采用粘合方式將作為上下文結點的虛結點和其對應結點進行粘合并去除虛標號,從而得到合法的新主圖.

3.2 文法表達能力

圖文法形式框架的表達能力指的是文法能夠描述圖語言的范圍,如何增強圖文法的表達能力,是該領域中的一個重要研究話題.與CGG 相比,對于圖語言LCF問題,由于引入了虛結點機制,vCGG 可以將第1.2 節中圖3的結點“fork”,“join”放入產生式中作為虛結點,直觀而簡潔地描述所有形如Lcf圖語言的多分支結構圖.從空間語義配置的全面性上對幾種框架進行對比,vCGG 對圖語言空間語義的描述更加全面.vCGG 在產生式中引入了虛結點作為上下文結點,虛結點在圖柄查找時不需考慮標號語義,匹配的是虛結點與實結點之間的語法結構以及空間語義關系,因此,vCGG 不僅可以描述產生式非公共子圖(不包含上下文結點的部分)的空間語義模型,也可以通過上下文結點的空間語義描述非公共子圖與主圖之間的坐標方位關系.與之對比,SG、SGG 與CGG 的產生式只能描述非公共子圖內部空間語義模型,缺乏對圖柄與主圖之間空間語義關系的描述能力,因此,空間語義配置的全面性不如vCGG.

3.3 分析效率

在文法分析效率方面,由于圖語言結構的二維非線性特點,文法分析過程中容易發生大量的回溯,造成了分析算法的最壞時間開銷通常為指數級.繼承自RGG、SGG 可以使用一個時間開銷為多項式級的分析算法—— SFPA 算法(selection-free parsing algorithm)[15].然而,SFPA 算法對產生式提出了約束較高的選擇無關條件作為歸約前提,導致SFPA 的通用性有所不足.由于歸約中回溯的不可避免性,大多數圖文法分析算法的設計目標是盡可能地降低圖柄查找過程的時間開銷.假設n是主圖的結點數量,m是產生式右圖的結點數量,n與m代表了主圖與產生式的規模,圖文法的圖柄查找時間開銷的時間復雜度在通常情況下為O()m nA,即在規模為n的主圖能夠查找到規模為m的不同結點順序子圖的最多數量.引入了空間語義機制后,由于產生式以及主圖中的結點可以按照其空間拓撲關系進行排序,利用該順序指導子圖匹配過程可以有效縮小圖柄的查找空間,從而減少時間開銷.因此,SGG 與CGG 的圖柄查找算法時間開銷位于[13,18]量級,將傳統圖柄查找過程的排列問題轉變成了典型的組合問題.繼承自CGG、vCGG 可以使用CGG 的圖柄查找算法,通過對結點排序而縮小圖柄的搜索空間,并且由于圖柄查找過程中不需要考慮懸邊的映射問題,vCGG 分析算法的實際時間開銷小于CGG.

圖文法分析性能的評價不僅體現在其時間開銷上,對非法語義關系與語法結構作出判斷的及時性也是評價的一個重要依據.與SG、SGG、CGG 相比,vCGG 產生式增加了上下文與產生式非公共子圖之間的空間關系約束,因此在分析過程中可以更早地發現錯誤,即時停機從而減少無效歸約.例如,圖10(a)是一個任意給定的主圖,不滿足圖10(b)、圖10(c)中產生式對圖形元素的空間語義約束.在歸約時,圖10(b)中CGG 產生式需要根據產生式p1,p2 對主圖進行兩次歸約才可以判定出該語義錯誤,而vCGG 產生式只需要圖10(c)中的一個產生式進行一步歸約便可判斷出其空間語義關系的非法性,在一定程度上減少了無效歸約的數量.

Fig.10 Detection of invalid host graph in CGG and vCGG圖10 CGG 與vCGG 對不合法主圖的檢測

3.4 文法應用

通過上述對比,vCGG 不僅可以描述產生式圖內部的空間語義模型,也可以將虛結點作為上下文結點直觀地描述產生式圖內部與主圖的坐標方位關系,提供了相對更全面的空間語義配置能力.因此,在空間圖文法的實際應用中,vCGG 可以處理一部分SG、SGG 與CGG 較難應對的實際應用問題.以圖模型布局需求為例,圖11是一個簡單的程序流程圖,其布局要求為:結點按從左到右的順序排列,每一個標號為“if”或“while”的結點需位于前一結點(設為n)的正下方,而標號為“Y-branch”或“endwhile”的結點需位于結點n的正右方.基于虛結點對上下文空間語義的顯式配置,使用vCGG 產生式可以較為容易地實現該布局要求.圖12 是一組用于繪制流程圖的vCGG 產生式.而使用該組產生式進行推導操作即可繪制出滿足上述布局要求的程序流程圖,如圖13 所示.

Fig.12 A set of vCGG productions for the programming flowchart圖12 描述程序流程圖的一組vCGG 產生式

Fig.13 Derivation of the programming flowchart圖13 上述程序流程圖的推導過程

相比之下,SG、SGG 與CGG 只能配置產生式圖內部的空間語義模型而缺乏對產生式與上下文之間的空間語義關系的描述.在面對上述需求時,最直接的方法是將vCGG 產生式中的虛結點(即上下文結點)引入產生式中作為普通實結點.例如,圖14 是一個滿足上述關于“if”結點布局要求的CGG 產生式.然而,該方法存在著較大的弊端:首先,將虛結點引入產生式作為普通實結點需要窮舉該結點允許接受的標號(如“statement”“endif”),而每種標號都對應著一個產生式,造成了產生式規模與數量的增長,尤其在需要引入多個虛結點作為實結點時,產生式的數量隨之呈指數增長;其次,實結點的增加在一定程度上影響了產生式圖作為一個圖形單元的邏輯獨立性,例如,圖14 中產生式中出現了不屬于“if”選擇結構的實結點“statement”;最后,在產生式中引入普通實結點還需考慮它們的上下文信息,進一步增加了產生式的規模與數量,也使產生式的抽象程度有所下降.

Fig.14 CGG production under the layout requirements圖14 滿足布局需求的一個CGG 產生式

SG、SGG 與CGG 配置產生式與上下文之間空間語義關系的另一種方法是:根據圖柄結點在主圖中與余圖的坐標關系,間接地設計嵌入圖結點的坐標信息.圖15 是根據這種間接配置方法設計的CGG 產生式,其設計過程為:首先計算出產生式左圖結點“stat”的圖柄與主圖中上下文的坐標差,再根據產生式右圖結點“if”與左圖結點之間的坐標關系分配滿足布局要求的“if”結點坐標.然而,由于缺少產生式與上下文的空間關系的顯式描述,這種間接配置方法的直觀性有所不足,增加了設計人員繪制產生式的難度,尤其在那些坐標計算較為復雜的應用場景下.例如,部分圖模型布局算法要求相鄰結點之間需保持一個合適的距離,例如力引導布局算法[22]、Fruchterman-Reingold 算法[23]以及Kamada-Kawai 算法[24].圖16 描述了一個要求相鄰結點距離不小于2 的布局需求,其中,圖轉換后與上下文結點“a”,“b”相鄰的結點由結點“d”轉變為新增結點“c”.

Fig.15 Indirect specification of the spatial relationship between production and context圖15 上下文與產生式之間空間關系的間接配置

Fig.16 Deficiency of the indirect specification of spatial semantics in intuitiveness圖16 間接空間語義配置在直觀性上的缺陷

以CGG 為例,由于產生式中缺少顯式的上下文結點“a”和“b”,導致在產生式設計階段結點“c”坐標的計算復雜化且易出錯,也在一定程度上增加了產生式設計人員學習曲線的陡峭程度,不利于布局方法的推廣應用.

4 結論與展望

針對空間圖文法形式框架存在的問題,本文對前期工作中構建的坐標圖文法CGG 進行改進,通過引入虛結點描述產生式與主圖之間的語法結構與空間語義關系,并構建了一個新的空間圖文法形式框架vCGG 與幾種典型空間圖文法形式框架進行對比分析,vCGG 具有以下幾個優點.

(1) 在產生式中引入虛結點作為上下文結點,上下文信息得到了顯式的描述,文法具有更好的直觀性;

(2) 采用粘合的方式進行圖轉換操作,有效防止了轉換過程中出現懸邊,操作的規范性得以保證;

(3) 通過虛結點描述上下文與產生式之間的空間語義關系,在保留上下文抽象性的同時,使文法具有更全面的空間語義配置性能;

(4) 使用虛結點代替懸邊描述上下文,在增強了文法表達能力的同時,避免了CGG 中的懸邊映射問題;

(5) 在歸約的過程中,能夠通過較少的產生式更早地發現語法與語義錯誤并及時停機,減少了無效歸約的數量.

在今后的研究中,在圖文法理論研究方面,我們將進一步改善空間圖文法形式框架,嘗試利用圖形元素之間的空間拓撲關系進一步縮小圖柄搜索空間,減小分析算法的時間開銷,使文法的實用性更強.在圖文法應用方面,我們考慮將圖形元素的空間特征作為關聯屬性,為產生式關聯語義動作或條件謂詞作為屬性文法,在圖轉換過程中加入語法制導翻譯,嘗試將圖文法應用在建筑外觀建模、工業設計與驗證等領域中,并開發一個空間圖文法系統平臺,為文法操作以及相關應用的落地提供支撐.

References:

[1] Shi Z,Zeng XQ.Bidirectional transformation between BPMN and BPEL with graph grammar.Computers and Electrical Engineering,2016,51:304-319.

[2] Hibshman J,Sikdar S,Weninger T.Towards interpretable graph modeling with vertex replacement grammars.In: Proc.of the Int’l Conf.on Big Data.2019.372-376.

[3] Li C,Huang L,Chen L.Breeze graph grammar: A graph grammar approach for modeling the software architecture of big data—Oriented software systems.Software Practice & Experience,2015,45(8):1023-1050.

[4] Duarte M,Ribeiro L.Graph grammar extraction from source code.In: Proc.of the Brazilian Symp.on Formal Methods.2017.52-69.

[5] Miyadera Y,Murakami C,Anada K,et al.Attribute graph grammar method for research information collection and sharing.In: Proc.of the Int’l Conf.on Digital Information Management.2016.235-242.

[6] Chen Q,Shi D,Feng G,et al.On-line handwritten flowchart recognition based on logical structure and graph grammar.In: Proc.of the Int’l Conf.on Information Science & Technology.2015.424-429.

[7] Park S,Nie X,Zhu SC.Attribute and-or grammar for joint parsing of human pose,parts and attributes.IEEE Trans.on Pattern Analysis and Machine Intelligence,2017,1555-1569.

[8] Julcaaguilar F,Mouchère H,Viardgaudin C,et al.Top-down online handwritten mathematical expression parsing with graph grammar.In: Proc.of the BeroAmerican Congress on Pattern Recognition.2015.444-451.

[9] Stiny G,Gips J.Shape grammars and the generative specification of painting and sculpture.Proc.of the Workshop on Generalisation & Multiple Representation Leicester,1971,71:1460-1465.

[10] Stiny G.Pictorial and formal aspects of shape and shape grammars and aesthetic systems.Los Angeles: University of California,1975.

[11] Mamoli M.A shape grammar for the building-type definition of the ancient Greek and Roman library and the evaluation of library plans.In: Proc.of the Artificial Intelligence for Engineering Design Analysis and Manufacturing.2020.1-16.

[12] Li YN,Zhang K,Li DJ.Rule-based automatic generation of logo designs.Leonardo,2017,50(2):177-181.

[13] Kong J,Zhang K,Zeng XQ.Spatial graph grammars for graphical user interfaces.ACM Trans.on Computer-Human Interaction,2006,13(2):268-307.

[14] Kong J,Zhang K.Parsing spatial graph grammars.In: Proc.of the IEEE Symp.on Visual Languages & Human Centric Computing.2004.99-101.

[15] Zhang DQ,Zhang K,Cao J.A context-sensitive graph grammar formalism for the specification of visual languages.The Computer Journal,2001,44(3):186-200.

[16] Kong J,Barkol O,Bergman R,et al.Web interface interpretation using graph grammars.IEEE Trans.on Systems,Man,and Cybernetics—Part C: Applications and Reviews,2012,42(4):590-602.

[17] Roudaki A,Kong J,Zhang K.Specification and discovery of web patterns: A graph grammar approach.Information Sciences,2016,328:528-545.

[18] Liu YF,Zeng XQ,Zhang K,Zou Y.Coordinate graph grammar for the specification of spatial graphs (online publication).The Computer Journal,2020.

[19] Liu YF,Zeng XQ,Zhang K.Quantitative spatial semantics in a graph grammar formalism.In: Proc.of the Int’l Workshop on Interactive and Spatial Computing.Dallas: ACM,2018.1-7.

[20] Zeng XQ,Han XQ,Zou Y.An edge-based context-sensitive graph grammar formalism.Ruan Jian Xue Bao/Journal of Software,2008,19(8):1893-1901 (in Chinese with English abstract).http://www.jos.org.cn/jos/article/abstract/20080804?st=article_issue [doi: 10.3724/SP.J.1001.2008.01893]

[21] Zou Y,Lü J,Cao C,et al.On the expressiveness of context-sensitive graph grammars.Ruan Jian Xue Bao/ Journal of Software,2012,23(7):1635-1655 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4085.htm [doi: 10.3724/SP.J.1001.2012.04085]

[22] Eades PA.A heuristic for graph drawing.Congressus Numerantium,1984,42(42):149-160.

[23] Fruchterman TMJ,Reingold EM.Graph drawing by force-directed placement.Software: Practice and Experience,1991,21(11): 1129-1164.

[24] Kamada T,Kawai S.An algorithm for drawing general undirected graphs.Information Processing Letters,1989,31(1):7-15.

附中文參考文獻:

[20] 曾曉勤,韓秀清,鄒陽.一種基于邊的上下文相關圖文法形式化框架.軟件學報,2008,19(8):1893-1901.http://www.jos.org.cn/jos/ article/abstract/20080804?st=article_issue [doi: 10.3724/SP.J.1001.2008.01893]

[21] 鄒陽,呂建,曹春,等.上下文相關圖文法的表達能力分析.軟件學報,2012,23(7):1635-1655.http://www.jos.org.cn/1000-9825/4085.htm [doi: 10.3724/SP.J.1001.2012.04085]