刘子恒1,2,侯英姿1,2，王方雄1,2，张翔3

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

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

　　关键词：连通分析；广度优先遍历算法；SuperMap iObjects；管网3DGIS

0引言

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

1管网连通分析方法

　　1.1设施网络模型

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

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

2管网连通分析功能实现

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

　　2.1管网连通性分析

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

　　2.2管网上下游追踪

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

　　2.3管网共同上下游查找

　　共同上下游查找，即查找两个管点的共同上游和共同下游，并标识出查找路径。在mapControl和SceneControl窗口分别通过Point2D和Point3D定义两个管点，并设置GeoStyle和GeoStyle3D类的点状符号风格，通过FacilityAnalyst 类调用FacilityAnalystResult、FindCommonAncestorsFromNodes和FindCommonCatchmentsFromNodes方法，查找两管点的共同上下游弧段，并返回弧段集合，用GeoStyle类设置弧段路径风格符号。查找共同下游结果如图5。

　　2.4最短路径分析

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

　　2.5查找源和汇

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

3结束语

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

参考文献

　　［1］ OSTFELD A，ASCE M.Water distribution systems connectivity analysis［J］. Journal of Water Resources Planning and Management, 2005, 131(1): 5866.

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

　　［3］ 陆鸣盛,沈成康.图的连通性快速算法［J］. 同济大学学报(自然科学版),2001,29（4）:436439.