DFS算法在爆管分析中的優(yōu)化研究

馬波，趙海波，李寧

(昆明市測繪研究院，云南 昆明 650051)

DFS算法在爆管分析中的優(yōu)化研究

馬波*，趙海波，李寧

(昆明市測繪研究院，云南 昆明 650051)

爆管分析是城市地下管網(wǎng)管理中的一個重要分析功能，通用的爆管分析算法多采用基于圖論、或流向原理的單一實現(xiàn)。由于外業(yè)采集的城市地下管網(wǎng)數(shù)據(jù)除排水類管線具有完整流向外，其他管線均無固定流向，所以導致這類算法在實際應用時與現(xiàn)實情況不相符。本文深入分析了管網(wǎng)數(shù)據(jù)實際情況，對爆管分析所涉及的理論、處理流程進行詳細整理，針對有完整流向、無固定流向的管線采用不同的優(yōu)化模型。經(jīng)算法實現(xiàn)，驗證算法在有完整流向、無固定流向情況下均能較好分析出正確的結果。

爆管；DFS；地下管網(wǎng)；優(yōu)化

1 引 言

城市地下管線(排水、供水、燃氣)爆管事故較為普遍，爆管后的搶修工作不容忽視。實現(xiàn)完善的爆管關閥分析功能將減少搶修時間，減少受影響范圍，將因爆管而造成的損失降為最小，提高管網(wǎng)的現(xiàn)代化管理水平[1]。怎樣快速、準確地分析出爆管位置最近的閥門及受影響的管線范圍，為搶修人員提供快速、準確的輔助，一直是業(yè)界研究的熱點問題[2]。目前一些管網(wǎng)系統(tǒng)已經(jīng)不同程度的實現(xiàn)了爆管分析功能，但還存在著一些不足?，F(xiàn)有的爆管分析算法一般有兩種，一種是基于圖論的爆管分析方法，一種是基于流向的爆管分析方法[3]。由于城市地下管網(wǎng)數(shù)據(jù)各自特性，外業(yè)采集的管線數(shù)據(jù)除排水能準確獲得實際、完整的流向外，有些沒有流向，或流向不具有實際意義。采用圖論的分析方法可以忽略流向進行分析，但僅能找出可能需要關閉的閥門，由于沒有用到流向，所以對于有流向的數(shù)據(jù)本身而言就丟失了“流向”這一重要數(shù)據(jù)?；诹飨虻姆治龇椒軌蚓_地找到應關閉閥門，要分析沒有流向的管線只能另想辦法。對此本文結合以上兩種分析方法，以流向為依據(jù)，采用圖論對兩者進行優(yōu)化，對有流向的管線，采用有向圖進行抽象，針對沒有流向的管線，則采用無向圖進行抽象，最后利用深度優(yōu)先(DFS)算法進行應關閉的閥門與受影響管段的查找。

2 數(shù)據(jù)組織

由于爆管分析針對的對象是管網(wǎng)與閥門、閥門井、檢修井，所以在數(shù)據(jù)組織過程中必須保證兩者之間正確的拓撲關系。管網(wǎng)系統(tǒng)中通常將管線抽象為網(wǎng)絡弧段，閥門抽象為網(wǎng)絡的節(jié)點，網(wǎng)絡節(jié)點位于弧段連接處?；诖?，在數(shù)據(jù)組織過程中將拓撲關系簡化為弧段與弧段、弧段與節(jié)點的關系[4]。

本文利用SDX+空間數(shù)據(jù)引擎對數(shù)據(jù)進行組織存儲。在構網(wǎng)前先對參與幾何網(wǎng)絡構建的點要素、線要素進行拓撲檢查，修正拓撲錯誤，確保構網(wǎng)的準確性。然后將閥門點建模為幾何網(wǎng)絡中的點要素，將管段建模為幾何網(wǎng)絡的邊要素。每個節(jié)點包括節(jié)點標識號、地理位置、附屬物等其他屬性。每個管段包括管段標識號、地理位置、起始節(jié)點號、連接點號等屬性信息。如圖1所示：

圖1 結點、弧段部分表結構

本文中針對的管網(wǎng)按照流向可以分為兩類，一類是有流向的管網(wǎng)，即在弧段表中流向字段FLOWDIR不為空，當FLOWDIR為‘+’表示從起始管線點流向連接點，反之當FLOWDIR為‘-’時則表示從連接點流向起始管線點。另一類是沒有流向的管網(wǎng)，即FLOWDIR為空。

3 爆管分析理論

一般說來，網(wǎng)絡在數(shù)學和計算機領域中被抽象為圖的概念，因而圖論與管網(wǎng)拓撲結構圖之間有著很自然的聯(lián)系。建立邏輯網(wǎng)絡模型拓撲關系實際上就是在邏輯網(wǎng)絡模型的基礎上抽象出無向圖，然后生成管網(wǎng)參與進行爆管分析的所有點狀要素之間的拓撲鄰接關系[5]。多數(shù)文獻中爆管分析的實現(xiàn)都是采用圖的廣度優(yōu)先遍歷算法[1，6，7]。

