苗偉華，危 輝

復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院/軟件學(xué)院 認(rèn)知算法模型實(shí)驗(yàn)室，上海 200438

對(duì)于一張有向圖G=(V,E)，其中u,v∈V?？蛇_(dá)性查詢(xún)是詢(xún)問(wèn)是否存在一條路徑使得u點(diǎn)可以到達(dá)v點(diǎn)。可達(dá)性查詢(xún)是圖論中的基礎(chǔ)操作，廣泛應(yīng)用于多種場(chǎng)景[1-3]，如XML數(shù)據(jù)庫(kù)、社交網(wǎng)絡(luò)分析、物流運(yùn)輸、生物信息學(xué)等。比如檢測(cè)兩種蛋白質(zhì)之間是否存在生物學(xué)通路等。但隨著人類(lèi)社會(huì)的發(fā)展以及大數(shù)據(jù)時(shí)代的來(lái)臨，圖的規(guī)模越來(lái)越大。傳統(tǒng)算法如傳遞閉包、深度優(yōu)先搜索等因?yàn)榫哂袠O高的時(shí)間復(fù)雜度或空間復(fù)雜度而變得不再適用。

一種有效的策略是針對(duì)有向圖的不同結(jié)構(gòu)特點(diǎn)，設(shè)計(jì)不同種類(lèi)的算法[4-7]。GRKPL（graph reachability indexing via key points labeling）算法的提出是為了解決稀疏圖上的可達(dá)性問(wèn)題。現(xiàn)實(shí)生活中很多網(wǎng)絡(luò)都是稀疏的，如電力網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等。稀疏圖通常具有的特點(diǎn)是邊集規(guī)模和點(diǎn)集規(guī)模同階。因此可以將稀疏圖看作由若干有向生成樹(shù)與少量非樹(shù)邊共同組成的。那么稀疏圖上的可達(dá)性問(wèn)題就可以被拆分為兩部分：第一部分是生成樹(shù)上的可達(dá)性問(wèn)題；第二部分是引入非樹(shù)邊后增加了哪些新的連通點(diǎn)對(duì)。對(duì)于第一部分，已經(jīng)有區(qū)間標(biāo)記法[8]可以在線(xiàn)性時(shí)間內(nèi)構(gòu)建標(biāo)記，并在常數(shù)時(shí)間內(nèi)回答詢(xún)問(wèn)，該算法會(huì)在2.1節(jié)詳細(xì)介紹。為了能夠高效解決第二部分帶來(lái)的可達(dá)性問(wèn)題，提出了GRKPL算法，即基于關(guān)鍵點(diǎn)標(biāo)記的圖上可達(dá)性查詢(xún)算法。GRKPL構(gòu)建了一個(gè)規(guī)模與原圖中非樹(shù)邊數(shù)量同階的關(guān)鍵點(diǎn)集，通過(guò)將原圖中的可達(dá)性查詢(xún)轉(zhuǎn)化為關(guān)鍵點(diǎn)集中點(diǎn)對(duì)的可達(dá)性的查詢(xún)，從而解決了第二部分帶來(lái)的問(wèn)題。為了快速回答關(guān)鍵點(diǎn)集中任意兩點(diǎn)之間是否可達(dá)，需要預(yù)處理關(guān)鍵點(diǎn)集的閉包。為了加速這一過(guò)程，構(gòu)建了新圖G′=(V′,E′)，其中V′為關(guān)鍵點(diǎn)集。并從數(shù)學(xué)上證明了V′與E′的規(guī)模都是與非樹(shù)邊數(shù)量同階的。設(shè)t為原圖G中非樹(shù)邊的數(shù)量，，di表示i點(diǎn)的入度。則關(guān)鍵點(diǎn)集閉包傳遞的時(shí)間復(fù)雜度可以表示為O(|V′||E′|)=O(t2)。通過(guò)使用位壓縮技術(shù)，將標(biāo)記預(yù)處理的時(shí)間復(fù)雜度降至O(n+m+t2/w)，其中n=|V|，m=|E|，w表示處理機(jī)字長(zhǎng)。標(biāo)記存儲(chǔ)的空間復(fù)雜度降至O(n+t2/b)，其中b為存儲(chǔ)標(biāo)記類(lèi)型的比特?cái)?shù)。查詢(xún)回答的時(shí)間復(fù)雜度為O(1)。最后在14 個(gè)現(xiàn)實(shí)數(shù)據(jù)集[9]上進(jìn)行了對(duì)比實(shí)驗(yàn)。GRKPL算法在中小規(guī)模數(shù)據(jù)集上表現(xiàn)優(yōu)異，在查詢(xún)處理方面，所用時(shí)間相對(duì)于其他算法平均減少49.8%，空間占用方面平均減少65.1%。預(yù)處理方面雖然表現(xiàn)不如搜索類(lèi)算法，但相比標(biāo)記類(lèi)算法中表現(xiàn)較好的TOL（total order labeling）算法用時(shí)減少了17.4%。

