杜 明，楊安平，周軍鋒*，陳子陽，楊 云

（1.東華大學計算機科學與技術(shù)學院，上海201620；2.上海立信會計金融學院信息管理學院，上海201620）

0 引言

給定有向無環(huán)圖（Directed Acyclic Graph，DAG）G，可達性查詢u？→v用于回答從頂點u出發(fā)是否存在一條路徑可以到達頂點v。實際應(yīng)用中，如社交網(wǎng)絡(luò)、通信與傳感器網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、可擴展標記語言（eXtensible Markup Language，XML）數(shù)據(jù)、資源描述框架（Resource Description Framework，RDF）數(shù)據(jù)等，可達性查詢可用于檢測兩點間是否存在特定關(guān)系?？蛇_性查詢處理是圖數(shù)據(jù)管理與分析的基本操作之一，是研究者廣泛關(guān)注的熱點問題［1-2］。然而，實際中除了檢測兩點間是否存在特定關(guān)系，還需要考慮關(guān)系的強弱程度，如存在信號衰減的傳感器網(wǎng)絡(luò)，用戶更感興趣的是長度受限的可達性查詢。傳統(tǒng)的可達性查詢只能回答兩個頂點間是否可達，并不能確定在幾步內(nèi)可達。本文研究k 步可達查詢的高效處理問題。與基本的可達性查詢相比，k步可達查詢用于回答從u出發(fā)，是否存在長度在k 步之內(nèi)的路徑到v。傳統(tǒng)的可達查詢可以看作k=∞時的k 步可達查詢［3］。由于k 步可達性查詢體現(xiàn)著圖中頂點對其他頂點的影響力，因而相對可達性查詢而言，能提供更多的信息。

現(xiàn)有解決k 步可達性查詢的方法主要分為兩類：Label-Only［4］和Label+G［5-7］。Label-Only類方法的主要思想是通過構(gòu)建所有可達頂點間最短路徑的索引，當判斷從頂點u能否在k步內(nèi)到達頂點v 時，只需通過標簽得到u 和v 之間的最短路徑長度，然后比較從u 到v 的最短路徑長度與k 的大小關(guān)系。當最短距離大于k 時，說明該查詢不滿足k 步可達性，否則說明該查詢滿足k 步可達性。Label+G 類方法的主要思想是快速構(gòu)建部分可達信息的索引，處理查詢時，若索引可回答查詢，則直接返回結(jié)果；否則需要通過圖遍歷來得到最終結(jié)果。相比較而言，Label-Only類方法的索引規(guī)模大、索引構(gòu)建時間長，且當查詢不可達時，處理效率低。而現(xiàn)有的Label+G 類方法由于索引記錄的可達信息少，查詢處理時需要遍歷的頂點較多，當滿足條件的查詢數(shù)量增多時，算法性能顯著下降。

針對以上問題，本文提出一種求解k 步可達查詢的高效Label+G算法kRH。其基本思想是通過快速構(gòu)建索引規(guī)模小、可達信息覆蓋廣的索引，從而可以在常量時間回答更多的查詢，同時降低圖遍歷的代價。具體來說，本文的工作如下：

1）提出一種基于部分點的雙向最短路徑索引，用于在常量時間回答大部分k 步可達查詢，并提出三種啟發(fā)式規(guī)則來減小索引規(guī)模。

2）提出基于簡化圖的正反互逆拓撲來提高不可達查詢的處理效率。

3）提出遠距離優(yōu)先的雙向搜索策略，并在此基礎(chǔ)上提出高效的查詢處理策略。

4）基于多個真實的數(shù)據(jù)集進行測試，實驗結(jié)果顯示，本文提出的方法比現(xiàn)有方法更高效。

1 背景知識及相關(guān)工作

1.1 數(shù)據(jù)模型及相關(guān)概念

本文處理有向無環(huán)圖（DAG）上的k 步可達查詢。給定DAG，V 表示頂點的集合，E 表示邊的集合。后續(xù)討論中，用(u，v)∈E 表示從u 到v 的邊，δ(u，v)表示u 與v 的最短路徑，Out(u)表示u 指向的頂點集，In(u)表示指向u 的頂點集。Out*(u)表示u 可達的頂點集，In*(u)表示可達u 的頂點集。給定G 中任意兩個頂點u 和v，若從u 到v 存在一條有向路徑，則說明u 可達v，否則說明u 不可達v。若從u 到v 存在一條長度不大于k 的路徑，說明從u 出發(fā)k 步可達v，用u →kv 表示；否則u不能在k步可達v，用u?kv表示。

