管网3DG lS的连通分析方法与实现*

刘子恒，侯英姿，王方雄，张 翔（1.辽宁师范大学辽宁省自然地理与空间信息科学重点实验室，辽宁大连116029；2.辽宁师范大学城市与环境学院，辽宁大连116029；.大连市城市规划设计研究院，辽宁大连116011）

管网3DG lS的连通分析方法与实现*

刘子恒1，2，侯英姿1，2，王方雄1，2，张 翔3
（1.辽宁师范大学辽宁省自然地理与空间信息科学重点实验室，辽宁大连116029；2.辽宁师范大学城市与环境学院，辽宁大连116029；3.大连市城市规划设计研究院，辽宁大连116011）

研究了城市管网3DGIS的连通分析方法，利用广度优先搜索算法根据管网流向信息进行正向和反向搜索来遍历管网结点，基于SuPerMaP iObjects开发实现了管网3DGIS的连通性分析、上下游追踪、共同上下游查找、最短路径分析、查找源和汇等连通分析功能。

连通分析；广度优先遍历算法；SuPerMaP iObjects；管网3DGIS

O 引言

随着城市建设步伐的加快，城市管网系统建设愈加庞杂，而管网连通性分析的可靠性和便捷性对可燃、易爆等管网系统的管理维护要求更加严格。在计算管网可靠性上，不同时期不同学者对城市管网的连通性进行了大量研究［1］。参考文献［2］在MaPInfo中实现了以图论为基础的动态淘汰算法的管网连通分析，但对有向管网的流向来源没有说明；参考文献［3］通过对数据结构变更来改写图的连通性算法以缩短运算时间，提高网络连通可靠性；参考文献［4］通过图论和模糊数学理论解决管网连通可靠性问题。为了更好地实现管网连通分析下的追踪分析、路径分析，解决连通分析中的管网流向和网络拓扑关系，本文以设施网络模型为基础，依靠管网有向图和管网邻接矩阵模型，将广度优先遍历（BFS）算法与SuPerMaP iObjects组件技术相结合，实现管网连通分析功能。

1 管网连通分析方法

1.1 设施网络模型

设施网络模型（Bui1dNetwork）是指根据网络中的拓扑关系以及源和汇的网络位置确定介质流向，按照一定的拓扑规则建立的网络模型。管网的设施网络模型采用管网逻辑模型和管网几何模型来表达管网拓扑信息和管网流向。SuPerMaP SDX+空间数据库引擎采用图库与分布式空间数据存储方式，存储各种关系的空间几何对象，支持拓扑关系和三维数据存储能力，形成空间数据和几何数据一体化的空间数据库。管网逻辑模型由管网结点数据和弧段数据拓扑构网而成，利用属性表信息来表达网络的连通性，具体可以通过数据集一对一和一对多的ID关联值来表达逻辑模型和几何模型中弧段（Edge）数据集和结点（Node）数据集的拓扑关系［5］。然后将管网模型中的阀门点、检修井等构建为管网几何模型中的节点数据集，将管网模型中的管线构建为几何模型中的弧段数据集，管网中介质的流向以源、汇数据集的网络位置确定，以Direction字段值表示。在构建设施网络模型时，根据管网源（source）、汇点（sink）的几何信息创建管网数据集的Bui1dNetwork，自动创建Direction属性字段（如图1（b））。

1.2 管网邻接矩阵

广度优先搜索算法（Breadth-First Search，BFS）是管网空间分析常用的一种方法，目的是遍历图中所有结点进行目标查询，并以此为基础衍生出其他算法［6］。BFS算法实质上是以源点W为起点，向外搜索与起点距离为d（1，2，3，…）的未被访问的邻接顶点P1，P2，P3，…，Pi，然后分别以这些顶点为起点搜索距离为d +1的其他未被搜索过的顶点，直到所有顶点都被搜索到为止。

所有管网在遍历时要以有向图为基础，构建非对称矩阵。通过设施网络模型可以构建管网有向图，并根据流向信息对管网的每条管道构建非对称矩阵，其中管道环路在矩阵中是对称的。管网邻接矩阵的建立过程如下：（1）定义管网模型的起始点、终止点和流向字段信息；（2）根据管网有向图图例，表达管网介质流动方向，即包括起点到终点、终点到起点、管网环路、不连通等；（3）结合设施网络模型Direction字段值与流向关系，构建邻接矩阵S，图内管点间关系用二维数组S［m］［n］存储，m，n表示管点序号；（4）根据广度优先搜索算法，当S［m］［n］=1时，则有流向Pm→Pn。以管点0为起点，在邻接矩阵中有S［0］［3］=0，S［3］［0］=1，判断管点0的上游是管点3，不参与搜索，则BFS算法下的管网有向图遍历顺序为0 -1 -2 -4 -5。管网有向图邻接矩阵的建立过程如图1所示。