1 相關(guān)工作

目前常見(jiàn)的可達(dá)性算法大致可以分為兩類(lèi)：標(biāo)記法與搜索法。標(biāo)記法會(huì)預(yù)先對(duì)圖進(jìn)行處理，構(gòu)建并存儲(chǔ)與可達(dá)性相關(guān)的標(biāo)記。在回答查詢(xún)時(shí)，便可以直接通過(guò)標(biāo)記快速回答。如Floyd[10]直接預(yù)處理圖中任意兩點(diǎn)間的可達(dá)性。鏈剖分[11]將有向圖分割成若干互不相交的鏈，預(yù)處理每個(gè)點(diǎn)能夠達(dá)到每條鏈中的最小編號(hào)。樹(shù)剖分[8]首先會(huì)找到有向圖的一棵生成樹(shù)，然后對(duì)其進(jìn)行區(qū)間標(biāo)記。因?yàn)橛蟹菢?shù)邊的存在，每個(gè)點(diǎn)可能會(huì)有多個(gè)區(qū)間標(biāo)記，那么在回答詢(xún)問(wèn)時(shí)就需要遍歷每一個(gè)標(biāo)記。Dual-Labeling[7]將可達(dá)性詢(xún)問(wèn)轉(zhuǎn)化為二維平面上線(xiàn)段數(shù)量的查詢(xún)。Path-Tree[12]將圖劃分為多條互不相交的路徑，并將每條路徑抽象成一個(gè)點(diǎn)，從而得到新圖，最后通過(guò)深度優(yōu)先搜索的方式對(duì)新圖進(jìn)行標(biāo)記并處理相關(guān)標(biāo)記。相關(guān)算法還有很多[13-19]。標(biāo)記類(lèi)方法的特點(diǎn)是預(yù)處理的過(guò)程通常需要花費(fèi)大量的時(shí)間與空間，但查詢(xún)的復(fù)雜度通常較低，大多數(shù)情況下均為常數(shù)級(jí)別。

搜索法則是另一種極端，通常具有較低的預(yù)處理時(shí)間復(fù)雜度與空間復(fù)雜度，但查詢(xún)的時(shí)間復(fù)雜度會(huì)相對(duì)較高。大部分的搜索類(lèi)算法都會(huì)結(jié)合一些標(biāo)記以達(dá)到剪枝的目的，從而加快搜索過(guò)程。如GRAIL（graph reachability indexing via randomized interval labeling）[20]通過(guò)對(duì)圖進(jìn)行多次隨機(jī)遍歷，使得每個(gè)點(diǎn)都擁有多個(gè)區(qū)間標(biāo)記。以此實(shí)現(xiàn)在搜索過(guò)程中快速處理不可達(dá)詢(xún)問(wèn)的目的。GRIPP（graph indexing based on pre-and post-order numbering）[21]在遍歷圖的同時(shí)維護(hù)了一張實(shí)例表，借助實(shí)例表可以在搜索過(guò)程中完成對(duì)查詢(xún)的轉(zhuǎn)換。IP（independent permutation）[22]首次引入了隨機(jī)性，使用k-min-wise獨(dú)立排列處理可達(dá)性查詢(xún)。BFL（Bloom filter labeling）[23]提出了基于Bloom filter的一種新型標(biāo)記方式，并證明了其誤報(bào)率是有界的。相關(guān)算法還有很多[24-27]。由此可見(jiàn)，不同種類(lèi)的算法本質(zhì)上都是對(duì)空間復(fù)雜度與時(shí)間復(fù)雜度的一種權(quán)衡與取舍。表1 展示了一些可達(dá)性算法的時(shí)間與空間復(fù)雜度[22-23]，其中n表示圖中頂點(diǎn)數(shù)量，m表示邊數(shù)。

表1 可達(dá)性算法復(fù)雜度Table 1 Reachability algorithm complexity

為了方便說(shuō)明，之后所提到的有向圖都默認(rèn)為有向無(wú)環(huán)圖，因?yàn)樗械挠邢驁D都可以通過(guò)Tarjan算法[28]進(jìn)行強(qiáng)連通分量縮點(diǎn)后變?yōu)橛邢驘o(wú)環(huán)圖。

2 GRKPL算法