對于一個DAG 來說，它體現(xiàn)頂點之間的偏序關(guān)系，通過拓撲排序，將頂點的偏序關(guān)系轉(zhuǎn)變?yōu)槿蜿P(guān)系，拓撲號即為全序關(guān)系的序號。頂點u、v 的拓撲號分別為Xu和Xv，若存在Xu＞Xv，u不可達v。

1.2 相關(guān)工作

1.2.1 可達查詢

針對圖論中的可達性查詢，按照索引覆蓋范圍的大小，分為兩大類：1）構(gòu)建全索引的方式；2）構(gòu)建部分索引的方式。全索引方式的主要思想是通過記錄任意兩個頂點之間的可達信息來處理可達查詢?；谠撍枷耄墨I［8］采用傳遞閉包的方式記錄任意兩個頂點間的可達信息，該算法雖然能夠在O(1)的時間復雜度內(nèi)處理查詢，缺點是空間復雜度是，實際中擴展性太差，無法應(yīng)用于大圖。文獻［9］采用壓縮傳遞閉包的方式，通過向上向下遍歷給圖中每個頂點v 附加兩個區(qū)間LIN(v)和LOUT(v)。當需要判斷u 與v是否可達時，僅需要判斷u 和v 之間是否存在交集，若交集不為空，則說明u 可達v；否則，u 不可達v。部分索引方式的主要思想是通過記錄部分頂點之間的可達信息配合遍歷的方式來處理可達查詢?；谠撍枷?，GRIPP算法［10］給所有頂點附加一個區(qū)間，并通過區(qū)間包含來判斷頂點間是否可達，若區(qū)間不包含，則需要通過遍歷的方法才能判定。Grial 算法［11］在GRIPP 算法的基礎(chǔ)上，采用不同的遍歷方式給圖中所有頂點附加多個區(qū)間，同樣是采用區(qū)間包含判定是否可達，對于不能判斷的查詢，需要采用遍歷的方式才能夠判斷。FELINE 算法［12］通過給圖中每個頂點附加兩個整數(shù)，代表頂點在圖中拓撲排序的序號，若頂點u 的拓撲序號大于v的拓撲序號，則可以判定u不可達v。

1.2.2 Label-Only方法

Label-Only 方法的思想是通過記錄所有頂點對之間的最短路徑長度來回答k 步可達查詢?；谠撍枷?，一種簡單的方法是直接記錄所有頂點對之間的最短路徑長度，該方法雖然可以O(shè)(1)時間回答k步可達查詢，但空間復雜度為在實際應(yīng)用中可擴展性太差，無法處理大圖。針對該問題，文獻［9］提出一種壓縮的最短路徑索引PLL（Pruned Landmark Labeling）。其基本思想是為圖中的每一個頂點v 建立LIN(v)和LOUT(v)兩個標簽，其中LIN(v)標簽用來記錄頂點v與In*(v)中部分頂點間的最短路徑，LOUT(v)用來記錄v 與Out*(v)中部分頂點間的最短路徑。則u 和v 之間的最短路徑δ(u，v)的計算問題就轉(zhuǎn)換為求解中間節(jié)點和u、v 最短路徑之和的最小值問題。當需要回答從u 到v 是否k 步可達時，只需判斷LIN(v)和LOUT(v)是否存在交集。若不存在交集，則說明兩個頂點不滿足k 步可達；若存在交集，說明u 通過交集中的任意一個頂點都可到達v。基于交集結(jié)果，可得到所有交集頂點與u 和v之間的最短路徑之和，則u和v之間的最短路徑δ(u，v)就等于最短路徑之和中的最小值。如果δ(u，v)≤k，說明u →kv；否則，說明u?kv。

該方法的問題在于兩方面：1）索引規(guī)模大、索引時間長，原因在于需要記錄完整的最短路徑信息；2）對不可達查詢的處理效率較低，原因是LOUT(u)與LIN(v)的交集為空意味著需要訪問LOUT(u)與LIN(v)中的所有信息。

1.2.3 Label+G方法

由于通過直接遍歷回答查詢的效率太低，而Label-Only方法的索引時間長、索引規(guī)模大，研究者試圖通過僅記錄部分k 步可達信息來在效率方面進行平衡。其基本思想是在線性或者近似線性時間復雜度內(nèi)記錄部分k 步可達信息，用于減小遍歷操作的搜索空間，根據(jù)其剪枝能力的不同，分為三種類型的方法。

第一類方法是直接使用傳統(tǒng)的可達查詢處理方法［10-11］來回答不可達查詢，對于可達查詢，通過直接遍歷的方法檢測是否滿足k 步的條件。該類方法雖然索引時間少，索引規(guī)模小，但當滿足條件的查詢數(shù)量增多時，效率異常低下。

