[發(fā)明專利]一種從EGG圖文法到RGG圖文法的轉(zhuǎn)換方法

無效

• 申請?zhí)枺?/td>: 201210443734.8
• 申請日: 2012-11-08
• 公開（公告）號: CN102929639A
• 公開（公告）日: 2013-02-13
• 發(fā)明（設(shè)計(jì)）人: 鄒陽;曾曉勤
• 申請（專利權(quán)）人: 河海大學(xué)
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 夏雪

1.一種從EGG圖文法到RGG圖文法的轉(zhuǎn)換方法，其特征在于，首先將EGG圖文法轉(zhuǎn)換為僅在圖柄定義上存在差異的RGG變種形式VRGG：(1)構(gòu)建從EGG產(chǎn)生式結(jié)點(diǎn)上的懸邊到VRGG產(chǎn)生式結(jié)點(diǎn)中的頂點(diǎn)的一一對應(yīng)關(guān)系，并將產(chǎn)生式結(jié)點(diǎn)上懸邊轉(zhuǎn)換成結(jié)點(diǎn)中的頂點(diǎn)，(2)對轉(zhuǎn)換后產(chǎn)生式中具有同一標(biāo)號的結(jié)點(diǎn)構(gòu)建它們的極大頂點(diǎn)集，并將此集合統(tǒng)一分配給該結(jié)點(diǎn)在產(chǎn)生式集合中的所有出現(xiàn)，同時(shí)相應(yīng)地調(diào)整與設(shè)置結(jié)點(diǎn)中的頂點(diǎn)標(biāo)號；然后，根據(jù)所得VRGG產(chǎn)生式集中的結(jié)點(diǎn)形式將EGG的初始圖轉(zhuǎn)換成VRGG形式的初始圖；最后，將VRGG圖文法的產(chǎn)生式集轉(zhuǎn)換為對應(yīng)的RGG產(chǎn)生式集。

2.根據(jù)權(quán)利要求1所述一種從EGG圖文法到RGG圖文法的轉(zhuǎn)換方法，其特征在于，具體包含以下步驟：

1)輸入一個(gè)EGG文法實(shí)例(A₁,P₁)；

2)置圖產(chǎn)生式集合P₂為空；

3)對于P₁中的每一個(gè)產(chǎn)生式p=(L,R),對p進(jìn)行形式變換，具體為：

3.1)對于p的左圖L懸邊集中的任一懸邊e以及右圖R懸邊集中與之對應(yīng)的懸邊e′，分別在L中和e相連的結(jié)點(diǎn)和在R中與e′相連的結(jié)點(diǎn)上各添加一個(gè)頂點(diǎn)v和v′，并設(shè)置頂點(diǎn)的相關(guān)特性；

3.2)從產(chǎn)生式p中刪除左圖和右圖中的懸邊集合；

3.3)將p添加到P₂中；

4)對于P₂中的每一個(gè)結(jié)點(diǎn)n，根據(jù)結(jié)點(diǎn)n在P₂中的所有出現(xiàn)，分別計(jì)算n中連接入邊和出邊的頂點(diǎn)集，具體為：

4.1)連接入邊頂點(diǎn)集c_in(n)基數(shù)為n在P₂的所有出現(xiàn)中入邊頂點(diǎn)數(shù)的最大值；

4.2)連接出邊頂點(diǎn)集c_out(n)基數(shù)為n在P₂的所有出現(xiàn)中出邊頂點(diǎn)數(shù)的最大值；

5)對于P₂中的每一個(gè)結(jié)點(diǎn)n，統(tǒng)一分配n的頂點(diǎn)集合，具體為：

5.1)對于結(jié)點(diǎn)n在P₂中的每一次出現(xiàn)，分別添加連接入邊頂點(diǎn)和連接出邊頂點(diǎn)使之成為為c_in(n)和c_out(n)，并相應(yīng)地調(diào)整結(jié)點(diǎn)中頂點(diǎn)與邊的連接關(guān)系；

6)依據(jù)P₂中結(jié)點(diǎn)的結(jié)構(gòu)變換A₁中對應(yīng)結(jié)點(diǎn)，并相應(yīng)地調(diào)整頂點(diǎn)與邊之間的連接關(guān)系得到A₂；

7)將已生成的VRGG文法實(shí)例(A₂,P₂)轉(zhuǎn)換成相應(yīng)的RGG文法實(shí)例：在定義句柄時(shí)允許與句柄候選子圖中頂點(diǎn)相連的邊的數(shù)目不為1，從而將RGG文法的句柄定義作為文法實(shí)例(A₂,P₂)的句柄定義；

8)輸出一個(gè)相應(yīng)的RGG文法實(shí)例(A₂,P₂)。