GRKPL 即基于關(guān)鍵點(diǎn)標(biāo)記的可達(dá)性算法，通過(guò)構(gòu)建關(guān)鍵點(diǎn)集，將原圖中的查詢(xún)變換成關(guān)鍵點(diǎn)集上的查詢(xún)，從而降低算法的時(shí)間和空間復(fù)雜度。設(shè)圖G=(V,E)為有向無(wú)環(huán)圖，其中n=|V|，m=|E|。T=(VT,ET)為圖G的一棵有向生成樹(shù)。對(duì)于圖G來(lái)說(shuō)，若存在多個(gè)入度為0的頂點(diǎn)，那么一棵樹(shù)無(wú)法完全覆蓋圖G中所有的頂點(diǎn)，但是可以通過(guò)建立一個(gè)虛擬的根節(jié)點(diǎn)vroot，使得vroot向圖G中所有入度為0 的點(diǎn)建邊。這樣以vroot為根的生成樹(shù)就可以完全覆蓋圖G中的所有節(jié)點(diǎn)。對(duì)于有向邊e，如果e∈E∧e∈ET，則稱(chēng)有向邊e為樹(shù)邊，否則稱(chēng)為非樹(shù)邊。設(shè)t為圖G中非樹(shù)邊的數(shù)量，則有式（1）：

其中，di表示i點(diǎn)的入度，其思想是樹(shù)上每個(gè)節(jié)點(diǎn)的入度至多為1，多余的入邊則為非樹(shù)邊。對(duì)于稀疏圖而言，往往有t<

2.1 區(qū)間標(biāo)記法

樹(shù)是有向無(wú)環(huán)圖的一種特殊情況，對(duì)于樹(shù)上任意兩點(diǎn)的可達(dá)性查詢(xún)有一個(gè)非常簡(jiǎn)單且高效的算法，稱(chēng)為區(qū)間標(biāo)記法[8]。只需要對(duì)樹(shù)進(jìn)行深度優(yōu)先搜索（前序遍歷），在第一次進(jìn)入節(jié)點(diǎn)u時(shí)記錄當(dāng)前的時(shí)間戳lu，在遍歷完u點(diǎn)的子樹(shù)后準(zhǔn)備回溯時(shí)，記錄當(dāng)前的時(shí)間戳ru。這樣對(duì)于樹(shù)中每一個(gè)節(jié)點(diǎn)u都有標(biāo)記[lu,ru)。在查詢(xún)兩點(diǎn)之間的可達(dá)性時(shí)，便可通過(guò)查詢(xún)兩點(diǎn)的區(qū)間標(biāo)記是否是包含關(guān)系來(lái)判斷，具體形式由式（2）給出：

如圖1所示，若要判斷v1是否能達(dá)到v5，只需查看進(jìn)入v5的時(shí)間是否在v1的區(qū)間標(biāo)記之中，即l5∈[l1,r1) 。又因?yàn)? ∈[0,6)，所以v1點(diǎn)可以到達(dá)v5點(diǎn)。通過(guò)此算法便可在O(n+m)的時(shí)間復(fù)雜度下預(yù)處理標(biāo)記，其中n為樹(shù)的節(jié)點(diǎn)數(shù)，m為樹(shù)的邊數(shù)。在O(1)的時(shí)間復(fù)雜度內(nèi)回答詢(xún)問(wèn)。

圖1 區(qū)間標(biāo)記后的樹(shù)Fig.1 Tree after interval labeling

因?yàn)橄∈鑸D可以看作以vroot為根的有向生成樹(shù)與少量非樹(shù)邊的組合，所以可以先找出稀疏圖的有向生成樹(shù)，然后對(duì)該生成樹(shù)進(jìn)行區(qū)間標(biāo)記。雖然稀疏圖中以vroot為根的生成樹(shù)并不唯一，但生成樹(shù)的形態(tài)對(duì)于算法復(fù)雜度的影響微乎其微。因?yàn)橛绊懰惴◤?fù)雜度的是圖中非樹(shù)邊的數(shù)量，而這個(gè)值與生成樹(shù)的形態(tài)無(wú)關(guān)。算法1 提供了一種在選取生成樹(shù)的同時(shí)進(jìn)行區(qū)間標(biāo)記的方法。

算法1尋找生成樹(shù)并進(jìn)行區(qū)間標(biāo)記

輸入：vroot表示虛根。

輸出：圖中所有節(jié)點(diǎn)的區(qū)間標(biāo)記(l,r)與生成樹(shù)。

參數(shù)說(shuō)明：dfn表示時(shí)間戳，G表示鄰接表，用于存圖。

2.2 查詢(xún)轉(zhuǎn)化