第二類方法是構(gòu)建可回答部分k 步可達查詢的索引來加快查詢處理的速度。文獻［5-7］基于頂點覆蓋技術(shù)構(gòu)建k 步索引。其基本思想是首先求得原圖的一個頂點覆蓋集合，然后在頂點覆蓋集上構(gòu)建傳遞閉包作為索引，最后根據(jù)該索引來處理k 步可達查詢。這種方法的問題是索引只能回答固定k值的可達查詢，擴展性較差。

第三類方法［3］采用FELINE 算法［12］作為特定的剪枝條件，來快速回答不可達查詢，對于其他查詢，則提出基于廣度優(yōu)先生成樹以及廣度層作為剪枝條件來提高k 步可達查詢的處理效率。該方法為生成樹的每個頂點附加一個區(qū)間，用于判斷頂點之間的祖先后代關(guān)系。若L(v)?L(u)，說明v 是u 的后代，則查詢可通過比較u 和v 之間的層數(shù)差來判斷；若L(v)?L(u)，說明v不是u的后代，則需要遞歸判斷u的后代中是否存在頂點p，滿足L(v)?L(p)。該算法的缺點是生成樹的區(qū)間覆蓋率很低，因此，當滿足條件的查詢數(shù)量增多時，查詢效率較低。

相比較而言，Label-Only方法雖然查詢處理時無需遍歷操作，但索引規(guī)模大、索引構(gòu)建時間長，同時對不可達查詢的處理效率較低；而Label+G 方法雖然索引構(gòu)建時間短、索引規(guī)模小，但查詢處理時因需要遍歷操作而顯得效率較低，尤其是當滿足條件的查詢增多時，效率顯著下降。本文針對該問題，提出一種增強的Label+G 方法，在降低索引規(guī)模的前提下，通過增強不可達查詢和可達查詢的剪枝效果來縮減遍歷操作的搜索空間，提升k步可達查詢的處理效率。

2 基于部分點的雙向最短路徑索引

2.1 雙向最短距離索引的基本思想

本文提出基于部分出度與入度之和較大的頂點（簡稱hop點）建立雙向最短路徑索引來加速k 步可達的判斷，這里雙向的意思是不僅記錄a與其可達點的最短距離，而且記錄a與可達a 的點的最短距離。具體來說，類似于2hop 索引［4］，本文為每個點v 設(shè)定兩個標簽LIN(v)和LOUT(v)。和2hop 索引的不同在于，兩個標簽中不僅僅記錄了可達信息，而且記錄了最短路徑信息。其中前者LIN(v)用于存儲可達v 及其與v 的最短路徑，后者LOUT(v)存儲v可達的點及其與v的最短距離。

圖1 有向無環(huán)圖G的示例Fig.1 Example of DAG G

例如，對圖1 的G，假設(shè)頂點的處理順序是c →a →b →d →e →f →g。當 處 理c 時，其 可 達 點 為c，e，f，g，可達c 的點為a，b。因此將元組加入到LIN(u（)其中u ∈{c，e，f，g}）中，這里dis 表示c 到u 的最短路徑長度。類似地，將加入LOUT(v)中（其中v ∈{a，b}），這里dis表示v和c 的最短路徑長度。表1 是基于圖1 所有頂點構(gòu)建的最短路徑索引。

表1 基于所有頂點的最短路徑索引Tab.1 Shortest path index based on all points

基于表1的索引，則給定任意兩點a和b，判斷a是否可在k 步到達b，則只需比較LOUT(a)和LIN(b)：如果二者的交集為空，說明a 不可達b；否則說明a 可達b。如果a 可達b，將a 通過交集中每個點到達b 的路徑長度計算出來，取其最小值即為a 和b 的最短路徑長度。如果該長度小于給定的k 值，則說明a可以在k步可達b，否則a不能在k步到達b。

2.2 雙向最短距離索引的優(yōu)化

雖然該索引可回答所有查詢，且無需在圖上執(zhí)行遍歷操作，但其索引規(guī)模太大，且求解交集的代價太高。為此，提出僅構(gòu)建部分點的雙向路徑索引來減小索引規(guī)模。原因在于：1）實際中的圖存在少量度很大的點，相應(yīng)地，其可達頂點也通常比較多，選擇這樣的點構(gòu)建雙向最短路徑可以顯著增加所維護的可達點對數(shù)量及通過這種點的最短路徑長度。2）我們的實驗表明，對一般圖來說，要么32 個點已經(jīng)維護了足夠多的可達信息，再增加頂點后，可達信息并沒有明顯增加；要么32 個點僅維護少量可達信息，再增加這種點同樣不會顯著增加可達信息維護量。如圖2 所示，從實際數(shù)據(jù)上的測試結(jié)果可以看出：對于amaze 數(shù)據(jù)集，即使k=1，雙向索引的可達覆蓋率也可接近100%；而對cit-Patents 而言，即使k 值增加到32，可達覆蓋率依然非常??；另外兩個數(shù)據(jù)集上，當k 值增加到16以后，數(shù)據(jù)基本不再發(fā)生變化。