图1 管网有向图邻接矩阵的建立过程

1.3 管网连通分析算法

通过BFS算法搜索每个管点是否为目标点来判断管网的连通性，而对于有向管网来说，在判断管段两端的管网是否连通的基础上，还需标识出管点的连通路径［7］。根据管网流向特征，如果某段管线连通，则该连通管段下游管段的所有上游管段均经过该管段，即利用BFS算法反向搜索管点并记录管段连通的路径［8］。搜索与起点P0邻接的上游管点，当S［m］［0］=1时，则Pm的上游邻接管点为P0，这在管网环路中同样成立，BFS算法反向搜索具体流程如图2（cmPPoint为已搜索过的管点，wi1Point为即将搜索的邻接管点，nonPoint为未搜索过的管点）。

2 管网连通分析功能实现

城市燃气管网连通分析功能的实现以SuPerMaP iObjects组件技术为支撑，在有向管网邻接矩阵的基础上，通过管网设施网络数据模型，以BFS算法为基础根据管网流向进行正向和反向搜索，实现管网系统的连通性分析、上下游追踪、共同上下游查找、最短路径分析、查找源和汇等。

图2 连通分析流程图

2.1 管网连通性分析

连通性分析主要是判断管点间管网的连通性，通过利用BFS算法判断燃气管网的两个管点之间是否连通，并在MaPContro1中标识出连通的路径。根据流向字段信息关系（SmFNode、SmTNode、Direction），用二维数组array记录所有管网邻接矩阵的管点，通过调用Faci1ityAna1ystResu1t类的FindPathFromNodes方法获取SmFNode、SmTNode的ID字段值和QueryParameter类库定义的SQL查询语句匹配管网阀门的On1yID，记录符合条件的ID数组，然后利用FindConnected EdgesFromNodes方法获取与节点ID数组连通的设施网络模型弧段，用GeoSty1e类记录线状路径的风格属性；在SceneContro1中通过Point3D定义相对应的管点，用GeoSty1e3D类设置三维场景中管点风格符号。分析结果如图3（两个管点均在管网环路上）。

图3 管网连通性分析

2.2 管网上下游追踪

燃气管网上下游追踪分为上游追踪和下游追踪，使用BFS算法基于流向进行正向和反向搜索计算并标识出燃气管网目标要素的上游和下游路径。具体通过调用Point2D和Point3D分别在MaPContro1和SceneContro1中选取一个管点，并使用GeoSty1e和GeoSty1e3D类设置点状符号风格；利用Faci1ityAna1ystResu1t类的TraceUP FromNode 和TraceDownFromNode方法，分别根据给定的nodeID进行上下游追踪，利用BFS算法查找该节点的上下游连通节点，利用FindConnectedEdgesFromNodes查找并返回与节点连通的弧段集合，用GeoSty1e类记录并设置线状符号风格属性。上游追踪分析结果如图4。

图4 管网上游追踪

2.3 管网共同上下游查找

共同上下游查找，即查找两个管点的共同上游和共同下游，并标识出查找路径。在maPContro1和SceneContro1窗口分别通过Point2D和Point3D定义两个管点，并设置GeoSty1e和GeoSty1e3D类的点状符号风格，通过Faci1ity-Ana1yst类调用Faci1ityAna1ystResu1t、FindCommonAncestors-FromNodes和FindCommonCatchmentsFromNodes方法，查找两管点的共同上下游弧段，并返回弧段集合，用GeoSty1e类设置弧段路径风格符号。查找共同下游结果如图5。

图5 管网共同下游查找

2.4 最短路径分析

最短路径分析是指在设施网络模型中，根据管网流向和管网长度权值来计算最短路径的过程。最短路径的计算以管段的长度值为参考，即通过给定的起始点，根据流向信息和BFS算法采用正向和反向搜索遍历到终止点的路径，根据长度权值选择最短返回路线。首先根据给定的起始点和终止点ID，利用Bui1dFaci1ityNetworkDirections方法正反BFS搜索，直到搜索到终止点ID，通过Faci1ityAna-1yst类调用Faci1ityAna1ystResu1t和FindPathFromNodes方法，根据Sm Length权值获取到最短路径。

