[發明專利]基于廣度優先搜索算法的管網空間分析方法

在審

• 申請號: 201510648981.5
• 申請日: 2015-10-09
• 公開（公告）號: CN105225187A
• 公開（公告）日: 2016-01-06
• 發明（設計）人: 楊俊;魯雪松;汪小東;曾書昶;鈕立明;陳建偉
• 申請（專利權）人: 蘇州盛景信息科技股份有限公司
• 主分類號: G06Q50/26
• 分類號: G06Q50/26;G06F17/30
• 代理公司: 蘇州慧通知識產權代理事務所(普通合伙) 32239
• 代理人: 黃建月

技術領域

本發明涉及一種管網分析技術，尤其是涉及一種基于廣度優先搜索算法的管網空間分析方法。

背景技術

城市管網錯綜復雜且與生活密切關聯，智慧城市概念的普及加大了對空間管網技術的要求，對webGIS技術的使用加強。隨著需求的不斷擴大，市場上推出一些較為專業的管網系統，如ESRI(美國環境系統研究所公司，EnvironmentalSystemsResearchInstituteInc，簡稱ESRI公司)的ArcFM，它可以有效管理電力、煤氣、排水、給水、石油等城市管網。西方國家嘗試將物聯網、人工智能同現有的城市管網結合，實現更具準確性、高效性的空間分析，將管線數據和分析結果進行聯網使用。國內城市管網webGIS應用程序多以SOAP(SimpleObjectAccessProtocol，簡單對象訪問協議)進行WEB服務，并將應用封裝起來，這樣可以靈活組織網絡資源與數據。

2002年，馬先立基于MapGIS平臺的二次開發組件結合ASP技術進行開發，并實現簡單的管網查詢功能。2004年，東野長磊運用ActiveX技術實現量算、管網信息統計功能。2008年，Fielding提出的REST技術得到人們的普遍認識與接受，推動了技術的發展進行。2013年，王印通使用AJAX技術、MapXtreme技術和OracleSpatial數據庫等技術實現爆管分析和連通分析。

目前，城市已經完成工業化、電氣化、信息化，智慧化緊隨其后，是世界發展的前沿趨勢。但是我國對城市管網的數字化研究起步比較晚，城市管網雖然可以滿足一般需求，但是在運行中還是存在一些不足：第一，數據組織缺少嚴格規范標準，影響分析功能的準確性及效率。第二，城市管網的網絡分析功能較少，對數據的空間查詢和屬性查詢研究較多。第三，城市管網的用戶體驗的提升空間很大，包括系統響應速度、操作方式、界面設計等。第四，基礎空間分析方法與其他非管網的webGIS分析方法類似，且實現技術相對成熟，研究重點逐漸轉向管網空間分析方法上。第五，核心算法與非Web的空間分析算法類似，較于桌面管網系統的管網webGIS的空間分析方法在技術上稍顯滯后。

發明內容

本發明的目的在于克服現有技術的缺陷，提供一種基于廣度優先搜索算法的管網空間分析方法，以探索管網在有向圖的廣度優先遍歷算法的分析計算。

為實現上述目的，本發明提出如下技術方案：一種基于廣度優先搜索算法的管網空間分析方法，包括：以源點V0向外擴展，首先訪問到的距離為K，未被訪問的鄰接頂點為V1，V2，V3，……Vn，再以這些頂點為中心，訪問與源點V0距離為K+1的其他未被訪問的頂點，直到全部頂點被訪問完為止，其中，n為大于1的整數，以實現管網的連通分析、爆管分析、最短路徑分析和剖面分析。

優選地，所述廣度優先搜索算法包括記錄路徑的連通分析算法、排除可關可不關閥門的爆管分析算法、最短路徑算法以及剖面分析算法。

優選地，所述連通分析方法中，將管網中的所有頂點分為已經搜索過的頂點、即將搜索的鄰接頂點、從未遍歷的頂點，所述連通分析方法的過程包括：

步驟1，輸入起點V0，并將所述起點V0加入即將搜索的鄰接頂點序列；

步驟2，判斷即將搜索的鄰接頂點序列中是否有值，若有，則從所述即將搜索的鄰接頂點序列中取出一個頂點Vn，將頂點Vn加入所述已經搜索過的頂點序列中，并取出頂點Vn所有上游相鄰且未被訪問的頂點Vw，將Vn和Vw記錄到路徑；

步驟3，判斷是否有終點V1，若有，則繼續進入步驟2，若沒有，則將頂點Vw加入即將搜索的鄰接頂點序列中，并進入步驟2。

優選地，步驟2中，若即將搜索的鄰接頂點序列中沒有值，則判斷是否找到目標點，若找到，則保留路徑并結束遍歷，若未找到，則清空路徑并結束遍歷。

優選地，所述爆管分析算法通過獲取閥門點集合V，然后對其進行判斷分析，進行排除，設V＝{V0，V1，V2……Vn}，若V0在下游存在一個或多個閥門，則V1、V2……Vn為可關可不關閥門，所述爆管分析算法包括：

起始點為V中閥門點，采用廣度優先搜索算法搜索其下游節點，若此節點屬于集合V，將其移出集合V添加到可關可不關閥門集合VA中，并將起始點的下游最近閥門列入可關可不關閥門。

優選地，所述最短路徑分析算法采用單源最短路徑算法計算管網有向圖中兩個頂點的最短路徑。

優選地，所述剖面分析算法包括橫剖面分析算法和縱剖面分析算法。