圖2 k個hop 點可達覆蓋率Fig.2 Coverage of reachability for k hop nodes

基于以上觀察，取32 個點構(gòu)建雙向最短路徑索引。假設(shè)對于圖1 所示的DAG G，本文取c 和f 兩個點構(gòu)建雙向最短路徑索引，如表2 所示。顯然，和表1 的索引相比，表2 的規(guī)模降低了。實際上，表2還可以進一步優(yōu)化。

表2 基于c和f的最短路徑索引Tab.2 Shortest path index based on c and f

定理1當基于頂點v 構(gòu)建雙向最短路徑索引時，如果向上（向下）遍歷的過程中遇到了已處理的hop 點u，則無需從u繼續(xù)向上（向下）遍歷。

證明 如圖3 所示，假設(shè)x 可達u，當前處理的是hop 點v，hop點u在v之前處理。當從v向上遍歷時遇到了u?；趗得到的標簽，假設(shè)求得x 到u 的距離是d1，u 到v的距離是d2，則x通過u 到v 的距離是d1+d2。顯然，從v 向上遍歷遇到u，所求u 與v 之間的距離仍然是d2，因此即使在u 不停止，所得x 和v的距離仍然是d1+d2，因此，無需從u繼續(xù)向上遍歷。

圖3 hop點作用示意圖Fig.3 Schematic diagram of hop nodes intension

定理2當基于頂點v 構(gòu)建雙向最短路徑索引時，如果向上（向下）遍歷的過程中通過非hop點遇到了w，且w通過u到v的距離小于w 通過非hop 點到v 的距離，則無需從w 繼續(xù)向上（向下）遍歷。

證明 如圖3 所示，假設(shè)hop 點u 先處理，目前處理的是hop 點v。假設(shè)從v 向上遍歷，通過非hop 點到達w，路徑長度是d4。如果w 和u的最短距離是d3，且d3+d2≤d4，顯然無需在LOUT(w)中記錄其和v 的距離d4，因為d4不是最短距離。因此，無需從w開始繼續(xù)向上遍歷。

基于定理1和定理2，在求解雙向最短路徑索引的過程中可有效減小索引規(guī)模，提高索引構(gòu)建的速度。例如，對圖1 的G 而言，假設(shè)選擇兩個hop 點c 和f 來構(gòu)建雙向最短路徑索引。先處理的是點c，當處理第二個點f時，當從其向上遍歷遇到第一個hop 點c時，可根據(jù)定理1 立即停止遍歷，當從非hop 點遍歷到b 時，可根據(jù)定理2 立即停止遍歷。當處理完這兩個點后，所得到的雙向路徑索引如表3所示。

表3 基于c和f的優(yōu)化后的最短路徑索引Tab.3 Optimized shortest path index based on c and f

3 基于棧的正反互逆拓撲

可達是k步可達的必要條件，因此，若查詢不可達，則必定k步不可達?；诖?，本文使用拓撲序號為基礎(chǔ)的方法來快速判斷不可達。其基本思想是：給定兩個頂點u和v，若u的拓撲號大于v的拓撲號，則u不可達v，因此u在k步內(nèi)不可達v。

文獻［3］通過使用互逆的兩個拓撲號來增強不可達查詢的判斷能力。具體而言，給定第一個拓撲順序，在構(gòu)建逆序拓撲時，始終優(yōu)先訪問第一個拓撲號最大且所有入鄰居均被訪問的頂點。以此建立的拓撲稱為第一遍拓撲的逆向拓撲。雖然實際中互逆拓撲可快速判斷很多不可達查詢，但仍然存在兩方面的問題。

首先，在實際應(yīng)用中，基于正向建立的兩個互逆拓撲號仍然存在很多不可達查詢無法判斷的問題。針對該問題，本文提出構(gòu)建正反互逆拓撲來過濾更多的不可達查詢。其基本思想是：首先，刪除已處理的hop 點。原因是與hop 點關(guān)聯(lián)的最短路徑均已處理完畢，后續(xù)的最短路徑計算與其無關(guān)。刪除hop點之后，數(shù)據(jù)圖得以很大程度上的簡化。其次，自頂向下、以深度優(yōu)先的方式構(gòu)建正向互逆拓撲。最后，沿著邊的相反方向，以自底向上，以深度優(yōu)先的方式構(gòu)建反向互逆拓撲。

