摘要：本文主要针对排水管网自动生成有向图的拓扑结构法进行综述分析，望能够为相关专家及学者对这一课题的深入研究提供有价值的参考或者依据。
关键词：排水管网；有向图；拓扑；结构；自动生成；方法；
前言：
由于现阶段国排水管网的建模基础资料以Auto CAD中dwg为数据信息格式来存储，无法存储管网图形相关信息数据及相关属性信息等，更无法表达出管网实际拓扑结构。那么，通过有向图此种方式便能够攻破以上难题。故深入研究排水管网自动生成有向图的拓扑结构法尤为必要。
1、描述问题与思路分析
为能将管道及节点间拓扑关系表达出来，应定义管道及节点基本属性。管道及节点，其与有向图的拓扑关系所生成属性即为：管段起始节点及终止节点的编号数值均为整形；节点编号、层级的标识及相邻节点的数量数值类型均为整形。借助管段起始节点及终止节点的编号，节点编号基本属性间所对应关系均可表达为管段坡度的方向有向图的拓扑关系。自动生成有向图的拓扑结构法即为：基于无向拓扑的结构，处于判断基础条件之下生成相应有向图。重点为经某确定已知的条件，借助明确判断法，程序自动化判断管段两个端点中，具体哪个为起点及终点。针对排水管网，可把管网当中节点先分成非排放口及排放口的两个节点，起点基于排放口的节点反向地寻找着通往着排水管网的起端节点法，自动化构建排水管网的拓扑结构。此法基于图广度优先的遍历，自排放口的节点向着起端节点实现层次化推进，推进期间节点层级标识可实现属性赋值。以层级的标识值大小来确定其管段方向，促使自动化生成有向图的拓扑结构，以下为具体流程：构建起无向图的拓扑结构，基于图广度优先的遍历算法来计算节点层级的标识，结合层级标识对管段起始及终点的节点编号进行合理调整，促使有向图的拓扑结构可自动生成。
2、节点层级的标识算法
通过以上分析论述后可了解到，此方法重点为怎样计算节点层级间的标识，以下为具体思路：把排放口的节点层级标识合理赋值为零，把它为出发的节点，借助广度优先的遍历法向着相邻的节点逐层推进，在为相邻的节点层级标识均赋最大值，把相邻阶段当成出发的节点，重复以上过程可到管网起始点。所有节点层级标识已完成赋值后，可通过对比管段两端的节点层级具体标识值，确定好节点针对现阶段管道的终点或起点。
若排水管网属于树状的管网，可借助传统广度优先的遍历，便能够准确确定好节点层级标识的数值，但真实排水管网内有管道成环，部分节点为若干排放口所处上游管道公共的节点，这种状况之下可借助传统式广度优先的遍历，依据节点遍历实际顺序，采取上下游的节点判断为发放，把促使节点所在上下游的关系受到末端及节点遍历实际深度影响所引起上下游发生顺序颠倒状况。对于以上状况，生成拓扑结构期间需借助节点度为主要的判断根据，出发点基于节点状况处于暂停或前进状态予以精准地判断，层级标识的赋值断开相邻阶段及出发节点连接关系，更新节点度。基于以上方法引入可防止节点的层级标识多次赋值与上下游的节点出现顺序颠倒状况。如图1所示，为管网实际所存在着运用传统式广度优先的遍历法失效两种最为典型管网的拓扑结构。图1当中（a），显示出A节点2个排放口的节点所在上游路径公共节点状况，若以传统式广度优先的遍历算法为基础，会导致此节点层级标识实际数值可由实际距离相对较近排放口的节点来确定，对与之相邻节点层级标识的赋值有着一定影响。依据传统式广度优先的遍历计算分析结果当中即可了解到，以传统式广度优先的遍历算法为基础，来对管道方向进行判断期间，管道方向有错误情况出现，亦或者是出现无法判断管道具体方向这一状况。在引入了暂停、前进这两种状态后，自排放口的B节点为起点，检索路径需先到A节点，但因A节点度＞3，故B节点处暂停状态之中，并不依据B节点层级标识的数值计算分析出A节点层级标识的数值，一直到自C节点检索路径达A节点，依据这两个路径进行计算分析获取到两个层级的标识数值，取最大数值为A节点层级的标识，给出图1（c）中显示节点层级的标识数值正确的计算分析结果。从图1（d）当中可了解到环状管道实际状况，自B节点到A节点路径为两个，可把A节点当成与图1当中（a）较为相似处于练歌排放的路径中公共的节点，若以传统式有先遍历法为基础，计算分析出节点层级的标识数值，如图1（e）为具体结果，显示出管道错误方向或无法判断实际状况。引入暂停、前进状态，获取图1（f）中正确层级标识的计算分析结果。计算节点层级的标识数值期间，上游节点层级的标识完成计算分析后，需将节点及层级标识断开计算，根据下游节点连接的关系，避免节点间有反复计算分析层级标识数值这一状况出现。在全部节点层级的标识具体计算分析及赋值完毕后，遍历全部管道，对比两个端点层级标识数值大小情况，层级标识做大数值即为起始的节点，最小数值则属于终止的节点。
图1运用传统式广度优先的遍历法失效两种最为典型管网的拓扑结构示图
3、案例分析
简单的一种排水管网，数字即为节点的编号。基于以上方法来对算例当中管网实施节点层级的标识数值计算分析，以获取到图2当中排水管网的有向图总体拓扑结构。在所有出发节点全部处于暂停状态，针对于可能与其多个出发的节点相邻节点当中，一次循环完成层级标识计算分析及赋值，避免出现多次赋值。如图3-1、3-2所示，15、12、7、4这几行实际状况。图3-1中15行当中，24与8节点均属于出发节点，均连接着节点9，从图中所描述方法当中即可了解到节点9仅在15次的循环当中实现赋值，层级标识依据24与8节点计算分析获取层级标识最大数值，上游节点层级标识数值超过下游节点层级标识的数值。以上方法通常可准确判段出管道节点上下游实际关系，但某些特殊状况下极易存在算法分析结果符合于实际状况这一问题。如两个出发的节点相邻，上下游之间关系自两个节点遍历中顺序来决定，出发节点所集合节点遍历的顺序具有随机性，促使该状况下极易存在算法分析结果符合于实际状况这一问题。如图2中节点16与7间上下游的关系极易出现与计算分析结果相反这一状况。可能引发持续错误结果两种典型的管网结构即为：环状的管网与末端两个节点相连树状管网。故构建完有向图的拓扑结构后，仍需做好人工检查工作。
图2 排水管网的有向图总体拓扑结构示图
图3-1算例管网层级标识的计算分析过程与结果
图3-2算例管网层级标识的计算分析过程与结果
4、结语
综上所述，基于排水管网无向图的拓扑结构，引入可表示着节点所处上下游之间关系层级表示的变量，自末端节点逐渐向着上游呈逆行式推进广度优先的遍历法，计算节点层级标识的变量赋值，以促使该排水管网能够自动生成有向图的拓扑结构。为处理好管道成环、相同节点处多个末端的节点上游所在位置状况，每次循环期间出发节点均修设暂停、前进这两种状态，以避免节点层级的标识出现多次赋值状况。此法计算分析结果下处理管道成环、相同节点处多个末端的节点连接树状管网总体结构期间，极易有错误情况出现。故而，构建完有向图的拓扑结构后，人工检查尤为必要。
参考文献：
[1]钱真，贾卫红，李世阳.河网水流模拟的矩阵标识法研究[C].全国河湖治理与水生态文明发展论坛.2017，34（05）：371-373
[2]王萌，史明昌.城市排水GIS系统拓扑模型的建立[J].测绘通报，2017，19（08）：138-143.
论文作者:黄尧舜
论文发表刊物:《基层建设》2019年第19期
论文发表时间:2019/9/21
标签：节点论文; 层级论文; 管网论文; 标识论文; 拓扑论文; 数值论文; 结构论文; 《基层建设》2019年第19期论文;