DFS算法在爆管分析中的优化研究

马波，赵海波，李宁

(昆明市测绘研究院，云南 昆明 650051)

DFS算法在爆管分析中的优化研究

马波*，赵海波，李宁

(昆明市测绘研究院，云南 昆明 650051)

爆管分析是城市地下管网管理中的一个重要分析功能，通用的爆管分析算法多采用基于图论、或流向原理的单一实现。由于外业采集的城市地下管网数据除排水类管线具有完整流向外，其他管线均无固定流向，所以导致这类算法在实际应用时与现实情况不相符。本文深入分析了管网数据实际情况，对爆管分析所涉及的理论、处理流程进行详细整理，针对有完整流向、无固定流向的管线采用不同的优化模型。经算法实现，验证算法在有完整流向、无固定流向情况下均能较好分析出正确的结果。

爆管；DFS；地下管网；优化

1 引 言

城市地下管线(排水、供水、燃气)爆管事故较为普遍，爆管后的抢修工作不容忽视。实现完善的爆管关阀分析功能将减少抢修时间，减少受影响范围，将因爆管而造成的损失降为最小，提高管网的现代化管理水平[1]。怎样快速、准确地分析出爆管位置最近的阀门及受影响的管线范围，为抢修人员提供快速、准确的辅助，一直是业界研究的热点问题[2]。目前一些管网系统已经不同程度的实现了爆管分析功能，但还存在着一些不足。现有的爆管分析算法一般有两种，一种是基于图论的爆管分析方法，一种是基于流向的爆管分析方法[3]。由于城市地下管网数据各自特性，外业采集的管线数据除排水能准确获得实际、完整的流向外，有些没有流向，或流向不具有实际意义。采用图论的分析方法可以忽略流向进行分析，但仅能找出可能需要关闭的阀门，由于没有用到流向，所以对于有流向的数据本身而言就丢失了“流向”这一重要数据。基于流向的分析方法能够精确地找到应关闭阀门，要分析没有流向的管线只能另想办法。对此本文结合以上两种分析方法，以流向为依据，采用图论对两者进行优化，对有流向的管线，采用有向图进行抽象，针对没有流向的管线，则采用无向图进行抽象，最后利用深度优先(DFS)算法进行应关闭的阀门与受影响管段的查找。

2 数据组织

由于爆管分析针对的对象是管网与阀门、阀门井、检修井，所以在数据组织过程中必须保证两者之间正确的拓扑关系。管网系统中通常将管线抽象为网络弧段，阀门抽象为网络的节点，网络节点位于弧段连接处。基于此，在数据组织过程中将拓扑关系简化为弧段与弧段、弧段与节点的关系[4]。

本文利用SDX+空间数据引擎对数据进行组织存储。在构网前先对参与几何网络构建的点要素、线要素进行拓扑检查，修正拓扑错误，确保构网的准确性。然后将阀门点建模为几何网络中的点要素，将管段建模为几何网络的边要素。每个节点包括节点标识号、地理位置、附属物等其他属性。每个管段包括管段标识号、地理位置、起始节点号、连接点号等属性信息。如图1所示：

图1 结点、弧段部分表结构

本文中针对的管网按照流向可以分为两类，一类是有流向的管网，即在弧段表中流向字段FLOWDIR不为空，当FLOWDIR为‘+’表示从起始管线点流向连接点，反之当FLOWDIR为‘-’时则表示从连接点流向起始管线点。另一类是没有流向的管网，即FLOWDIR为空。

3 爆管分析理论

一般说来，网络在数学和计算机领域中被抽象为图的概念，因而图论与管网拓扑结构图之间有着很自然的联系。建立逻辑网络模型拓扑关系实际上就是在逻辑网络模型的基础上抽象出无向图，然后生成管网参与进行爆管分析的所有点状要素之间的拓扑邻接关系[5]。多数文献中爆管分析的实现都是采用图的广度优先遍历算法[1，6，7]。