其次，文獻［12］基于堆求解逆序拓撲，其時間復雜度為O(|V|log|V|)。本文設(shè)計了高效算法在線性時間構(gòu)建正反互逆拓撲。與以上工作相比，由于首先刪除了hop 點，因而所建立的正反互逆拓撲可以過濾更多的不可達查詢。和文獻［12］相比，本文提出的正反互逆拓撲索引具有線性的時間復雜度，同時能過濾更多的不可達查詢。和文獻［3］的方法相比，由于我們在求解正反互逆拓撲之前去除了hop 點，數(shù)據(jù)圖得以很大程度的簡化，因而效率更高。

4 索引構(gòu)建

4.1 基于hop點的最短距離索引構(gòu)建

4.1.1 算法描述

給定DAG G，求解hop 點的最短路徑索引總體上分為3步。首先求解hop 點，然后基于hop 點執(zhí)行廣度優(yōu)先遍歷（Breadth First Search，BFS）建立LIN索引，最后基于hop 點執(zhí)行反向BFS建立LOUT索引。下面分別予以說明。

（1）根據(jù)(In(v)+1)*(Out(v)+1)從大到小的順序選擇前32個頂點作為hop點。如算法1第1）行。

（2）從hop 點v 開始執(zhí)行BFS，對于遍歷到的頂點u，若是通過標簽計算得到了長度大于從v 到u 的路徑長度，則更新LIN(u)并繼續(xù)訪問u可達的點；若是通過標簽計算得到的長度小于從v 點到u 的路徑長度，則不更新LIN(u)且不再從u 出發(fā)繼續(xù)BFS。如算法1第2）～12）行所示。

（3）從hop點開始執(zhí)行反向BFS，對于遍歷到的頂點u，若是通過標簽得到的長度大于從hop點到u的路徑長度，則更新LOUT(u)并且訪問u的父親；若通過標簽得到的長度小于從hop點到u 的路徑長度，則不更新LOUT(u)且不訪問u 的父親。如算法1第13）行所示。

算法1 hop(G=(V，E))。

算法1 用于求解基于hop 頂點的最短路徑，其中QU(v，u，LOUT(v)，LIN(u))表示通過標簽求解得到從v 到u 的最短路徑長度，Dis(v，u)表示基于BFS得到從v到u路徑長度，初始值為0，Q表示隊列。算法1中第1）行按照規(guī)則選擇度大的32 個頂點作為hop 點。第2）、3）行將hop 點依次執(zhí)行入隊操作。當隊列不空時，執(zhí)行出隊操作（第5）、6）行）。若通過標簽求得的最短路徑不大于遍歷的路徑長度，則停止訪問其后代（第7）、8）行）；否則，更新LIN標簽，并將其后代加入到Q 中（第9）～12）行）。將hop點v再入隊列，通過執(zhí)行反向BFS構(gòu)建第13）行）。

注 意，算 法1 中 需 要 在 第7）行 調(diào) 用 函 數(shù)QU(v，u，LOUT(v)，LIN(u))求解根據(jù)已處理hop 點得到的路徑長度。這一操作需要比較LOUT和LIN，即執(zhí)行集合求交集的操作。為了加快集合交集操作的處理，需要先對集合中的頂點按照編號，或者某種序號進行排序。

4.1.2 索引優(yōu)化

若v 和u 之 間 通 過hop 點 有 路 徑 相 連，則 函 數(shù)QU(v，u，LOUT(v)，LIN(u))進行集合交集操作的結(jié)果是經(jīng)過hop 點相連的路徑長度，無需知道hop 點是誰。因此，采用如下規(guī)則對算法1進行優(yōu)化。

規(guī)則1 所有頂點的LIN或者LOUT中無需存儲頂點自身編號，只需存儲代表頂點處理順序的數(shù)字即可。

根據(jù)規(guī)則1，構(gòu)建索引時，無需執(zhí)行排序操作，對第i 個處理的hop 點，直接在相應(yīng)頂點的標簽中加入即可，這里的i表示當前hop點是第i個被處理的hop點，dis是hop點和當前點的最短路徑距離。

進一步，由于只選擇了32個hop點，且實際中數(shù)據(jù)圖的拓撲層數(shù)有限，因此無需使用兩個整數(shù)來表示標簽中的元組。利用規(guī)則2來進一步減少索引規(guī)模。

4.2 正反互逆拓撲構(gòu)建

求解正反互逆的拓撲號索引總體上分為4 步：首先刪除32 個hop 點，然后求解正向的拓撲號X，接著基于X 求其逆向拓撲號Y，最后在反向圖上求解兩個拓撲號索引M和N。