圖2 展示了對(duì)圖G進(jìn)行區(qū)間標(biāo)記后的結(jié)果。其中實(shí)線(xiàn)表示樹(shù)邊，虛線(xiàn)表示非樹(shù)邊。假設(shè)查詢(xún)(u,v)，即查詢(xún)u點(diǎn)是否可以到達(dá)v點(diǎn)。如果v點(diǎn)在u點(diǎn)的子樹(shù)內(nèi)，那么u點(diǎn)便可以?xún)H通過(guò)樹(shù)邊到達(dá)v點(diǎn)。不然u點(diǎn)必須要經(jīng)過(guò)若干樹(shù)邊和非樹(shù)邊才可以到達(dá)v點(diǎn)，或者是不可達(dá)。定義u點(diǎn)為覆蓋點(diǎn)，當(dāng)且僅當(dāng)u點(diǎn)的入邊或出邊中包含非樹(shù)邊。圖2 中的覆蓋點(diǎn)集合CG={v5,v6,v8,v11,v12}。若u點(diǎn)要經(jīng)過(guò)若干樹(shù)邊和非樹(shù)邊才可以到達(dá)v點(diǎn)，那么u點(diǎn)必然會(huì)先走到其子樹(shù)中的某個(gè)覆蓋點(diǎn)x，再?gòu)膞出發(fā)經(jīng)過(guò)若干非樹(shù)邊和樹(shù)邊到達(dá)某個(gè)覆蓋點(diǎn)y，最后從y點(diǎn)沿樹(shù)邊走到v點(diǎn)。這樣便可以把原始查詢(xún)(u,v)變?yōu)樾虏樵?xún)(x,y)。但并不是所有的查詢(xún)都可以轉(zhuǎn)化為覆蓋點(diǎn)之間的查詢(xún)。假如u點(diǎn)的子樹(shù)內(nèi)不包含覆蓋點(diǎn)，那么u點(diǎn)到v點(diǎn)的所有路徑中必然不會(huì)經(jīng)過(guò)任何一條非樹(shù)邊。同理，若v點(diǎn)的祖先內(nèi)不包含覆蓋點(diǎn)，那么同樣u點(diǎn)到v點(diǎn)的所有路徑中也不會(huì)經(jīng)過(guò)任何一條非樹(shù)邊。因此需要對(duì)這種情況進(jìn)行特殊判斷。

圖2 區(qū)間標(biāo)記后的圖GFig.2 Graph G after interval labeling

2.3 構(gòu)建關(guān)鍵點(diǎn)集

設(shè)Su表示u點(diǎn)子樹(shù)中的覆蓋點(diǎn)集，Pv表示v點(diǎn)祖先中的覆蓋點(diǎn)集。對(duì)于查詢(xún)(u,v)，如果v點(diǎn)不在u點(diǎn)的子樹(shù)中，那么需要枚舉Su中的點(diǎn)，檢查其是否能到達(dá)Pv中的任意一點(diǎn)。因?yàn)閨Su|和|Pv|的數(shù)量級(jí)都是O(t) 的，所以這種做法的時(shí)間復(fù)雜度會(huì)退化到O(t2)。但事實(shí)上可以通過(guò)兩步優(yōu)化，將查詢(xún)的復(fù)雜度降到O(1)。

優(yōu)化1設(shè)根節(jié)點(diǎn)的深度為0。Pv中深度較小的節(jié)點(diǎn)一定能夠沿樹(shù)邊達(dá)到深度大于或等于自身的節(jié)點(diǎn)。因此對(duì)于查詢(xún)(u,v)來(lái)說(shuō)，只需要檢查Su中是否存在一個(gè)節(jié)點(diǎn)，能夠到達(dá)Pv中深度最大的節(jié)點(diǎn)即可。這樣時(shí)間復(fù)雜度就可以降至O(t)。

優(yōu)化2當(dāng)|Su|>1 時(shí)，希望可以找到一個(gè)點(diǎn)x，滿(mǎn)足點(diǎn)x可以到達(dá)Su中任意一點(diǎn)。這個(gè)點(diǎn)x實(shí)際上就是Su中所有節(jié)點(diǎn)的公共祖先。不妨取x點(diǎn)為u點(diǎn)子樹(shù)內(nèi)所有覆蓋點(diǎn)的公共祖先中深度最大的祖先，即最近公共祖先（lowest common ancestor，LCA）[29]。那么原查詢(xún)(u,v)就可以轉(zhuǎn)化為新查詢(xún)(x,y)，其中y為Pv中深度最大的節(jié)點(diǎn)。因此只要預(yù)處理T中每個(gè)節(jié)點(diǎn)子樹(shù)內(nèi)所有覆蓋點(diǎn)的最近公共祖先，再結(jié)合優(yōu)化1，就可以做到在O(1)時(shí)間復(fù)雜度內(nèi)回答查詢(xún)。