图的遍历要比树的遍历更为复杂，因为图的任一顶点都可能和其余的顶点相邻接。深度优先遍历类似于树的先根遍历，是树先根遍历的推广。当图中所有顶点未曾被访问，则深度遍历可以从图的某顶点出发，然后依次从该顶点邻接点出发深度遍历图，直至图中所有和该顶点有路径相同的顶点都被访问到[8]。本文中由于涉及两种类型管线，所以涉及有向图与无向图的遍历。对于有向图而言，按照方向进行查找，对于无向图而言，由用户指定查找方向后进行查找。

针对管段有流向与否其实都可以利用无向图模型进行实现。但是就有流向的管段而言，采用无向图模型进行分析导致遍历路程增加，在算法上体现出来的结果就是一次分析时间增长，而如果仅仅利用有向图模型则只能针对有流向的管段，那么这样的算法就有局限性。综合以上，本文算法在拾取管段时先判断管段有无流向，若有流向则使用有向图模型进行遍历，无流向则采用无向图进行遍历。这样算法不仅更具有健壮性，同时在算法分析时间上面也会有所减少。

4 算法设计与优化

爆管分析功能按照查找对象来划分，可分为两个部分，第一部分为需要关闭的阀门(包括阀门、阀门井、检修井等)，第二部分为受影响管线段。本算法的实现以搜索上游最邻近阀门为最终目的，结合深度优先遍历(DFS)的算法思想设计。整个算法的核心思想就是对“上游”管点进行递归迭代，直到找到满足条件的阀门。以下分为有流向和无流向来说明。

4.1 有流向管段关阀分析

应关闭阀门查找具体步骤如下：

①获得爆管点所在的管段；

②获得该管段流向，根据流向获取其“上游节点”(若该管段的流向为“+”，则其上游为该管段的起始节点，如果该管段的流向为“-”，则其上游为该管段的连接节点)；

③判断该节点是否为阀门。如果为阀门，结束整个搜索流程。如果不是阀门，继续根据其流向搜索“上游节点”，直至所有“上游阀门”找到为止。

大多数爆管分析功能的实现仅仅分析查找出最邻近关闭的阀门，本文在此基础上增加了受影响管线段的查找，与阀门的查找方向不同，受影响管线段位于爆管点下游。该功能的实现不仅使得爆管分析功能更加完善，而且能形象展示由于某个管段爆管而影响的范围区域，为相关决策的指定提供帮助。该功能的具体实现步骤如下：

受影响管段查找具体步骤如下：

①获得爆管点所在的管段；

②得该管段流向，根据流向获取其“下游方向”，查找其下游管段，根据递归的方法查找出所有受影响管段。

以上两个步骤具体可以如图2所示。

图2 有流向爆管阀门搜索流程图

4.2 无流向管段关阀分析

针对没有流向的管线段而言，因其丢失了流向信息，所以我们只能通过人为的指定一个流向信息让发生爆管的管段具备“流向”，这样就可以使得发生爆管的管段拥有了上游和下游的概念。同时由于管段丢失了“流向”信息，所以在管网的组织中，其起始点与连接点往往是很复杂，很凌乱的，所以这里以一个例子来模拟本文所使用的查询算法。

如图3所示代表一段实际情况中所遇到的“无流向”管线，其中每段管线起始节点用实心圆表示，而连接节点则用三角形表示。假设此时用户指定查找方向为上游，即查找管段C起始节点P3上游的所有阀门。所以查找上游阀门点的具体步骤如下所示：

图3 一段“无流向”管网模拟

①查找上游，即找到起始节点，判断是否为阀门，如果是阀门则停止搜索，否则继续搜索；

②找到所有以P3上游方向(P3为起点或终点)且没有访问过的管段；

③在B、F管段中找到没有访问过的管点并判断是否为阀门如果是阀门，则停止搜索，否则继续搜索；