給定一個有向無環(huán)圖G，可以通過以下步驟得到X：1）將G中入度為0的頂點入棧S。2）對棧中元素執(zhí)行以下操作：（a）將S的棧頂元素v出棧，并標記v的拓撲順序；（b）刪除v及所有從v 出發(fā)的邊；（c）將v 的孩子中入度為0 的頂點插入S。3）重復步驟2）直到S為空，相應(yīng)的頂點出棧順序稱為X。

給定X，同樣基于棧可以得到其逆向拓撲順序Y。基本操作方法如下：首先所有入度為0 的頂點按照它們在X 中從小到大的順序進入棧S。對棧中元素執(zhí)行以下操作：1）將S的棧頂元素v 出棧，并標記v 的逆向拓撲號；2）刪除v 及從v 出發(fā)的邊；3）將v的孩子中入度為0 的頂點按照它們在X 中從小到大的順序入棧。執(zhí)行上述步驟，直至?？占纯傻玫降诙瓮負漤樞験。

定理3求解逆向拓撲時，棧頂元素和使用堆選擇的拓撲號最大的元素為相同頂點。

證明 首先，使用大頂堆時，堆頂元素是當前堆中拓撲號最大的頂點。其次，使用棧時，本文首先將入度為0 的頂點按照第一遍拓撲的順序從小到大入棧，因此可以保證對初始入度為0 的頂點，棧頂元素的拓撲號最大。最后，由于棧頂元素的拓撲號最大，其孩子的拓撲號必然也大于棧中元素的拓撲號。每處理一個棧頂元素，其孩子中可進一步拓撲的頂點也是按照第一遍拓撲的順序從小到大入棧，這樣可以保證棧頂元素始終具有最大的拓撲號。因而可以保證每次處理的都是可拓撲的頂點中拓撲號最大的。

算法2 genTopo(G=(V，E))。

輸入 G=(V，E)；

輸出 所有頂點v的四個拓撲序號X，Y，M，N。

1） 從G中刪除32個hop點

2） Construct(G，X)

3） Construct(G，Y)

4） 將G的邊反轉(zhuǎn)，執(zhí)行第1)～2)行，求解反向互逆拓撲

第2）、3）行都是調(diào)用的Construct函數(shù)，代碼如下所示：

Function Construct(G=(V，E)，H)

1） 將入度為0的頂點按照特定順序入棧S

2） topoNum ←0

3） while S ≠? do

4） v ←pop(S)

5） HV←topoNum

6） topoNum ←topoNum+1

7） for each u ∈Out(v) do

8） insize(u)←insize(u)-1

9） if insize(u)=0 then push u into S

在得到正向互逆的拓撲后，將圖的邊反轉(zhuǎn)，在反向圖上執(zhí)行上述步驟，從而得到反向圖上的拓撲號M 和N。最終，這4個拓撲順序構(gòu)成本文提出的正反互逆的拓撲號索引。

算法2 用于求解給定的DAG G 的正反互逆拓撲序號，其中第2）行調(diào)用函數(shù)Construct 求解第一個拓撲順序X，第3）行求X 的逆向拓撲Y，第4）行求解反向互逆拓撲M 和N。函數(shù)Construct 用于根據(jù)特定順序得到一個拓撲序號，其中S 為棧，Hv表示頂點的拓撲序號。insize(v)表示存儲頂點v 入度的臨時數(shù)組。第1）行將圖中入度為0 的頂點入棧。從第3）～9）行的迭代中，每循環(huán)一次處理一個頂點。具體做法是，第4）～5）行元素出棧并設(shè)定其拓撲號，然后在第7）～9）行將其出鄰居的入度減1，若入度為0，則將其入棧。需要注意的是，算法第1）行，對于第一和第三遍拓撲，特定順序不代表任何含義，只要找到一個入度為0 的頂點就將其入棧。第二遍和第四遍求的分別是第一、三遍的逆向拓撲，這時，特定順序代表在第一邊拓撲后，根據(jù)第一遍拓撲序號的升序?qū)⑷攵葹? 的頂點入棧，這樣就能保證第一、二遍拓撲互逆，第三、四遍拓撲互逆。另外，第7）行按照存儲順序處理，當執(zhí)行第一遍拓撲后，圖的鄰接表中頂點按照拓撲號升序排序，且第二遍處理的是基于拓撲排序后的鄰接表進行處理。這么做是為了在保證互逆的基礎(chǔ)上，避免排序操作。

對圖1的G 而言，在求解正反拓撲號之前，首先刪除32個hop 點，得到簡化的圖，之后執(zhí)行算法2 后，給每個頂點賦予4個拓撲號。

