適用于稀疏圖的基于關鍵點標記的可達性算法

苗偉華，危 輝

復旦大學 計算機科學技術學院/軟件學院 認知算法模型實驗室，上海 200438

對于一張有向圖G=(V,E)，其中u,v∈V。可達性查詢是詢問是否存在一條路徑使得u點可以到達v點?？蛇_性查詢是圖論中的基礎操作，廣泛應用于多種場景[1-3]，如XML數據庫、社交網絡分析、物流運輸、生物信息學等。比如檢測兩種蛋白質之間是否存在生物學通路等。但隨著人類社會的發展以及大數據時代的來臨，圖的規模越來越大。傳統算法如傳遞閉包、深度優先搜索等因為具有極高的時間復雜度或空間復雜度而變得不再適用。

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

1 相關工作

目前常見的可達性算法大致可以分為兩類：標記法與搜索法。標記法會預先對圖進行處理，構建并存儲與可達性相關的標記。在回答查詢時，便可以直接通過標記快速回答。如Floyd[10]直接預處理圖中任意兩點間的可達性。鏈剖分[11]將有向圖分割成若干互不相交的鏈，預處理每個點能夠達到每條鏈中的最小編號。樹剖分[8]首先會找到有向圖的一棵生成樹，然后對其進行區間標記。因為有非樹邊的存在，每個點可能會有多個區間標記，那么在回答詢問時就需要遍歷每一個標記。Dual-Labeling[7]將可達性詢問轉化為二維平面上線段數量的查詢。Path-Tree[12]將圖劃分為多條互不相交的路徑，并將每條路徑抽象成一個點，從而得到新圖，最后通過深度優先搜索的方式對新圖進行標記并處理相關標記。相關算法還有很多[13-19]。標記類方法的特點是預處理的過程通常需要花費大量的時間與空間，但查詢的復雜度通常較低，大多數情況下均為常數級別。

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

表1 可達性算法復雜度Table 1 Reachability algorithm complexity

為了方便說明，之后所提到的有向圖都默認為有向無環圖，因為所有的有向圖都可以通過Tarjan算法[28]進行強連通分量縮點后變為有向無環圖。

2 GRKPL算法

GRKPL 即基于關鍵點標記的可達性算法，通過構建關鍵點集，將原圖中的查詢變換成關鍵點集上的查詢，從而降低算法的時間和空間復雜度。設圖G=(V,E)為有向無環圖，其中n=|V|，m=|E|。T=(VT,ET)為圖G的一棵有向生成樹。對于圖G來說，若存在多個入度為0的頂點，那么一棵樹無法完全覆蓋圖G中所有的頂點，但是可以通過建立一個虛擬的根節點vroot，使得vroot向圖G中所有入度為0 的點建邊。這樣以vroot為根的生成樹就可以完全覆蓋圖G中的所有節點。對于有向邊e，如果e∈E∧e∈ET，則稱有向邊e為樹邊，否則稱為非樹邊。設t為圖G中非樹邊的數量，則有式（1）：

其中，di表示i點的入度，其思想是樹上每個節點的入度至多為1，多余的入邊則為非樹邊。對于稀疏圖而言，往往有t<

2.1 區間標記法

樹是有向無環圖的一種特殊情況，對于樹上任意兩點的可達性查詢有一個非常簡單且高效的算法，稱為區間標記法[8]。只需要對樹進行深度優先搜索（前序遍歷），在第一次進入節點u時記錄當前的時間戳lu，在遍歷完u點的子樹后準備回溯時，記錄當前的時間戳ru。這樣對于樹中每一個節點u都有標記[lu,ru)。在查詢兩點之間的可達性時，便可通過查詢兩點的區間標記是否是包含關系來判斷，具體形式由式（2）給出：