設(shè)T中的覆蓋點(diǎn)集合為CT={a1,a2,…,am}，T中每個(gè)節(jié)點(diǎn)子樹(shù)內(nèi)所有覆蓋點(diǎn)的最近公共祖先為L(zhǎng)T={lca(Sv)|v∈[1,n]}。定義圖G的關(guān)鍵點(diǎn)集KG=CT?LT。綜上可知，除2.2 節(jié)中討論的特殊情況外，原圖中任意點(diǎn)對(duì)之間可達(dá)性的查詢(xún)均可轉(zhuǎn)化為關(guān)鍵點(diǎn)集中點(diǎn)對(duì)可達(dá)性的查詢(xún)。定理1與定理2將證明|KG|的數(shù)量級(jí)為O(t)。

由定理1 可知，設(shè)CT={a1,a2,…,am}表示T中所有覆蓋點(diǎn)，則有式（3）成立。因此不需要對(duì)T中每個(gè)節(jié)點(diǎn)都計(jì)算出其子樹(shù)內(nèi)所有覆蓋點(diǎn)的最近公共祖先，只需把所有覆蓋點(diǎn)兩兩之間的最近公共祖先求出即可。

證明定理2 等價(jià)于：對(duì)于i∈[2,r]，有?j∈[1,i),成立。當(dāng)r=2 時(shí)，有l(wèi)ca(a1,a2)=lca(b1,b2)，定理顯然成立。假設(shè)r=k時(shí)定理成立，當(dāng)r=k+1時(shí)，不妨假設(shè)存在u=lca(bt,bk+1),t∈[1,k)，且設(shè)dep(u)表示u點(diǎn)在生成樹(shù)中的深度，因?yàn)閎j是按照前序遍歷的順序排序后得到的，所以當(dāng)j

由定理2 可知，LT=Qvroot=Rvroot，因?yàn)閨Rvroot|的數(shù)量級(jí)為O(t)，所以L(fǎng)T的數(shù)量級(jí)也為O(t) 。又因?yàn)镵G=CT?LT，所以關(guān)鍵點(diǎn)集|KG|的數(shù)量級(jí)也為O(t)。圖3展示了G中的關(guān)鍵點(diǎn)集，其中CT={v5,v6,v8,v11,v12}，用斜線(xiàn)填充的節(jié)點(diǎn)表示。LT={v1,v2,v3,v7}，用實(shí)心節(jié)點(diǎn)表示。由于有向圖的生成樹(shù)并不唯一，對(duì)于不同形態(tài)的生成樹(shù)，其得到的關(guān)鍵點(diǎn)集也是不同的。但由定理2可知，|LT|

圖3 圖G 中的關(guān)鍵點(diǎn)集Fig.3 Set of key points in graph G

2.4 標(biāo)記預(yù)處理

GRKPL 算法的標(biāo)記由兩部分組成：第一部分是點(diǎn)u祖先中深度最大的關(guān)鍵點(diǎn)，記為pidu；第二部分是點(diǎn)u子樹(shù)中深度最小的關(guān)鍵點(diǎn)，記為sidu。因?yàn)殛P(guān)鍵點(diǎn)中已經(jīng)包含了所有覆蓋點(diǎn)兩兩之間的最近公共祖先，所以sidu必然是u點(diǎn)子樹(shù)內(nèi)所有覆蓋點(diǎn)的最近公共祖先。需要對(duì)圖G中所有節(jié)點(diǎn)都求出這兩部分標(biāo)記。對(duì)于第一部分標(biāo)記，可以用棧在深度優(yōu)先搜索的時(shí)候保留路徑上的關(guān)鍵點(diǎn)，對(duì)于當(dāng)前點(diǎn)來(lái)說(shuō)，若棧為空，則表示其祖先中不存在關(guān)鍵點(diǎn)，否則棧頂即為所求。在回溯的時(shí)候，如果當(dāng)前點(diǎn)是關(guān)鍵點(diǎn)，那么從棧中把它彈出。對(duì)于第二部分標(biāo)記，可以在深度優(yōu)先搜索的時(shí)候檢查當(dāng)前點(diǎn)u是否為關(guān)鍵點(diǎn)，如果是則從當(dāng)前點(diǎn)開(kāi)始沿著父親邊（樹(shù)邊）往回跳，一直跳到點(diǎn)v已經(jīng)被打上第二部分標(biāo)記或者跳到根為止。這回跳的過(guò)程中經(jīng)過(guò)的所有點(diǎn)的第二部分標(biāo)記都是點(diǎn)u。最終標(biāo)記效果由圖3 給出。算法偽代碼由算法2給出。

