Study Of The Maximum Flow Problem On Uncertain Graph

Maximum flow means the maximum value of flow from source node to sink node in the network,the maximum flow research based on uncertain graph is the extension of the traditional maximum flow problem.As uncertainty is the inherent attribute of the actual systems,the research is essential for constructing reliable network,selecting reliable transmission paths and evaluating key edges,so it has been widely concerned in the field of research and application.The paper focuses on two representative problems in the maximum flow research field based on uncertain graph,with regard to the application of d-flow is more universal,the maximum flow is only the special case,so combine the two cases as the object of the research.Firstly,study the flow reliability problem which defines the probability of transferring the maximum/d units flow from source node to sink node.However,stochastic flow reliability problem is NP-Hard,the performance of accurate algorithm is unacceptable when the scale of graph increases.Therefore,the Monte Carlo approximation algorithms are proposed while these algorithms are required to calculate maximum flow of all the sample state vectors and make the cost is high.Then MC_DF algorithm is proposed which exploits minimal cut sets filter rule and augmented flow filter rule to avoid calculation of invalid states,furthermore,the MC_MFEP algorithm is proposed which exploits the cache and index of simple paths to accelerate the search of augmented path,meanwhile accelerate the calculation of maximum flow and improve the performance of d-flow reliability evaluation.Moreover,MC KFL algorithm is proposed,it replaces the direct random sampling plan with stratified sampling plan based on failure edges to reduce sampling variance and the number of samples.Besides,concentrate on the most reliable flow problem which means the most reliable flow distribution transferring the maximum/d units flow from source node to sink node.However,the current algorithm ISDA-d just considers the states which satisfy d-flow and ignore to inspect the reliability of flow in the space decomposition period and leads to some meaningless space decompositions,thus SDBA SF algorithm is proposed,it utilizes space filter rule to reduce the number of states to be divided.Considering that the network topology may change because of accidents,it is necessary to find an alternative flow distribution quickly.The algorithm in the static environment is no longer suitable because of its complexity,therefore,a rapid reliable flow distribution solution in dynamic environment is put forward,it calculates Top-K most reliable d-flow distributions and caches all simple paths in advance.If the network satisfies d-flow after edge fails,then get a d-flow distribution quickly from the existing K-1 distributions.If no feasible d-flows exist,then use simple path replacement algorithm to replace fail paths in the original d-flow.If the network can not satisfy d-flow or replacement algorithm fails to get a feasible d-flow distribution,then use PRAA algorithm to calculate a new reliable d-flow distribution.Finally,design series experiments to verify the flow reliability algorithms and most reliable flow algorithms proposed in this paper.The experimental results certify the accuracy and performance of approximation algorithms of flow reliability,and compare with current d-flow algorithms to verify the effectiveness of d-flow algorithms proposed in this paper.