圖的遍歷要比樹的遍歷更為復雜，因為圖的任一頂點都可能和其余的頂點相鄰接。深度優(yōu)先遍歷類似于樹的先根遍歷，是樹先根遍歷的推廣。當圖中所有頂點未曾被訪問，則深度遍歷可以從圖的某頂點出發(fā)，然后依次從該頂點鄰接點出發(fā)深度遍歷圖，直至圖中所有和該頂點有路徑相同的頂點都被訪問到[8]。本文中由于涉及兩種類型管線，所以涉及有向圖與無向圖的遍歷。對于有向圖而言，按照方向進行查找，對于無向圖而言，由用戶指定查找方向后進行查找。

針對管段有流向與否其實都可以利用無向圖模型進行實現(xiàn)。但是就有流向的管段而言，采用無向圖模型進行分析導致遍歷路程增加，在算法上體現(xiàn)出來的結果就是一次分析時間增長，而如果僅僅利用有向圖模型則只能針對有流向的管段，那么這樣的算法就有局限性。綜合以上，本文算法在拾取管段時先判斷管段有無流向，若有流向則使用有向圖模型進行遍歷，無流向則采用無向圖進行遍歷。這樣算法不僅更具有健壯性，同時在算法分析時間上面也會有所減少。

4 算法設計與優(yōu)化

爆管分析功能按照查找對象來劃分，可分為兩個部分，第一部分為需要關閉的閥門(包括閥門、閥門井、檢修井等)，第二部分為受影響管線段。本算法的實現(xiàn)以搜索上游最鄰近閥門為最終目的，結合深度優(yōu)先遍歷(DFS)的算法思想設計。整個算法的核心思想就是對“上游”管點進行遞歸迭代，直到找到滿足條件的閥門。以下分為有流向和無流向來說明。

4.1 有流向管段關閥分析

應關閉閥門查找具體步驟如下：

①獲得爆管點所在的管段；

②獲得該管段流向，根據(jù)流向獲取其“上游節(jié)點”(若該管段的流向為“+”，則其上游為該管段的起始節(jié)點，如果該管段的流向為“-”，則其上游為該管段的連接節(jié)點)；

③判斷該節(jié)點是否為閥門。如果為閥門，結束整個搜索流程。如果不是閥門，繼續(xù)根據(jù)其流向搜索“上游節(jié)點”，直至所有“上游閥門”找到為止。

大多數(shù)爆管分析功能的實現(xiàn)僅僅分析查找出最鄰近關閉的閥門，本文在此基礎上增加了受影響管線段的查找，與閥門的查找方向不同，受影響管線段位于爆管點下游。該功能的實現(xiàn)不僅使得爆管分析功能更加完善，而且能形象展示由于某個管段爆管而影響的范圍區(qū)域，為相關決策的指定提供幫助。該功能的具體實現(xiàn)步驟如下：

受影響管段查找具體步驟如下：

①獲得爆管點所在的管段；

②得該管段流向，根據(jù)流向獲取其“下游方向”，查找其下游管段，根據(jù)遞歸的方法查找出所有受影響管段。

以上兩個步驟具體可以如圖2所示。

圖2 有流向爆管閥門搜索流程圖

4.2 無流向管段關閥分析

針對沒有流向的管線段而言，因其丟失了流向信息，所以我們只能通過人為的指定一個流向信息讓發(fā)生爆管的管段具備“流向”，這樣就可以使得發(fā)生爆管的管段擁有了上游和下游的概念。同時由于管段丟失了“流向”信息，所以在管網(wǎng)的組織中，其起始點與連接點往往是很復雜，很凌亂的，所以這里以一個例子來模擬本文所使用的查詢算法。

如圖3所示代表一段實際情況中所遇到的“無流向”管線，其中每段管線起始節(jié)點用實心圓表示，而連接節(jié)點則用三角形表示。假設此時用戶指定查找方向為上游，即查找管段C起始節(jié)點P3上游的所有閥門。所以查找上游閥門點的具體步驟如下所示：

圖3 一段“無流向”管網(wǎng)模擬

①查找上游，即找到起始節(jié)點，判斷是否為閥門，如果是閥門則停止搜索，否則繼續(xù)搜索；

②找到所有以P3上游方向(P3為起點或終點)且沒有訪問過的管段；

③在B、F管段中找到?jīng)]有訪問過的管點并判斷是否為閥門如果是閥門，則停止搜索，否則繼續(xù)搜索；

④找到所有以P7為起點或終點(P3上游方向)且沒有訪問過的管段；

⑤在G、H管段中找到?jīng)]有訪問過得管點并判斷是否為閥門如果是閥門，停止搜索，否則繼續(xù)搜索。

由于采用深度優(yōu)先(DFS)算法，所以算法執(zhí)行順序為：P3→B→P2→F→P7→G→P8→H→P9，注意：B、F和G、H的優(yōu)先性是隨機的。具體流程圖如圖4所示。