3.根據(jù)權(quán)利要求2所述一種從EGG圖文法到RGG圖文法的轉(zhuǎn)換方法，其特征在于，所述步驟3.1具體包括以下步驟：

3.1.1)如果懸邊e的起點(diǎn)n為p的左圖L的結(jié)點(diǎn)，則在產(chǎn)生式兩端分別添加頂點(diǎn)并進(jìn)行屬性設(shè)置，否則轉(zhuǎn)3.1.2；上述產(chǎn)生式變換具體為：

3.1.1.1)在L的結(jié)點(diǎn)n上添加一個(gè)頂點(diǎn)v；

3.1.1.2)設(shè)置頂點(diǎn)v上邊的連接方向?yàn)閛ut；

3.1.1.3)設(shè)p的右圖R中與e標(biāo)號相同的邊e′的起點(diǎn)為n′，在R的結(jié)點(diǎn)n′上添加一個(gè)頂點(diǎn)v′；

3.1.1.4)設(shè)置頂點(diǎn)v′上邊的連接方向?yàn)閛ut；

3.1.2)如果懸邊e的終點(diǎn)n為p的右圖R的結(jié)點(diǎn)，則在產(chǎn)生式兩端分別添加頂點(diǎn)并進(jìn)行屬性設(shè)置，具體為：

3.1.2.1)在L的結(jié)點(diǎn)n上添加一個(gè)頂點(diǎn)v；

3.1.2.2)設(shè)置頂點(diǎn)v上邊的連接方向?yàn)閕n；

3.1.2.3)設(shè)p的右圖R中與e標(biāo)號相同的邊e′的終點(diǎn)為n′，在R的結(jié)點(diǎn)n′上添加一個(gè)頂點(diǎn)v′；

3.1.2.4)設(shè)置頂點(diǎn)v′上邊的連接方向?yàn)閕n；

3.1.3)設(shè)置結(jié)點(diǎn)n與n′中新添頂點(diǎn)的標(biāo)號，具體為：

3.1.3.1)設(shè)產(chǎn)生式p中的懸邊集標(biāo)記函數(shù)為M₁，則置頂點(diǎn)v的標(biāo)號為M₁(e)；

3.1.3.2)置頂點(diǎn)v′的標(biāo)號為M₁(e)。

所述步驟5.1具體包括以下步驟：

5.1.1)設(shè)n在P₂的任一次出現(xiàn)為nⁱ，令nⁱ中的頂點(diǎn)數(shù)為d，其中連接入邊的頂點(diǎn)數(shù)和連接出邊的頂點(diǎn)數(shù)分別為d₁和d₂，對應(yīng)的頂點(diǎn)標(biāo)號集合分別為Lb₁和Lb₂；

5.1.2)在nⁱ中添加c_in(n)-d₁個(gè)連接入邊的頂點(diǎn)和c_out(n)-d₂個(gè)連接出邊的頂點(diǎn)，得到新nⁱ結(jié)點(diǎn)；

5.1.3)建立nⁱ與新nⁱ頂點(diǎn)標(biāo)號之間的一一映射f，具體為：

5.1.3.1)將Lb₁中的數(shù)字按升序映射到區(qū)間[1,d₁]；

5.1.3.2)將Lb₂中的數(shù)字按升序映射到區(qū)間[c_in(n)+1,c_in(n)+d₂]；

5.1.4)在新nⁱ中對所有頂點(diǎn)統(tǒng)一分配標(biāo)號，具體為：

5.1.4.1)應(yīng)用已構(gòu)造的映射f為新nⁱ中已標(biāo)記頂點(diǎn)重新賦予標(biāo)號：將連接入邊頂點(diǎn)v的標(biāo)號mark(v)從Lb₁中的某個(gè)值替換成1~d₁中的f(mark(v))，將連接出邊頂點(diǎn)v′的標(biāo)號mark(v′)從Lb₂中的某個(gè)值替換成c_in(n)+1~c_in(n)+d₂中的f(mark(v′))；

5.1.4.2)為新nⁱ中未標(biāo)記頂點(diǎn)賦予標(biāo)號：將d₁+1~c_in(n)作為頂點(diǎn)標(biāo)號分別賦予未標(biāo)記的連接入邊頂點(diǎn)，將c_in(n)+d₂+1~c_in(n)+c_out(n)作為頂點(diǎn)標(biāo)號分別賦予未標(biāo)記的連接出邊頂點(diǎn)；

5.1.5)調(diào)整與nⁱ中任一頂點(diǎn)v相連的邊，使之在新nⁱ中與標(biāo)號為f(mark(v))的頂點(diǎn)相連。