Research On The Maximum Flow Acceleration Algorithm Of Large-scale Graph Based On Parallel Graph Computing Framework

The maximum flow problem is an important basic problem in graph theory,its solution algorithm has been widely used in the fields of science and engineering as well as in real life,the traffic flow control related to urban traffic,the calculation of the maximum displacement of urban drainage pipeline,network planning,path planning and other important issues can be abstracted as the maximum flow problem;the maximum flow problem is also the theoretical basis of computer vision,big data,image processing and other technologies.These technologies are still developing and updating rapidly,therefore,the in-depth study of the maximum flow problem is helpful to promote the development of related fields,and has important theoretical and practical significance.The academia has proposed many new algorithms and new ideas to solve the maximum flow problem,and relatively complete theoretical system for solving the maximum flow problem on a single machine is gradually established.Although the existing algorithms solve the maximum flow problem from multiple angles,there are still some problems such as inaccurate calculation results and low solution efficiency when applied to the processing of massive graphs.In response to these problems,this paper mainly studies the maximum flow acceleration of large-scale graph based on the GraphChi framework,and tries to solve the key problems such as the high computational complexity of graph segmentation and the large amount of redundant calculations in this parallel graph computing framework.The main content of this article is as follows:(1)Research on the method of graph data partition and overlay graph construction for maximum flow calculation,use the cut vertices to build the overlay graph and split the original graph into multiple subgraphs,map the cut vertices to the overlay graph and put the remaining vertices into different subgraphs.The test results on classic datasets such as the United States Road Networks(TIGER/Line)show that the algorithm reduces the number of vertices to 0.97% ~6.64% of the original graph.(2)Research on the mapping and splitting method of the maximum flow problem based on the overlay graph,given source and sink vertex,locate the corresponding two vertices of the overlay graph in the overlay graph,then find the path between the corresponding two vertices in the overlay graph,and find the corresponding subgraphs according to the determined path.In order to improve the calculation speed of the maximum flow of multiple subgraphs,a parallel acceleration algorithm for maximum flow was proposed to compute the maximum flow locally of multiple subgraphs on the path in parallel.The experimental results show that the maximum flow calculation results of the algorithm are highly consistent with the classical algorithm,the accuracy rate is above 96%,and calculate the maximum flow on the largest subgraph can significantly improve the computation speed.(3)In order to further accelerate the calculation of the maximum flow of multiple subgraphs,an accelerated computing method based on GraphChi framework was proposed,submit multiple subgraphs on the path to the GraphChi framework for parallel computing,and integrate the maximum flow results of these subgraphs to obtain the maximum flow values of source and sink vertex in the original graph.The experimental results show that the algorithm proposed in this paper can improve the computation speed of the maximum flow of large-scale graphs to about 23~39 times that of Dinic algorithm,effectively reduces the time complexity,and verify the feasibility of the algorithm.