算法2構(gòu)建GRKPL標(biāo)記

輸入：vroot表示虛根。

輸出：圖中所有節(jié)點(diǎn)的(sid,pid)。

參數(shù)說(shuō)明：vis[u]表示點(diǎn)u是否訪(fǎng)問(wèn)過(guò)；stk表示棧；par[u]用來(lái)記錄點(diǎn)u在樹(shù)中的父親；G表示鄰接表，用于存圖；K(G)表示圖G中的關(guān)鍵點(diǎn)集。

2.5 閉包傳遞

為了加速關(guān)鍵點(diǎn)集中閉包的傳遞，需要將關(guān)鍵點(diǎn)集從原圖G中分離出來(lái)。圖4 展示了分離之后得到的新圖G′。為了防止G′中邊的規(guī)模退化到O(t2)，需要維持原本的樹(shù)形結(jié)構(gòu)。具體做法為在深度優(yōu)先搜索的過(guò)程中處理出每個(gè)點(diǎn)其祖先中深度最大的關(guān)鍵點(diǎn)，然后只需要連接這兩個(gè)點(diǎn)即可。這樣既不會(huì)破壞閉包，同時(shí)也將新圖中邊集的大小控制在了O(t)級(jí)別，因?yàn)槿コ菢?shù)邊后，每個(gè)點(diǎn)的入度都是1。因此邊集的數(shù)量級(jí)和點(diǎn)集的數(shù)量級(jí)是相同的。

圖4 分離后的新圖G′Fig.4 New graph G′ after separation

傳統(tǒng)Floyd-Warshal[10]算法傳遞閉包的時(shí)間復(fù)雜度是O(n3)，空間復(fù)雜度為O(n2)。但對(duì)于有向無(wú)環(huán)圖來(lái)說(shuō)，可以通過(guò)動(dòng)態(tài)規(guī)劃的方法進(jìn)行加速，使時(shí)間復(fù)雜度變?yōu)镺(nm)。具體做法是：首先設(shè)dp[u][v]這個(gè)二維數(shù)組存儲(chǔ)圖G中任意兩點(diǎn)之間的可達(dá)性，取值0或1。然后將圖G按逆拓?fù)湫蜻M(jìn)行排序后順序遍歷，若當(dāng)前節(jié)點(diǎn)為u，那么u點(diǎn)可以通過(guò)它的出邊到達(dá)它所有的后繼節(jié)點(diǎn)，即可以用所有后繼節(jié)點(diǎn)的狀態(tài)來(lái)更新當(dāng)前節(jié)點(diǎn)的狀態(tài)。又因?yàn)楸闅v的順序是逆拓?fù)湫颍@樣就保證了訪(fǎng)問(wèn)u點(diǎn)之前，u點(diǎn)所有可能可達(dá)的點(diǎn)已經(jīng)都訪(fǎng)問(wèn)過(guò)，從而保證了算法的正確性。具體更新規(guī)則由式（4）給出：

由于所要求解的答案只有兩種狀態(tài)，即0和1，分別表示可達(dá)與不可達(dá)，可以用1 bit 來(lái)表示這個(gè)信息。計(jì)算機(jī)在進(jìn)行一次運(yùn)算時(shí)是以字為單位的，設(shè)計(jì)算機(jī)字長(zhǎng)為wbit。那么將信息位壓縮后，時(shí)間復(fù)雜度變?yōu)镺(nm/w)，因?yàn)橛?jì)算機(jī)一次可以對(duì)wbit同時(shí)操作。空間復(fù)雜度也會(huì)相應(yīng)地降低。若以C++中語(yǔ)言的int 類(lèi)型來(lái)存儲(chǔ)信息，因?yàn)橐粋€(gè)int 類(lèi)型有32 bit，那么壓縮后的空間復(fù)雜度會(huì)變?yōu)镺(n2/32)。

2.6 查詢(xún)處理

對(duì)于查詢(xún)(u,v)，如果u=v，那么一定可達(dá)。設(shè)dep[u]表示點(diǎn)u的深度，根的深度為0。點(diǎn)u的區(qū)間標(biāo)記為[lu,ru)，點(diǎn)v的區(qū)間標(biāo)記為[lv,rv)。如果點(diǎn)v在點(diǎn)u的子樹(shù)內(nèi)，即滿(mǎn)足dep[u]

算法3查詢(xún)處理

輸入：(u,v)查詢(xún)u是否能到達(dá)v。

輸出：true or false。