如圖1所示，若要判斷v1是否能達到v5，只需查看進入v5的時間是否在v1的區間標記之中，即l5∈[l1,r1) 。又因為3 ∈[0,6)，所以v1點可以到達v5點。通過此算法便可在O(n+m)的時間復雜度下預處理標記，其中n為樹的節點數，m為樹的邊數。在O(1)的時間復雜度內回答詢問。

圖1 區間標記后的樹Fig.1 Tree after interval labeling

因為稀疏圖可以看作以vroot為根的有向生成樹與少量非樹邊的組合，所以可以先找出稀疏圖的有向生成樹，然后對該生成樹進行區間標記。雖然稀疏圖中以vroot為根的生成樹并不唯一，但生成樹的形態對于算法復雜度的影響微乎其微。因為影響算法復雜度的是圖中非樹邊的數量，而這個值與生成樹的形態無關。算法1 提供了一種在選取生成樹的同時進行區間標記的方法。

算法1尋找生成樹并進行區間標記

輸入：vroot表示虛根。

輸出：圖中所有節點的區間標記(l,r)與生成樹。

參數說明：dfn表示時間戳，G表示鄰接表，用于存圖。

2.2 查詢轉化

圖2 展示了對圖G進行區間標記后的結果。其中實線表示樹邊，虛線表示非樹邊。假設查詢(u,v)，即查詢u點是否可以到達v點。如果v點在u點的子樹內，那么u點便可以僅通過樹邊到達v點。不然u點必須要經過若干樹邊和非樹邊才可以到達v點，或者是不可達。定義u點為覆蓋點，當且僅當u點的入邊或出邊中包含非樹邊。圖2 中的覆蓋點集合CG={v5,v6,v8,v11,v12}。若u點要經過若干樹邊和非樹邊才可以到達v點，那么u點必然會先走到其子樹中的某個覆蓋點x，再從x出發經過若干非樹邊和樹邊到達某個覆蓋點y，最后從y點沿樹邊走到v點。這樣便可以把原始查詢(u,v)變為新查詢(x,y)。但并不是所有的查詢都可以轉化為覆蓋點之間的查詢。假如u點的子樹內不包含覆蓋點，那么u點到v點的所有路徑中必然不會經過任何一條非樹邊。同理，若v點的祖先內不包含覆蓋點，那么同樣u點到v點的所有路徑中也不會經過任何一條非樹邊。因此需要對這種情況進行特殊判斷。

圖2 區間標記后的圖GFig.2 Graph G after interval labeling

2.3 構建關鍵點集

設Su表示u點子樹中的覆蓋點集，Pv表示v點祖先中的覆蓋點集。對于查詢(u,v)，如果v點不在u點的子樹中，那么需要枚舉Su中的點，檢查其是否能到達Pv中的任意一點。因為|Su|和|Pv|的數量級都是O(t) 的，所以這種做法的時間復雜度會退化到O(t2)。但事實上可以通過兩步優化，將查詢的復雜度降到O(1)。

優化1設根節點的深度為0。Pv中深度較小的節點一定能夠沿樹邊達到深度大于或等于自身的節點。因此對于查詢(u,v)來說，只需要檢查Su中是否存在一個節點，能夠到達Pv中深度最大的節點即可。這樣時間復雜度就可以降至O(t)。

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

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

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

證明定理2 等價于：對于i∈[2,r]，有?j∈[1,i),成立。當r=2 時，有lca(a1,a2)=lca(b1,b2)，定理顯然成立。假設r=k時定理成立，當r=k+1時，不妨假設存在u=lca(bt,bk+1),t∈[1,k)，且設dep(u)表示u點在生成樹中的深度，因為bj是按照前序遍歷的順序排序后得到的，所以當j

由定理2 可知，LT=Qvroot=Rvroot，因為|Rvroot|的數量級為O(t)，所以LT的數量級也為O(t) 。又因為KG=CT?LT，所以關鍵點集|KG|的數量級也為O(t)。圖3展示了G中的關鍵點集，其中CT={v5,v6,v8,v11,v12}，用斜線填充的節點表示。LT={v1,v2,v3,v7}，用實心節點表示。由于有向圖的生成樹并不唯一，對于不同形態的生成樹，其得到的關鍵點集也是不同的。但由定理2可知，|LT|