圖4 “上游閥門點”搜索流程

查找下游受影響管線段的流程如下所示：

①查找下游，即找到連接節(jié)點；

②找到所有以P4下游方向(P4為起點或終點)且沒有訪問過的管段；

③在管線D中找到其沒有訪問過的節(jié)點；

④找到所有以P5為起點或終點(P4下游方向)且沒有訪問過的管段；

⑤分別在E、I中找到?jīng)]有訪問過的節(jié)點；

⑥找到所有以P6、P10為起點或終點(P4下游方向)且沒有訪問過的管段。

由于采用深度優(yōu)先(DFS)算法，所以算法執(zhí)行順序為：P4→D→P5→E→P6→K→I→P10→J，注意：E、I的優(yōu)先性是隨機的。具體流程圖如圖5所示：

圖5 “下游受影響管線”搜索流程

5 算法驗證

本文采用的開發(fā)軟件為Visual Studio 2010開發(fā)環(huán)境，采用的開發(fā)語言為C#，采用的二次開發(fā)組件包為iObject8C。在管線數(shù)據(jù)存儲方面，采用SuperMap SDX+空間數(shù)據(jù)引擎將數(shù)據(jù)存儲在Postgresql9.4數(shù)據(jù)庫中?；谏疃葍?yōu)先遍歷(DFS)算法實現(xiàn)的爆管分析應用在地圖、三維場景中，實現(xiàn)了地圖、場景與業(yè)務的聯(lián)動，并且能夠快捷查詢受影響管線段。如圖6(a)所示為燃氣管線的爆管分析，由于燃氣管線沒有流向，所以在分析的過程中需要用戶選取查找上游影響管段(相應的應關閉閥門位于下游)或者查找下游受影響管段(相應的應關閉閥門位于上游)，而如圖6(b)所示則為排水管網(wǎng)的爆管分析結果，由于排水管網(wǎng)有流向，所以不需要用戶自行選取分析方向，自動按照流向進行分析。圖7(a)(b)對應圖6(a)(b)在三維場景中的分析結果。

圖6 爆管分析結果圖(無流向)

圖7 爆管分析結果圖(無流向)

6 結 論

本文根據(jù)城市地下管線數(shù)據(jù)特點和爆管分析的需要基于圖論與拓撲網(wǎng)絡模型，優(yōu)化了DFS算法模型。本文算法不僅找出應關閉閥門點，還找出了所有受影響管段，且能適應管段有無固定流向，針對不同情況采用不同模型。與其他算法相比較，實際應用效果表明了該算法的可行性和有效性，結果更符合實際情況。

[1] 胡新玲，張宏飛. 供水管網(wǎng)地理信息系統(tǒng)中爆管分析的算法研究[J]. 測繪科學，2008，33(4)：225～226.

[2] 楊姍姍. 供水管網(wǎng)地理信息系統(tǒng)中爆管分析的設計與實現(xiàn)[D]. 武漢：武漢大學，2005.

[3] 王衛(wèi)兵，于志斌，田春偉等. 供水管網(wǎng)爆管分析算法及其GIS組件的實現(xiàn)[J]. 哈爾濱理工大學學報，2015，20(4)：122～126.

[4] 李平，李永樹. 基于流向的管網(wǎng)爆管分析算法[J]. 計算機應用，2012，32(z2)：45～47.

[5] 林偉華，伍永剛，曾文等. 燃氣管網(wǎng)爆管分析模型研究[J]. 測繪科學，2007，32(6)：162～163.

[6] 張會. 基于GIS技術的地下管線爆管分析優(yōu)化算法[J]. 信息技術與信息化，2014(7)：82～84.

[7] 王方雄，崔羽. 基于GIS的管網(wǎng)爆管分析算法優(yōu)化與實現(xiàn)[J]. 武漢理工大學學報·交通科學與工程版，2012，36(3)：575～578.

[8] 嚴蔚敏，吳偉明. 數(shù)據(jù)結構(C語言版)[M]. 北京：清華大學出版社，2011.

The Optimization Study of DFS Algorithm for Pipe Burst Analysis

Ma Bo，Zhao Haibo，Li Ning

(Kunming Surveying and Mapping Institute，Kunming 650051，China)

Tube bursting analysis is one of the most important functions in the management of urban underground pipe network.Because the city underground pipe network data collected by the external industry has a complete flow outward，other pipelines have no fixed flow，so the algorithm is not consistent with the actual situation in the practical application.In this paper，the actual situation of pipe network data is analyzed in detail，and the theory and process flow are analyzed in detail. After algorithm implementation，the verification algorithm can better analyze the correct results in the case of complete flow direction and no fixed flow direction.

tube bursting analysis；DFS；underground pipe network；optimization

1672-8262(2016)06-23-04

P208.1

A

2016—09—14

馬波(1979—)，男，高級工程師，總工程師，主要從事測繪、地理信息技術開發(fā)及管理工作。

昆明市科技計劃項目(昆科計字2015-1-G-00972)