參數(shù)說(shuō)明：dep[u]表示u點(diǎn)深度，map[u]表示關(guān)鍵點(diǎn)u在新圖G′中的編號(hào)。

3 實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境：操作系統(tǒng)Windows 11，CPU Intel i5-9300HF，內(nèi)存16 GB，編譯指令g++-std=c++17-O3。程序語(yǔ)言為C++，編譯器版本為gcc 8.1.0，boost 庫(kù)版本為1.80。實(shí)驗(yàn)共用到14 個(gè)數(shù)據(jù)集[9]，包含了10 個(gè)中小規(guī)模數(shù)據(jù)集與4 個(gè)大規(guī)模數(shù)據(jù)集，表2 展示了數(shù)據(jù)集的規(guī)模。參與比較的算法可以分為兩部分，搜索類(lèi)的算法有IP[22]和BFL[23]，標(biāo)記類(lèi)的算法有TOL[16]、TF-Label[17]和GRKPL。程序代碼均由原作者提供。

表2 數(shù)據(jù)集規(guī)模Table 2 Scale of datasets

算法參數(shù)配置：GRKPL 算法包含兩個(gè)可變參數(shù)。計(jì)算機(jī)字長(zhǎng)w由CPU架構(gòu)決定，實(shí)驗(yàn)采用64位機(jī)器，因此w=64。存儲(chǔ)標(biāo)記類(lèi)型的比特?cái)?shù)b由程序語(yǔ)言與編譯器決定，實(shí)驗(yàn)采用int 類(lèi)型存儲(chǔ)標(biāo)記，因此b=32 。其余算法均采用原論文中使用的默認(rèn)參數(shù)。

實(shí)驗(yàn)內(nèi)容：對(duì)于每一個(gè)數(shù)據(jù)集，隨機(jī)生成1 000萬(wàn)個(gè)查詢(xún)，測(cè)試并分析不同算法在查詢(xún)時(shí)間、預(yù)處理時(shí)間與標(biāo)記的空間占用三方面的表現(xiàn)。

表3 展示了五種算法在處理查詢(xún)時(shí)所耗費(fèi)的時(shí)間?？梢园l(fā)現(xiàn)在14個(gè)數(shù)據(jù)集的測(cè)試中，GRKPL算法在其中8個(gè)數(shù)據(jù)集上都有更好的表現(xiàn)，但是也有一些表現(xiàn)不佳的情況，這是由于稀疏圖中大部分的隨機(jī)查詢(xún)都是不可達(dá)的。雖然GRKPL 回答查詢(xún)的復(fù)雜度是O(1)，但并沒(méi)有對(duì)不可達(dá)的查詢(xún)進(jìn)行優(yōu)化，因此程序運(yùn)行時(shí)所執(zhí)行的語(yǔ)句會(huì)相對(duì)更多，時(shí)間就會(huì)相對(duì)較慢。GRKPL 算法在10 個(gè)中小規(guī)模數(shù)據(jù)集上查詢(xún)共用時(shí)663.145 ms，優(yōu)于其他四種對(duì)比算法，查詢(xún)平均用時(shí)減少49.8%。

表3 查詢(xún)處理時(shí)間Table 3 Query processing time 單位：ms

表4 展示了五種算法在不同數(shù)據(jù)集上的預(yù)處理時(shí)間?？梢钥闯鏊阉黝?lèi)算法（IP、BFL）的表現(xiàn)整體優(yōu)于標(biāo)記類(lèi)算法（TOL、TF-Label、GRKPL）。這是由于算法類(lèi)型的不同，搜索類(lèi)構(gòu)建的標(biāo)記更多是用于對(duì)搜索過(guò)程的剪枝，而標(biāo)記類(lèi)算法則是需要依靠標(biāo)記來(lái)回答詢(xún)問(wèn)。因此這注定了搜索類(lèi)算法在預(yù)處理時(shí)間以及標(biāo)記存儲(chǔ)空間兩方面都會(huì)優(yōu)于標(biāo)記類(lèi)算法，表5 展示的標(biāo)記的空間占用情況也證實(shí)了這一點(diǎn)。盡管如此，GRKPL 算法在許多數(shù)據(jù)集上的表現(xiàn)也會(huì)優(yōu)于搜索類(lèi)算法，并在絕大多數(shù)情況下都會(huì)優(yōu)于其他兩種標(biāo)記類(lèi)算法或表現(xiàn)相當(dāng)。GRKPL 在10 個(gè)中小規(guī)模數(shù)據(jù)集上的預(yù)處理時(shí)間總計(jì)為16.965 ms，僅次于搜索類(lèi)算法BFL 的6.026 ms。相比同屬標(biāo)記類(lèi)算法中表現(xiàn)較好的TOL（20.549 ms），預(yù)處理時(shí)間減少17.4%。GRKPL在10個(gè)中小規(guī)模數(shù)據(jù)集上的空間占用總計(jì)為1.443 MB，優(yōu)于其他四種對(duì)比算法，空間占用平均減少65.1%。但是在大規(guī)模數(shù)據(jù)集上，GRKPL算法的預(yù)處理時(shí)間與空間占用都非常大。這是由于圖中存在大量的入度為0的節(jié)點(diǎn)，導(dǎo)致非樹(shù)邊的數(shù)量較高，影響了性能表現(xiàn)。

