流体网络的简化技术

Network simplification technology of fluid network

网络自动简化技术是分析流体网络的强有力工具,网络简化对提高流体网络算法的运行速度也具有重要意义。采用最长路径的思想限制算法的搜索范围,减少深度优先搜索算法搜索子网的次数,如果搜索的次数超过了源汇节点之间的搜索次数上限阈,那么就可以判定源汇节点之间不存在可以简化的子网。只需要通过正向搜索和反向搜索两次搜索过程即可确定需要简化的子网分支集合以及子网的类型,避免了纯粹数学计算方法的缺陷。同时采取"由内至外"的网络简化策略,从网络中层次间距最小的子网开始简化,将子网简化成1条分支,一层一层的向外进行简化,这样使得算法本身就具备了层次性,保证了最终网络简化结果的层次性。最后将简化算法进行应用并与文献提出的算法的简化结果进行了比较和分析。

Network simplification is a powerful tool to analyze fluid network and it is also a significant improvement in computation speed of network algorithm. So far, the existing network simplification algo- rithm can not be well applied to large-scale and complex fluid net- works due to its poor efficiency, arising from recursive nature of.the old algorithm which gives easy end intuitive understandings but strict- ly conforms to the mathematical definition for network simplification. Based on the longest path method, an improvement in order to reduce search counts on traditional DFS algorithm was achieved through re- ducing child networks searching, calculating layer attributes of nodes in network, then imposing a max-search-counts limit on the extent of DFS algorithm. The conclusion could be easily drawn that there is no child network could be simplified between source and sink nodes, in case the search counts reach upper boundary. Edge sets and network type of child network can also be established through only two forward and backward search processes, eliminating inefficient deficiencies caused by pure mathematical calculation method. This algorithm would not try to compare all node pairs because it is much wastage of time on large-scale network. 0nly node whose outdegree or indegree is greater than two is selected as source or sink node, while the algo- rithm＇s judgment and comparison counts are greatly reduced for that strategy. In order to make the network simplification algorithm satis- fies the hierarchical requirements, a ＂from inside to outside＂ strategy was adopted. Network simplification was started from child network with the minimum vertical distance, then the child network was sim- plified to a virtual edge and the process was continued from lower node distance to higher. In this way, a hierarchical network simplifi- cation result is obtained while the process of network simplification al- gorithm has exhibited the characteristic of hierarchy as well. Finally, the developed network simplification was applied to a simple practical application and the result was compared with the old reference algo- rithm.