计算机工程与应用Issue(15)：1-6,6.DOI:10.3778/j.issn.1002-8331.1312-0073
基于分层法的通风网络图绘制算法研究
Study on drawing algorithm of ventilation network graph based on layer method
摘要
Abstract
Drawing ventilation network graph based on longest path method requires frequently searching the longest path between any two nodes. There is a lot of time wasted in useless paths search process because of the depth first search algo-rithm. Geometric intersection method is adopted to determine the arc crossings, but it has low efficiency and can not effec-tively reduce the arc crossings number. The layered method is introduced to ventilation network graph drawing. The longest path method is employed to rank nodes of ventilation network, and long edges are removed by solving integer programming problem for optimizing node ranking. Then simulated annealing-genetic algorithm is used to optimize the nodes order based previous node ranking step, reducing the arc crossings number from the network topology. In order to decrease the meaningless longest path search process, a modified version of the longest path method is made to calculate node coordi-nates and arc shape, which is called longest parallel path method. The test example of drawing ventilation network graph is presented based on layered method.关键词
通风网络图/最长路径法/整数规划/分层法/模拟退火遗传算法Key words
ventilation network graph/longest path method/integer programming/layered method/simulated annealing-genetic algorithm分类
矿业与冶金引用本文复制引用
邓立军,刘剑..基于分层法的通风网络图绘制算法研究[J].计算机工程与应用,2014,(15):1-6,6.基金项目
国家自然科学基金委员会与神华集团有限公司联合资助项目（No.51174265）。 （）