圖3 圖G 中的關鍵點集Fig.3 Set of key points in graph G

2.4 標記預處理

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

算法2構建GRKPL標記

輸入：vroot表示虛根。

輸出：圖中所有節點的(sid,pid)。

參數說明：vis[u]表示點u是否訪問過；stk表示棧；par[u]用來記錄點u在樹中的父親；G表示鄰接表，用于存圖；K(G)表示圖G中的關鍵點集。

2.5 閉包傳遞

為了加速關鍵點集中閉包的傳遞，需要將關鍵點集從原圖G中分離出來。圖4 展示了分離之后得到的新圖G′。為了防止G′中邊的規模退化到O(t2)，需要維持原本的樹形結構。具體做法為在深度優先搜索的過程中處理出每個點其祖先中深度最大的關鍵點，然后只需要連接這兩個點即可。這樣既不會破壞閉包，同時也將新圖中邊集的大小控制在了O(t)級別，因為去除非樹邊后，每個點的入度都是1。因此邊集的數量級和點集的數量級是相同的。

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

傳統Floyd-Warshal[10]算法傳遞閉包的時間復雜度是O(n3)，空間復雜度為O(n2)。但對于有向無環圖來說，可以通過動態規劃的方法進行加速，使時間復雜度變為O(nm)。具體做法是：首先設dp[u][v]這個二維數組存儲圖G中任意兩點之間的可達性，取值0或1。然后將圖G按逆拓撲序進行排序后順序遍歷，若當前節點為u，那么u點可以通過它的出邊到達它所有的后繼節點，即可以用所有后繼節點的狀態來更新當前節點的狀態。又因為遍歷的順序是逆拓撲序，這樣就保證了訪問u點之前，u點所有可能可達的點已經都訪問過，從而保證了算法的正確性。具體更新規則由式（4）給出：

由于所要求解的答案只有兩種狀態，即0和1，分別表示可達與不可達，可以用1 bit 來表示這個信息。計算機在進行一次運算時是以字為單位的，設計算機字長為wbit。那么將信息位壓縮后，時間復雜度變為O(nm/w)，因為計算機一次可以對wbit同時操作。空間復雜度也會相應地降低。若以C++中語言的int 類型來存儲信息，因為一個int 類型有32 bit，那么壓縮后的空間復雜度會變為O(n2/32)。

2.6 查詢處理

對于查詢(u,v)，如果u=v，那么一定可達。設dep[u]表示點u的深度，根的深度為0。點u的區間標記為[lu,ru)，點v的區間標記為[lv,rv)。如果點v在點u的子樹內，即滿足dep[u]

算法3查詢處理

輸入：(u,v)查詢u是否能到達v。

輸出：true or false。

參數說明：dep[u]表示u點深度，map[u]表示關鍵點u在新圖G′中的編號。

3 實驗

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

表2 數據集規模Table 2 Scale of datasets

算法參數配置：GRKPL 算法包含兩個可變參數。計算機字長w由CPU架構決定，實驗采用64位機器，因此w=64。存儲標記類型的比特數b由程序語言與編譯器決定，實驗采用int 類型存儲標記，因此b=32 。其余算法均采用原論文中使用的默認參數。

實驗內容：對于每一個數據集，隨機生成1 000萬個查詢，測試并分析不同算法在查詢時間、預處理時間與標記的空間占用三方面的表現。

表3 展示了五種算法在處理查詢時所耗費的時間?？梢园l現在14個數據集的測試中，GRKPL算法在其中8個數據集上都有更好的表現，但是也有一些表現不佳的情況，這是由于稀疏圖中大部分的隨機查詢都是不可達的。雖然GRKPL 回答查詢的復雜度是O(1)，但并沒有對不可達的查詢進行優化，因此程序運行時所執行的語句會相對更多，時間就會相對較慢。GRKPL 算法在10 個中小規模數據集上查詢共用時663.145 ms，優于其他四種對比算法，查詢平均用時減少49.8%。

