|
概念图的布局算法研究
赵国庆 杨南应 贾振洋 范 典 黄荣怀
（北京师范大学 知识科学与工程研究所，北京 100875）
概念图是一种有效的知识可视化工具，而概述图的布局是影响其信息传递能力的重要因素，因此布局算法是实现概念图工具的重要技术基础。本文在Sugiyama层次布局算法的基础上，针对概念图的特点和布局要求，提出了一种概念图的布局算法：首先对概念图的概念节点和关系节点进行简化处理，然后应用Sugiyama层次布局算法的第一步（分层），并对图中的关系节点进行特殊处理，调整分层，最后应用Sugiyama层次布局算法的“交叉减少”和“坐标分配”模块，得出概念图各个节点（包括概念节点、关系节点和虚拟节点）的坐标，最终得出概念图的布局。该算法已通过编程实现，并成功应用于我们自主研发的概念图工具软件中。
【关键词】概念图； 知识可视化； 布局算法； 有向图布局； Sugiyama层次布局
【中图分类号】G434
【文献标识码】A
【文章编号】1007-2179（2005）05-0032-06
Research on Algorithm for Drawing Concept Maps
ZHAO Guoqing, YANG Nanying, JIA Zhenyang, FAN Dian & HUANG Ronghuai
(Institute of Knowledge Science and Engineering, Beijing Normal University, Beijing 100875)
Abstract: Concept maps are effective tools for knowledge visualization, and their layouts have a significant effect on their power of information expression. Based on the Sugiyama Hierarchical Layout Algorithm and the special needs of concept mapping tools, this paper presents an algorithm for drawing concept maps. Firstly, we simplify nodes of concepts and linking words into common ones, and then use the first step of Sugiyama Layout Algorithm to assign layers. Secondly, we adjust these layers through specific treating on nodes of linking words. At last, Crossing Reduction and Coordinate Assignment are applied, which are second and third phrases of Sugiyama Layout Algorithm. In this way, the coordinates of all nodes, including nodes of concepts, nodes of linking words and model nodes, are generated, and the final layout of concept map is available. The algorithm has been implemented and applied to developing a new concept mapping tool by KSEI (abbr. of Institute of Knowledge Science and Engineering) at Beijing Normal University.
Key words：concept Map; knowledge visualization; layout algorithm; layout of directed graph; sugiyama hierarchical layout
|