給定DAG G=(V，E)，刪除32個hop點的操作可在線性時間內(nèi)完成。由于函數(shù)Construct 在執(zhí)行過程中始終沒有執(zhí)行特定的排序操作，在每次執(zhí)行函數(shù)Construct時，每個頂點v 的處理代價是，因此函數(shù)Construct 的時間復雜度是。算法2 總共調(diào)用了4 次函數(shù)Construct，因此算法2的時間復雜度是。

5 查詢

算法3 用于判定查詢的k 步可達性。其中QU(v，u，LOUT(v)，LIN(u))表示通過標簽求解得到的最短路徑長度。算法3的第1）、2）行采用hop點的最短路徑索引判定該查詢是否滿足k步可達性。具體來說：若通過最短路徑索引求得從u到v的最短路徑不大于k，說明該查詢滿足k步可達；否則若最短路徑大于k并且查詢中的頂點存在hop點，說明該查詢不滿足k 步可達性（第3）行）。若上述條件均不能判定查詢的k 步可達性，則在第4）、5）行采用正反互逆的拓撲號判定查詢的可達性：若查詢不可達，則說明該查詢不滿足k 步可達；否則，在第6）～13）行以遞歸的方式執(zhí)行遍歷操作。

算法3 kRH (u，v，k，G=(V，E))。

輸入 G=(V，E)；

輸出 true or false。

1） if QU(v，u，LOUT(v)，LIN(u))≤k

2） return true

4） if Xu＞Xvor Yu＞Yvor Mu＜Mvor Nu＜Nv

5） return false

6） if Out(u) ≤ In(v) then

7） for each p in Out(u)do

8） if kRH(p，v，k-1)

9） return true

10）else

11） for each p in In(v) do

12） if kRH(u，p，k-1)

13） return true

基于如下兩個啟發(fā)式來加速遍歷的過程。

規(guī)則3 給定k 步可達查詢的兩個端點u 和v。若u 的出度大于v 的入度，則從v 出發(fā)向上遍歷找u；否則從u 出發(fā)向下遍歷找v。

規(guī)則4 當從v 出發(fā)遍歷時，優(yōu)先選擇與其拓撲層相差大的頂點w進行遍歷。

規(guī)則4 中拓撲層相差較大，說明v 通過w 可能更快到達目標點。

6 實驗與結(jié)果分析

6.1 實驗環(huán)境

根據(jù)相關(guān)工作分析可知，在Label-Only 類算法中，PLL 查詢效率最高；在Label+G 類算法中，根據(jù)文獻［3］，BFSI-B（Breadth First Search Index-Bilateral）算法比k-reach［5］更快，是Label+G類算法中查詢效率最高的算法。因此，本文實驗中用于比較的算法有BFSI-B［3］和PLL［9］。對于Label+G中第一類方法而言，例如GRAIL，因其并非專門處理k步可達查詢，本文不再進行比較。所有算法都采用C++實現(xiàn)，并使用GCC7.3.0進行編譯。所有算法使用相同的數(shù)據(jù)集和查詢集，并在相同的平臺上運行得到實驗數(shù)據(jù)。機器配置是4 GB RAM 的Intel Core i5-3230 CPU（8 核，2.60 GHz）和Ubuntu18.04LTS。以索引規(guī)模、索引構(gòu)建時間、查詢時間作為評價指標來比較三種算法的性能。本文方法中的hop點個數(shù)是32。

6.2 實驗數(shù)據(jù)集

實驗數(shù)據(jù)集由21 個真實的數(shù)據(jù)集組成，這些數(shù)據(jù)集都廣泛地出現(xiàn)在圖論的可達性查詢研究［14-16］中，它們的統(tǒng)計信息如表4 所示。其中arxiv、citeseer、pubmed 來自引文獻［14］；cit系列的數(shù)據(jù)集來自文獻［6］，其非葉子頂點的平均出度為10到30；uniprot100m、uniprot150m 來自Uniprot 數(shù)據(jù)庫的注釋聯(lián)合 圖［15］，皆 是UniProt 的 完 整 資 源 描 述 框 架（Resource Description Framework，RDF）的子集；soc-LJ（soc-LiveJournall）是來自社會網(wǎng)絡(luò)的有向無環(huán)圖；wikiTalk是來自維基百科的有向無環(huán)圖；web-Google 是來自Google 網(wǎng)頁的有向無環(huán)圖；dbpedia 為知識圖；web-uk 是文獻［16］收集的網(wǎng)絡(luò)有向無環(huán)圖。由表4 可知，除了前5 個數(shù)據(jù)集的規(guī)模較小之外，其余數(shù)據(jù)集規(guī)模較大；|V |表示給定有向無環(huán)圖的頂點數(shù)量，|E |為邊的數(shù)量，|d |表示頂點的平均度。對于每個數(shù)據(jù)集，本文使用隨機生成的100 萬個查詢進行測試，算法的運行時間為處理100萬個查詢的總時間。