2.5 查找源和汇

查找源和汇指在设施网络模型中根据指定的管点，按照流向信息查找流向该管点最近的源点或下游汇点。首先判断该管点ID所在的管段，根据流向Direction字段信息使用反向BFS搜索算法查找最近的源点，使用正向BFS算法查找该管点的下游汇点。具体通过给定管点ID匹配管线起始点或终止点ID并判断该管线流向，利用反向BFS算法记录所有符合条件的管点ID并存储在二维数组中，通过调用Faci1ityAna1ystResu1t类的Find-SourceFromNode方法查找流向该管点的源点，并在Find-ConnectedEdgesFromNodes中查找与管点相连通的管段集合，在GeoSty1e中设置结果显示风格。查找源点结果如图6。

图6 查找源点

3 结束语

管网3DGIS的连通分析，首先要解决管网数据模型的拓扑关系，其次针对管网介质的流动性，分析管网流向对连通分析的影响。基于流向的设施网络模型在燃气管网连通分析中，利用BFS基础算法，采用正向和反向搜索遍历管网中管点和管段关系，解决了燃气管网在流向和环路上的连通分析问题，包括管网的连通性分析、上下游追踪、共同上下游查找、最短路径分析、查找源和汇等连通分析功能，对管网系统的优化管理、提高可靠性和运行效率提供了可行性方法。

［1］OSTFELD A，ASCE M.Water distribution systems connectivity ana1ysis［J］.Journa1ofWater Resources P1anning and Management，2005，131（1）：58-66.

［2］段琪庆，刘寒芳，薛冰.数字管网连通分析的淘汰算法与实现［J］.测绘科学，2008（S1）：168-169.

［3］陆鸣盛，沈成康.图的连通性快速算法［J］.同济大学学报

（自然科学版），2001，29（4）：436-439.［4］何双华，赵洋，宋灿.城市供水管网在地震时的连通可靠性分析［J］.防灾减灾工程学报，2011，31（5）：585-589.

［5］王方雄，崔羽.基于GIS的管网爆管分析算法优化与实现［J］.武汉理工大学学报（交通科学与工程版），2012，36 （3）：575-578.

［6］虞成诚，钟声，胡绍华.基于深度优先搜索的一般图匹配算法［J］.计算机工程与科学，2008，30（12）：45-48.

［7］张翔，王方雄，崔羽.城市三维管网地理信息系统的设计与开发［J］.测绘地理信息，2015，40（2）：17-19.

［8］雷伟刚.城市地下管网信息系统中管网追踪算法［J］.同济大学学报（自然科学版），2003，31（1）：99-103.

侯英姿（1974 -），通信作者，女，博士，讲师，主要研究方向：GIS建模与技术应用。E-mai1：hyzwhu@163.com。

Connectivity ana1ysis and imP1ementation of PiPe 3DGIS

Liu Ziheng1，2，Hou Yingzi1，2，Wang Fangxiong1，2，Zhang Xiang3
（1.Liaoning Key Lab of Physica1GeograPhy and Geomatics，Liaoning Norma1University，Da1ian 116029，China；2.Schoo1of Urban and Environmenta1Sciences，Liaoning Norma1University，Da1ian 116029，China；3.Da1ian Urban P1anning&Design Institute，Da1ian 116011，China）

This PaPer studied connectivity ana1ysismethod of city PiPe 3DGIS.Themethod uses breadth -first search a1gorithm to traverse and search network node by Positive and negative based on f1ow information of network.Based on SuPerMaP iObjects Program，it achieves the communication ana1ysis functions of PiPe 3DGIS 1ike connectivity ana1ysis，tracking ana1ysis of uPstream and downstream，searching common uP-stream and downstream，shortest Path ana1ysis and to find source&sink.

connectivity ana1ysis；breadth-first search a1gorithm；SuPerMaP iObjects；PiPe 3DGIS

U178

A

10.19358 /j.issn.1674-7720.2016.09.023

刘子恒，侯英姿，王方雄，等.管网3DGIS的连通分析方法与实现［J］.微型机与应用，2016，35（9）：78-80，84.

教育部人文社会科学研究一般项目（11YJC630202）

2016-01-15）

刘子恒（1988 -），男，硕士研究生，主要研究方向：GIS开发与技术应用。