有向无环图分层算法研究  

Research on layering algorithm of DAG

作　　者：陈建新[1] 唐海[2] 

机构地区：[1]孝感学院计算机科学系,湖北孝感432000 [2]武汉大学国家多媒体软件工程技术研究中心,武汉430072

出　　处：《华中师范大学学报（自然科学版）》2008年第3期359-363,共5页Journal of Central China Normal University：Natural Sciences

基　　金：国家863计划项目(2003AA001032)

摘　　要：具有复杂概念结构的数字化教学资源,其可视化是教学资源整合的重要组成部分.对有向无环图(DAG)的结点进行分层,使得所有结点指向同一个方向,是经典的Sugiyama画图算法中的一个重要步骤.在对现有几个具有代表性分层算法的实验和结果分析基础上,运用线性规划的思想,采用单纯形法的结点分层算法作为数字化教学资源的可视化工具.该算法可以确保分层后的图的总边长跨度最小,并保证其所占的面积也比其他的算法显著减少.The visualization of complex conceptual structure is a very important section of the educational media integration. The problem of partitioning a directed acyclic graph into layers is considered such that all edges point the same directionally. We perform an experimental analysis of some of the existing laye~：ing algorithm. Then we propose simplex algorithm based on linear programming to layering a graph. The goal is to minimize the total sum of edge span so that the layered graph has a smaller area than other algorithms.

关 键 词：画图 分层算法 单纯形法 知识结构可视化 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]