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

馬波，趙海波，李寧

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

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

馬波*，趙海波，李寧

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

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

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

1 引 言

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

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

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

本文利用SDX+空間數(shù)據(jù)引擎對(duì)數(shù)據(jù)進(jìn)行組織存儲(chǔ)。在構(gòu)網(wǎng)前先對(duì)參與幾何網(wǎng)絡(luò)構(gòu)建的點(diǎn)要素、線要素進(jìn)行拓?fù)錂z查，修正拓?fù)溴e(cuò)誤，確保構(gòu)網(wǎng)的準(zhǔn)確性。然后將閥門(mén)點(diǎn)建模為幾何網(wǎng)絡(luò)中的點(diǎn)要素，將管段建模為幾何網(wǎng)絡(luò)的邊要素。每個(gè)節(jié)點(diǎn)包括節(jié)點(diǎn)標(biāo)識(shí)號(hào)、地理位置、附屬物等其他屬性。每個(gè)管段包括管段標(biāo)識(shí)號(hào)、地理位置、起始節(jié)點(diǎn)號(hào)、連接點(diǎn)號(hào)等屬性信息。如圖1所示：

圖1 結(jié)點(diǎn)、弧段部分表結(jié)構(gòu)

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

3 爆管分析理論

一般說(shuō)來(lái)，網(wǎng)絡(luò)在數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域中被抽象為圖的概念，因而圖論與管網(wǎng)拓?fù)浣Y(jié)構(gòu)圖之間有著很自然的聯(lián)系。建立邏輯網(wǎng)絡(luò)模型拓?fù)潢P(guān)系實(shí)際上就是在邏輯網(wǎng)絡(luò)模型的基礎(chǔ)上抽象出無(wú)向圖，然后生成管網(wǎng)參與進(jìn)行爆管分析的所有點(diǎn)狀要素之間的拓?fù)溧徑雨P(guān)系[5]。多數(shù)文獻(xiàn)中爆管分析的實(shí)現(xiàn)都是采用圖的廣度優(yōu)先遍歷算法[1，6，7]。

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

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

4 算法設(shè)計(jì)與優(yōu)化

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

4.1 有流向管段關(guān)閥分析

應(yīng)關(guān)閉閥門(mén)查找具體步驟如下：

①獲得爆管點(diǎn)所在的管段；

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

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

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

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

①獲得爆管點(diǎn)所在的管段；

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

以上兩個(gè)步驟具體可以如圖2所示。

圖2 有流向爆管閥門(mén)搜索流程圖

4.2 無(wú)流向管段關(guān)閥分析

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

如圖3所示代表一段實(shí)際情況中所遇到的“無(wú)流向”管線，其中每段管線起始節(jié)點(diǎn)用實(shí)心圓表示，而連接節(jié)點(diǎn)則用三角形表示。假設(shè)此時(shí)用戶指定查找方向?yàn)樯嫌危床檎夜芏蜟起始節(jié)點(diǎn)P3上游的所有閥門(mén)。所以查找上游閥門(mén)點(diǎn)的具體步驟如下所示：

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

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

②找到所有以P3上游方向(P3為起點(diǎn)或終點(diǎn))且沒(méi)有訪問(wèn)過(guò)的管段；

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

④找到所有以P7為起點(diǎn)或終點(diǎn)(P3上游方向)且沒(méi)有訪問(wèn)過(guò)的管段；

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

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

圖4 “上游閥門(mén)點(diǎn)”搜索流程

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

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

②找到所有以P4下游方向(P4為起點(diǎn)或終點(diǎn))且沒(méi)有訪問(wèn)過(guò)的管段；

③在管線D中找到其沒(méi)有訪問(wèn)過(guò)的節(jié)點(diǎn)；

④找到所有以P5為起點(diǎn)或終點(diǎn)(P4下游方向)且沒(méi)有訪問(wèn)過(guò)的管段；

⑤分別在E、I中找到?jīng)]有訪問(wèn)過(guò)的節(jié)點(diǎn)；

⑥找到所有以P6、P10為起點(diǎn)或終點(diǎn)(P4下游方向)且沒(méi)有訪問(wèn)過(guò)的管段。

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

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

5 算法驗(yàn)證

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

圖6 爆管分析結(jié)果圖(無(wú)流向)

圖7 爆管分析結(jié)果圖(無(wú)流向)

6 結(jié) 論

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

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

[2] 楊?yuàn)檴? 供水管網(wǎng)地理信息系統(tǒng)中爆管分析的設(shè)計(jì)與實(shí)現(xiàn)[D]. 武漢：武漢大學(xué)，2005.

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

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

[5] 林偉華，伍永剛，曾文等. 燃?xì)夤芫W(wǎng)爆管分析模型研究[J]. 測(cè)繪科學(xué)，2007，32(6)：162～163.

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

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

[8] 嚴(yán)蔚敏，吳偉明. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M]. 北京：清華大學(xué)出版社，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—)，男，高級(jí)工程師，總工程師，主要從事測(cè)繪、地理信息技術(shù)開(kāi)發(fā)及管理工作。

昆明市科技計(jì)劃項(xiàng)目(昆科計(jì)字2015-1-G-00972)