表3 查詢處理時間Table 3 Query processing time 單位：ms

表4 展示了五種算法在不同數據集上的預處理時間?？梢钥闯鏊阉黝愃惴ǎ↖P、BFL）的表現整體優于標記類算法（TOL、TF-Label、GRKPL）。這是由于算法類型的不同，搜索類構建的標記更多是用于對搜索過程的剪枝，而標記類算法則是需要依靠標記來回答詢問。因此這注定了搜索類算法在預處理時間以及標記存儲空間兩方面都會優于標記類算法，表5 展示的標記的空間占用情況也證實了這一點。盡管如此，GRKPL 算法在許多數據集上的表現也會優于搜索類算法，并在絕大多數情況下都會優于其他兩種標記類算法或表現相當。GRKPL 在10 個中小規模數據集上的預處理時間總計為16.965 ms，僅次于搜索類算法BFL 的6.026 ms。相比同屬標記類算法中表現較好的TOL（20.549 ms），預處理時間減少17.4%。GRKPL在10個中小規模數據集上的空間占用總計為1.443 MB，優于其他四種對比算法，空間占用平均減少65.1%。但是在大規模數據集上，GRKPL算法的預處理時間與空間占用都非常大。這是由于圖中存在大量的入度為0的節點，導致非樹邊的數量較高，影響了性能表現。

表4 預處理時間Table 4 Preprocessing time 單位：ms

表5 標記的空間占用Table 5 Space occupied by labels 單位：MB

測試所用的數據集分別對應了若干個不同的現實領域。如agrocvc、amaze、anthra 等對應于生化領域，包括蛋白質相互作用、基因表達等。基因、化合物、蛋白質等可以抽象為節點，它們之間已知的關聯作用可以抽象為有向邊。GRKPL算法可用于快速回答兩個節點是否存在直接或間接的聯系，如查詢一個基因是否受到另一個基因的調控。nasa 與xmark為XML 文檔，其結構化的特征使其能夠被抽象為一張有向圖。GRKPL算法能夠快速回答元素之間的從屬關系。GRKPL算法的特點在于其影響復雜度的主要因素為圖中非樹邊的數量，這使得其在一些規模較小的現實網絡如生化網絡、XML 文檔等中優勢較大，不僅查詢速度快，標記占用空間與預處理時間也很少。但在一些規模較大的網絡如郵件網絡（Email-EuAll）、網站引用網絡（web-Google）中，因為非樹邊的數量較大，導致標記占用空間與預處理時間增加。

4 結束語

本文提出了一種針對有向稀疏圖可達性算法GRKPL。通過對圖進行拆分，將原圖中的查詢轉換到另一個規模更小的點集中的查詢，該點集也稱為關鍵點集。并證明了關鍵點集的規模與原圖中非樹邊的數量同階。這使得在處理稀疏圖中可達性問題時，預處理標記的時間與標記的空間占用都進一步縮小。最后在14個現實數據集中進行測試，GRKPL算法在大部分的數據集中都表現優異。GRKPL算法局限性在于：其預處理時間復雜度與標記占用空間復雜度的級別都是非樹邊數量的平方。因此當作用于一些規模較大或較為稠密的網絡時，算法的性能表現會下降。

后續研究方向主要包含兩部分：第一部分是如何優化不可達查詢的處理速度。在稀疏圖中有大量不可達查詢，而GRKPL 算法的邏輯是優先判斷可達。因此在面對不可達查詢時，所要執行的步驟較多，會影響查詢速度。第二部分是如何將GRKPL算法擴展到動態圖中，即在面對節點或邊的動態增加或刪除時，如何快速更新標記，保證查詢效率等。