利用遗传算法改进DAG绘制的方法  

Improved method for drawing directed acyclic graph with genetic algorithm

作　　者：郭涛[1] 么炜[1] 苑迎春[1] 

机构地区：[1]河北农业大学信息科学与技术学院,河北保定071001

出　　处：《计算机工程与应用》2011年第8期172-174,222,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60873236);河北省自然科学基金(No.2009000653)~~

摘　　要：DAG图(Directed Acyclic Graph)广泛应用于数据库建模、工程设计等领域。DAG图一般用矩阵来存储,能够将矩阵存储的DAG图正确、美观地画出来,使得DAG图更直观,清晰,方便各种问题的分析和处理。DAG图的绘制包含分层、最小化边交叉数和删除哑结点。提出了基于遗传算法的分层和最小化边交叉数的方法和删除哑结点的启发式算法。实例结果表明提出的方法能有效解决DAG图绘制中的交叉点问题。The DAG graph（Directed Acyclic Graph） is widely used in database modeling and engineering design,and it is always stored by using matrix.If the DAG graph which is stored by matrix can be draw precisely and clearly,the graph will be easily to read.Many problems will be conveniently to solve.There are three main aspects in the drawing of the DAG graph：delaminating,minimizing the edge crossing number and eliminating the void notes.An edge crossing minimization algorithm for layered digraphs based on genetic algorithms is presented,and a heuristic algorithm to eliminate void notes is also proposed.The result of the example shows that these methods can solve the DAG drawing problem effectively.

关 键 词：分层 最小化边交叉数 遗传算法 哑结点 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]