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

摘要

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 whish 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 erosing number and eliminating the void notes.An edge crossing minimization algorithm for layered digraphs besed 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.