概念图的布局算法研究

Research on Algorithm for Drawing Concept Maps

概念图是一种有效的知识可视化工具，而概念图的布局是影响其信息传递能力的重要因素，因此布局算法是实现概念图工具的重要技术基础。本文在Sugiyama层次布局算法的基础上，针对概念图的特点和布局要求，提出了一种概念图的布局算法：首先对概念图的概念节点和关系节点进行简化处理，然后应用Sugiyama层次布局算法的第一歩（分层），并对图中的关系节点进行特殊处理，调整分层，最后应用Sugiyama层次布局算法的”交叉减少”和”坐标分配”模块，得出概念图各节点（包括概念节点、关系节点和虚拟节点）的坐标，最终得出概念图的布局。该算法已通过编程实现，并成功应用于我们自主研发的概念图工具软件中。

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 models 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.