表4 預(yù)處理時(shí)間Table 4 Preprocessing time 單位：ms

表5 標(biāo)記的空間占用Table 5 Space occupied by labels 單位：MB

測(cè)試所用的數(shù)據(jù)集分別對(duì)應(yīng)了若干個(gè)不同的現(xiàn)實(shí)領(lǐng)域。如agrocvc、amaze、anthra 等對(duì)應(yīng)于生化領(lǐng)域，包括蛋白質(zhì)相互作用、基因表達(dá)等?；颉⒒衔?、蛋白質(zhì)等可以抽象為節(jié)點(diǎn)，它們之間已知的關(guān)聯(lián)作用可以抽象為有向邊。GRKPL算法可用于快速回答兩個(gè)節(jié)點(diǎn)是否存在直接或間接的聯(lián)系，如查詢(xún)一個(gè)基因是否受到另一個(gè)基因的調(diào)控。nasa 與xmark為XML 文檔，其結(jié)構(gòu)化的特征使其能夠被抽象為一張有向圖。GRKPL算法能夠快速回答元素之間的從屬關(guān)系。GRKPL算法的特點(diǎn)在于其影響復(fù)雜度的主要因素為圖中非樹(shù)邊的數(shù)量，這使得其在一些規(guī)模較小的現(xiàn)實(shí)網(wǎng)絡(luò)如生化網(wǎng)絡(luò)、XML 文檔等中優(yōu)勢(shì)較大，不僅查詢(xún)速度快，標(biāo)記占用空間與預(yù)處理時(shí)間也很少。但在一些規(guī)模較大的網(wǎng)絡(luò)如郵件網(wǎng)絡(luò)（Email-EuAll）、網(wǎng)站引用網(wǎng)絡(luò)（web-Google）中，因?yàn)榉菢?shù)邊的數(shù)量較大，導(dǎo)致標(biāo)記占用空間與預(yù)處理時(shí)間增加。

4 結(jié)束語(yǔ)

本文提出了一種針對(duì)有向稀疏圖可達(dá)性算法GRKPL。通過(guò)對(duì)圖進(jìn)行拆分，將原圖中的查詢(xún)轉(zhuǎn)換到另一個(gè)規(guī)模更小的點(diǎn)集中的查詢(xún)，該點(diǎn)集也稱(chēng)為關(guān)鍵點(diǎn)集。并證明了關(guān)鍵點(diǎn)集的規(guī)模與原圖中非樹(shù)邊的數(shù)量同階。這使得在處理稀疏圖中可達(dá)性問(wèn)題時(shí)，預(yù)處理標(biāo)記的時(shí)間與標(biāo)記的空間占用都進(jìn)一步縮小。最后在14個(gè)現(xiàn)實(shí)數(shù)據(jù)集中進(jìn)行測(cè)試，GRKPL算法在大部分的數(shù)據(jù)集中都表現(xiàn)優(yōu)異。GRKPL算法局限性在于：其預(yù)處理時(shí)間復(fù)雜度與標(biāo)記占用空間復(fù)雜度的級(jí)別都是非樹(shù)邊數(shù)量的平方。因此當(dāng)作用于一些規(guī)模較大或較為稠密的網(wǎng)絡(luò)時(shí)，算法的性能表現(xiàn)會(huì)下降。

后續(xù)研究方向主要包含兩部分：第一部分是如何優(yōu)化不可達(dá)查詢(xún)的處理速度。在稀疏圖中有大量不可達(dá)查詢(xún)，而GRKPL 算法的邏輯是優(yōu)先判斷可達(dá)。因此在面對(duì)不可達(dá)查詢(xún)時(shí)，所要執(zhí)行的步驟較多，會(huì)影響查詢(xún)速度。第二部分是如何將GRKPL算法擴(kuò)展到動(dòng)態(tài)圖中，即在面對(duì)節(jié)點(diǎn)或邊的動(dòng)態(tài)增加或刪除時(shí)，如何快速更新標(biāo)記，保證查詢(xún)效率等。