利用有向图进行排水管网自动化流向分析
|
摘要
超标排放是城市排水系统中面临的问题之一,为了高效准确地获取超标水体的流径及最终排放口,提出一种基于有向图的流向分析算法。在分析管网有向几何模型、流向与管线一致性后,利用正向广度优先搜索、缓冲区分析及跨管种混接点搜索进行算法设计,实现在步进搜索过程中自动获取超标水体所流经的管线,并通过实例验证了算法的有效性。与传统方法比较,提出的算法在海量数据下大幅提高了分析效率。
The overproof sewerage is still a sternly and headachy question in the city drainage system. In order to efficiently and accurately obtain the flow through of wastewater, this paper puts forward an automatic flow direction analysis algorithm based on directed graphs. Firstly, the geometric model of pipeline network, consistency of flow direction and pipeline property are analyzed. Secondly, the algorithm is designed by forward breadth-first search, buffer analysis and search hybrid junction pipeline, realized automatic acquisition of polluted pipelines in the step-search process. Finally, the validity of the algorithm is demonstrated using an example, and comparison with traditional methods, for massive pipeline network data, the proposed algorithm greatly improves the efficiency of analysis.
The overproof sewerage is still a sternly and headachy question in the city drainage system. In order to efficiently and accurately obtain the flow through of wastewater, this paper puts forward an automatic flow direction analysis algorithm based on directed graphs. Firstly, the geometric model of pipeline network, consistency of flow direction and pipeline property are analyzed. Secondly, the algorithm is designed by forward breadth-first search, buffer analysis and search hybrid junction pipeline, realized automatic acquisition of polluted pipelines in the step-search process. Finally, the validity of the algorithm is demonstrated using an example, and comparison with traditional methods, for massive pipeline network data, the proposed algorithm greatly improves the efficiency of analysis.
引文
[1] Cui Lei, Qian Lin, Chen Tingwu. Design and Application of Underground Pipeline Information Management System Based on ArcEngine[J].Urban Geotechnical Investigation & Surveying,2018(5):45-48 (崔磊,钱林,陈廷武.基于ArcEngine的地下管线信息管理系统的设计与应用[J].城市勘测,2018(5):45-48)
[2] Li Ping, Li Yongshu.Arithmetic Research of Pipe Burst Analysis in Pipe Network Based on Flow Direction[J]. Journal of Computer Applications, 2012,32(S2):45-47(李平,李永树.基于流向的管网爆管分析算法[J].计算机应用,2012,32(S2): 45-47)
[3] Zeng Wen, Ao Qingxin, Yang Zhijiang. The Unit-valve Graph Model of Water Supply Networks for Valve-closing Analysis Algorithm[J]. Geomatics and Information Science of Wuhan University, 2014,39(12): 1 441-1 445(曾文,敖卿鑫,杨之江.适用于关阀分析算法的供水管网单元-阀门图模型[J].武汉大学学报·信息科学版, 2014,39(12):1 441-1 445)
[4] Li Le, Fan Ying. Directed Network Analysis Based on Bipartite Structure[J]. Journal of Beijing Normal University(Natural Science), 2015,51(5):480-483(李乐,樊瑛.基于二分结构的有向网络分析[J].北京师范大学学报(自然科学版),2015,51(5):480-483)
[5] Ni W, Cheng D Z. Leader-Following Consensus of Multi-agent Systems Under Fixed and Witching Topologies[J]. Systems &Control Letters,2010,59(3-4): 209-217
[6] National Administration of Surveying, Mapping and Geoinformation of China. Classification Codes and Cartorgraphic Symbols for Pipeline Features[S]. Beijing: Surveying and Mapping Press,2015(国家测绘地理信息局.管线要素分类代码与符号表达[S].北京:测绘出版社,2015)
[7] Ma Chao, Sun Qun, Chen Huanxin, et al. Application of Weighted Page Rank Algorithm in Road Network Auto-selection[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1 159-1 165(马超,孙群,陈换新,等.加权网页排序算法在道路网自动选取中的应用[J].武汉大学学报·信息科学版,2018,43(8):1 159-1 165)
[8] Huang Hong, Gong Jianya, Zhong Zheng. On Intelligent Checking of Underground Pipeline Data[J]. Geomatics and Information Science of Wuhan University, 2007,32(8): 731-734(黄鸿,龚健雅,钟正.地下管线数据的智能化检查研究[J].武汉大学学报·信息科学版,2007,32(8):731-734)
[9] Li Feng, Shang Huiliang. An Isomorphism Testing Algorithm for Directed Graphs: The In-degree and Out-degree Sequence Method[J]. Journal of Applied Sciences, 2002,20(3):258-262 (李锋,商慧亮.有向图的同构判定算法:出入度序列法[J].应用科学学报,2002,20(3):258-262)
[10] Peng Limin. Virtual Network Embedding Algorithm Based on Breadth-First Search[J]. Journal of Sichuan University(Engineering Science Edition) ,2015,47(2):117-122 (彭利民.基于广度优先搜索的虚拟网络映射算法[J].四川大学学报(工程科学版),2015,47(2):117-122)
[2] Li Ping, Li Yongshu.Arithmetic Research of Pipe Burst Analysis in Pipe Network Based on Flow Direction[J]. Journal of Computer Applications, 2012,32(S2):45-47(李平,李永树.基于流向的管网爆管分析算法[J].计算机应用,2012,32(S2): 45-47)
[3] Zeng Wen, Ao Qingxin, Yang Zhijiang. The Unit-valve Graph Model of Water Supply Networks for Valve-closing Analysis Algorithm[J]. Geomatics and Information Science of Wuhan University, 2014,39(12): 1 441-1 445(曾文,敖卿鑫,杨之江.适用于关阀分析算法的供水管网单元-阀门图模型[J].武汉大学学报·信息科学版, 2014,39(12):1 441-1 445)
[4] Li Le, Fan Ying. Directed Network Analysis Based on Bipartite Structure[J]. Journal of Beijing Normal University(Natural Science), 2015,51(5):480-483(李乐,樊瑛.基于二分结构的有向网络分析[J].北京师范大学学报(自然科学版),2015,51(5):480-483)
[5] Ni W, Cheng D Z. Leader-Following Consensus of Multi-agent Systems Under Fixed and Witching Topologies[J]. Systems &Control Letters,2010,59(3-4): 209-217
[6] National Administration of Surveying, Mapping and Geoinformation of China. Classification Codes and Cartorgraphic Symbols for Pipeline Features[S]. Beijing: Surveying and Mapping Press,2015(国家测绘地理信息局.管线要素分类代码与符号表达[S].北京:测绘出版社,2015)
[7] Ma Chao, Sun Qun, Chen Huanxin, et al. Application of Weighted Page Rank Algorithm in Road Network Auto-selection[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1 159-1 165(马超,孙群,陈换新,等.加权网页排序算法在道路网自动选取中的应用[J].武汉大学学报·信息科学版,2018,43(8):1 159-1 165)
[8] Huang Hong, Gong Jianya, Zhong Zheng. On Intelligent Checking of Underground Pipeline Data[J]. Geomatics and Information Science of Wuhan University, 2007,32(8): 731-734(黄鸿,龚健雅,钟正.地下管线数据的智能化检查研究[J].武汉大学学报·信息科学版,2007,32(8):731-734)
[9] Li Feng, Shang Huiliang. An Isomorphism Testing Algorithm for Directed Graphs: The In-degree and Out-degree Sequence Method[J]. Journal of Applied Sciences, 2002,20(3):258-262 (李锋,商慧亮.有向图的同构判定算法:出入度序列法[J].应用科学学报,2002,20(3):258-262)
[10] Peng Limin. Virtual Network Embedding Algorithm Based on Breadth-First Search[J]. Journal of Sichuan University(Engineering Science Edition) ,2015,47(2):117-122 (彭利民.基于广度优先搜索的虚拟网络映射算法[J].四川大学学报(工程科学版),2015,47(2):117-122)