④找到所有以P7为起点或终点(P3上游方向)且没有访问过的管段；

⑤在G、H管段中找到没有访问过得管点并判断是否为阀门如果是阀门，停止搜索，否则继续搜索。

由于采用深度优先(DFS)算法，所以算法执行顺序为：P3→B→P2→F→P7→G→P8→H→P9，注意：B、F和G、H的优先性是随机的。具体流程图如图4所示。

图4 “上游阀门点”搜索流程

查找下游受影响管线段的流程如下所示：

①查找下游，即找到连接节点；

②找到所有以P4下游方向(P4为起点或终点)且没有访问过的管段；

③在管线D中找到其没有访问过的节点；

④找到所有以P5为起点或终点(P4下游方向)且没有访问过的管段；

⑤分别在E、I中找到没有访问过的节点；

⑥找到所有以P6、P10为起点或终点(P4下游方向)且没有访问过的管段。

由于采用深度优先(DFS)算法，所以算法执行顺序为：P4→D→P5→E→P6→K→I→P10→J，注意：E、I的优先性是随机的。具体流程图如图5所示：

图5 “下游受影响管线”搜索流程

5 算法验证

本文采用的开发软件为Visual Studio 2010开发环境，采用的开发语言为C#，采用的二次开发组件包为iObject8C。在管线数据存储方面，采用SuperMap SDX+空间数据引擎将数据存储在Postgresql9.4数据库中。基于深度优先遍历(DFS)算法实现的爆管分析应用在地图、三维场景中，实现了地图、场景与业务的联动，并且能够快捷查询受影响管线段。如图6(a)所示为燃气管线的爆管分析，由于燃气管线没有流向，所以在分析的过程中需要用户选取查找上游影响管段(相应的应关闭阀门位于下游)或者查找下游受影响管段(相应的应关闭阀门位于上游)，而如图6(b)所示则为排水管网的爆管分析结果，由于排水管网有流向，所以不需要用户自行选取分析方向，自动按照流向进行分析。图7(a)(b)对应图6(a)(b)在三维场景中的分析结果。

图6 爆管分析结果图(无流向)

图7 爆管分析结果图(无流向)

6 结 论

本文根据城市地下管线数据特点和爆管分析的需要基于图论与拓扑网络模型，优化了DFS算法模型。本文算法不仅找出应关闭阀门点，还找出了所有受影响管段，且能适应管段有无固定流向，针对不同情况采用不同模型。与其他算法相比较，实际应用效果表明了该算法的可行性和有效性，结果更符合实际情况。

[1] 胡新玲，张宏飞. 供水管网地理信息系统中爆管分析的算法研究[J]. 测绘科学，2008，33(4)：225～226.

[2] 杨姗姗. 供水管网地理信息系统中爆管分析的设计与实现[D]. 武汉：武汉大学，2005.

[3] 王卫兵，于志斌，田春伟等. 供水管网爆管分析算法及其GIS组件的实现[J]. 哈尔滨理工大学学报，2015，20(4)：122～126.

[4] 李平，李永树. 基于流向的管网爆管分析算法[J]. 计算机应用，2012，32(z2)：45～47.

[5] 林伟华，伍永刚，曾文等. 燃气管网爆管分析模型研究[J]. 测绘科学，2007，32(6)：162～163.

[6] 张会. 基于GIS技术的地下管线爆管分析优化算法[J]. 信息技术与信息化，2014(7)：82～84.

[7] 王方雄，崔羽. 基于GIS的管网爆管分析算法优化与实现[J]. 武汉理工大学学报·交通科学与工程版，2012，36(3)：575～578.

[8] 严蔚敏，吴伟明. 数据结构(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—)，男，高级工程师，总工程师，主要从事测绘、地理信息技术开发及管理工作。

昆明市科技计划项目(昆科计字2015-1-G-00972)