6.3 索引大小及時間

表5 和表6 分別給出了不同方法的索引大小和索引構(gòu)建時間。從索引大小來看，如表5 所示，可以看出：1）在所有數(shù)據(jù)集上，本文方法構(gòu)建的索引規(guī)模最小。2）對于規(guī)模較小的圖而言，三種方法的索引規(guī)模相差不大。3）當圖是稠密圖時，PLL 算法建立的索引規(guī)模最大。原因在于，PLL 要構(gòu)建所有點的雙向索引，而BFSI-B 的索引規(guī)模與圖的頂點個數(shù)成正比，每個頂點對應(yīng)8個整數(shù)。本文方法kRH為每個頂點設(shè)定4個拓撲號。雖然建立的是32 個hop 點的索引，但由于使用了提前終止條件以及每個hop 點關(guān)聯(lián)的頂點有限，平均到每個點，hop標簽不會超過4個數(shù)字，因此索引規(guī)模比BFSI-B小。

表4 實驗數(shù)據(jù)集統(tǒng)計信息Tab.4 Statistics of experimental datasets

表5 不同數(shù)據(jù)集上的索引大小 單位：MBTab.5 Index size on different datasets unit：MB

在索引時間方面，如表6 所示。相比PLL，kRH 算法的索引構(gòu)建時間更短，尤其當圖的規(guī)模大且稠密時更加明顯；相比BFSI-B，二者索引時間相差不大。

表6 不同數(shù)據(jù)集上的索引時間 單位：msTab.6 Index time on different datasets unit：ms

6.4 查詢時間

表7 展示了三種算法當k=3 時的查詢處理時間。由表7可知，三種方法相比，本文算法所需時間最短。原因有兩方面：一方面，和PLL 相比，本文算法可以在常量時間處理不可達查詢；另一方面，和BFSI-B相比，本文算法基于4個拓撲號，可在常量時間檢測更多的不可達查詢。由于PLL不能常量時間回答查詢，因此在表8 中和BFSI-B 比較了常量時間內(nèi)可判定的查詢個數(shù)，可以看出本文算法可在常量時間內(nèi)判定更多的查詢，因而可以獲得比BFSI-B更高的查詢響應(yīng)速度。

表7 k=3時不同數(shù)據(jù)集上的查詢時間 單位：msTab.7 Query time on different datasets when k=3 unit：ms

6.5 不同k值的查詢處理性能

圖4 分別展示了三種算法在不同特征的數(shù)據(jù)集上處理100 萬個查詢時隨k 值變化的情況?？梢钥闯?，本文方法和PLL 對k 值的變化不敏感，而BFSI-B 的性能受k 值影響較大，隨著k 值的增加，其所需的查詢處理時間增長較多。對于稀疏數(shù)據(jù)集來說，k 值的變化對于BFSI-B 和kRH 算法的查詢時間影響不大；而對于稠密數(shù)據(jù)集（go_uniprot）來說，BFSI-B 和kRH 算法的查詢時間隨著k 的增大而增加，但是BFSI-B 的增加幅度更大。這是因為kRH算法比BFSI-B覆蓋程度更高。

圖4 不同數(shù)據(jù)集上三種算法的查詢時間對比Fig.4 Query time comparison of three algorithms on different datasets

表8 k=3時常量時間內(nèi)可判定的查詢數(shù)量Tab.8 Query answers can be determined in constant time when k=3

7 結(jié)語

針對已有k 步可達查詢方法存在的索引規(guī)模大、查詢響應(yīng)速度慢的問題，本文提出通過構(gòu)建大度頂點的雙向最短路徑來提高可達查詢的覆蓋率，同時提出基于簡化圖的正反互逆拓撲來提高常量時間內(nèi)不可達查詢的處理效率。本文還提出了一系列優(yōu)化方法來減小索引規(guī)模、提高查詢處理的效率?；谡鎸崝?shù)據(jù)集的實驗結(jié)果表明，本文算法具有較小的索引規(guī)模和更快的查詢響應(yīng)速度，同時具有較好的擴展性。最好情況下，在cit-Patents數(shù)據(jù)集上，與PLL算法相比，本文算法的索引規(guī)模和索引構(gòu)建時間僅為PLL 算法3%，查詢時間僅為PLL 算法的20%；和BFSI-B 算法相比，本文算法的索引僅為BFSI-B算法索引規(guī)模、查詢時間的一半。