基于分层法的通风网络图绘制算法研究

最长路径法绘制通风网络图需要频繁地搜索任意两个节点之间的最长路径，采用深度优先搜索导致大量的时间浪费在无用路径的搜索过程中；且采用几何相交方法判断分支交叉，效率低且无法有效地减少分支交叉数。提出了将分层法引入到通风网络图绘制中。采用最长路径法对网络图进行节点分层，求解整数规划问题优化节点分层减少长边；采用模拟退火遗传算法优化节点排序，从拓扑上减少分支交叉数。为了减少无意义地搜索最长路径过程，采用最长路径并联通路法计算节点坐标和分支形状。给出了基于分层法的通风网络图绘制的测试例子。

Study on drawing algorithm of ventilation network graph based on layer method

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 algorithm. Geometric intersection method is adopted to determine the arc crossings, but it has low efficiency and can not effectively 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 coordinates and arc shape, which is called longest parallel path method. The test example of drawing ventilation network graph is presented based on layered method.