摘要: 随着信息可视化技术应用范围的扩大，赋权树形图的绘制过程中常常需要对边的长度进行限定。本文对赋权树形图的布局与绘制实现方法进行了研究，着重讨论了在绘图时如何在尽可能少出现交叉的情况下，使得树形舒展而分布均匀问题，提出了赋权树形的一种新绘制方法。通过对比绘制方法中两种不同的区域范围确定算法，给出了一种没有交叉的赋权树形图绘制实现的方法，最后编写了实验程序验证算法的有效性和比较的结论。
　　关键词: 赋权树形图; 交叉; 分布; 绘制

　　1、引言
    树形图可以清晰地表示离散结构的层次关系,而层次结构是一种重要的数据结构形式，所以树形图在相当广泛的领域中都有应用[1]。传统的树形图，如组织结构图、决策树图，要表现的信息维数较低，主要强调节点间的接连层次关系。在树形图自动绘制中，节点间的距离没有限制,所以传统树形图可以通过调整节点间距离进行布局[2]。对于赋权的树形图，在传统的绘制方法中一般采用数字标注的方式，并不对节点间的距离进行限制。
    随着信息量和信息维数迅速增加，信息可视化技术应运而生，人们将复杂的数据以易于理解和接受的图形或图像的形式展示出来。树形图对信息可视化技术极为重要，在表示多维信息时，节点的大小、形状、颜色、节点间连线的线型、粗细、曲直、长短（节点间的距离反映权值大小）都被用来表现相关信息。当节点间的距离用于表现诸如节点相似度、网络时延等权值信息时，那么节点间的距离就不能随意地延展了，这时图中节点位置的分布就变得相当的重要。分布得不好，容易出现交叉或者图形分布不均匀。交叉直接影响到树中节点间连接关系的准确表现，导致信息理解上的错误。而图形分布不均匀影响美观，特别是过密的节点会影响信息的直观表示，阻碍相关信息的添加。
    目前，可视化算法中效果比较好的FR算法由T.M.J.FRUCHTERMAN和E.M.REINGOLD在1991年提出。该算法将一个无向连通图看作一个力学系统[3]，通过力学平衡的原理使得图形中节点的分布较为均匀，在各种无向图的绘制上总体效果相当好。但是，该算法在表现多层赋权树形图时，会出现交叉的情况[3]。对此，本文应用父子节点的角度继承关系，提出一种无交叉的赋权树形图的绘制实现方法，称为继承法，用Inherit表示；下面详细叙述其绘图原则与布局方法、关键技术和实现过程。

　　2、绘图原则与布局方法
    在树形图绘制中节点间距离对节点布局影响最大，而节点的大小、形状、颜色，线条的线形粗细、曲直则处于次要地位。特别是交叉会导致信息理解上的错误，所以减少交叉将作为绘图布局的一个重要原则。限于篇幅次要因素在本文中不作叙述。
　　2.1　绘图原则
　　① 每一个节点采用相同的大小、形状、颜色。
　　② 节点间连线为同等宽度的直线，表示节点间的连接关系。
　　③ 节点间连线的长短表示节点间的距离（节点间的距离是给定的正权值）。
　　④ 尽可能减少图中节点间连线的交叉。
　　2.2　布局方法
    布局的总体思路为：从根节点出发，按深度优先分布各点，一个节点布局完成后，立即对其子节点进行布局，直到所有节点布局完成。
　　2.2.1　子节点布局
    在子节点布局时，父子节点关系如图1所示。父节点坐标（X0,Y0）已知，且子节点到父节点的距离D1是确定的，一旦确定父子节点间连线角度 ，就可以用公式

图1　父与子节点的关系图

    X1= D1×Cosθ＋X0
    Y1= D1×Sinθ＋Y0
    计算得到子节点的坐标(X1, Y1)。
    从公式可知，子节点的布局实质上就是各子节点θ值的确定。
　　2.2.2　子节点布局方法
    在布局时，依据子树的节点数多少按适当的规律排列相邻次序，可以使节点较多的子树和节点较少的子树在区域安排上更合理、更均匀、美观。在分配区域范围时，依据子树的节点数多少分配区域范围，可以使拥有较多节点的子树分得较大的空间，一方面可以保证树形匀称，另一方面可以减小交叉出现的可能性。
    考虑上述因素，规定在子节点布局时遵照以下几条规则：
　　(1) 每个节点从父节点分得一块扇形区域，该节点将被布局到区域的中轴线上。
　　(2) 子节点依据子树的节点数目按一定的规律排列相邻顺序
　　(3) 根据各子树的节点数分配各子树的区域范围大小，并确定各子节点的θ值。
    其中，节点排序规则如下：①处理根节点时，采用大小间隔的规律排序，使树形分布更均匀，疏密有致。②对于非根节点，针对不同的区域确定法采用不同的排序规则，以尽量减少交叉。

　　3、关键技术
    为达到理想的绘制效果，即减少交叉且均匀布局，绘制的关键在于对子节点的合理布局，而布局子节点的关键又在于到父节点连线角度θ的确定上。
从子节点布局规则上看，角度θ和两个方面因素相关：可供布局的区域范围的角度和子节点排列的顺序。
　　3.1　可供布局的区域范围的角度（以下简写为AreaArc）
    可供布局的区域范围是指所有子节点的布局区域，这个区域可以看成一个以父节点为中心的扇形。扇形的角度大小的确定直接影响最终树的结构。AreaArc越大，那么得到树形越舒展。要使树形舒展美观，AreaArc应该尽可能地大。但是AreaArc的放大常会带来交叉可能性的增大，因此要在有效控制交叉的情况下，尽可能地扩大可供布局的区域范围的角度。
本文在实现这一思路时，计算AreaArc用了两种方法：固定比例法和Inherit法。
　　3.1.1　固定比例法
    在固定比例法中所有点的AreaArc都取固定大小，取360°乘上一个系数r ,其中 r ∈（0,1]。
    这种方法每个节点的AreaArc都相同，树形的舒展不受树的层次影响，在树枝末端仍保持着一定的舒展度，但在多层、节点出度较大时，容易出现交叉。
    对不同的节点用固定比例法确定的AreaArc如图2所示。例如当r 取0.4时，树形图中所有非根节点的AreaArc都是144°，其子节点都分布在144°的一个扇形区域内。图2中每个扇形区域表示一个节点的可供分配的角度范围。从图上不难看出，其中会存在交叉的可能性。

图2固定比例法示意图

    使用固定比例法确定AreaArc时，子节点的相邻关系采用大小间隔的顺序排列。与子节点较多的子树相邻的是子节点较少的子树，这可以有效地减小交叉的可能。
　　3.1.2　Inherit法
    Inherit法是基于区域范围的分配的。在布局子节点时，将可供分配的区域范围分配给各子节点，每个子节点得到一定角度的扇形区域。节点A从父节点那里分得一块角度为α的扇形，那么当布局A的子节点时，A的AreaArc值就从α继承，也取α。
    Inherit法的最显著优点就在于不会出现交叉，每个节点为根的子树都在该节点分得的区域范围之内。但是，节点会随着距离根节点的层次的增加，AreaArc不断缩小，导致可供分配的扇形区域不断变窄，称为收缩现象。也就是说，Inhreit法对于层次较多的树，在末端枝叶节点会靠得很近，不舒展。
　　对不同节点采用Inherit法确定的AreaArc如图3所示。如图3所示，A点分得的扇形区域角度为α，那么分配子节点时，A节点的AreaArc就取α。容易看出，所有子节点的分得的范围都在其父节点分得的区域之内，即使多层也不会出现交叉。但是在多层时，末端节点C和D如果还有子节点，那么子节点就会比较靠近。

　　3.1.3　固定比例法与Inherit法的比较
    在前面的介绍中可知，固定比例法绘制的树形图，树叶舒展，但是在节点较多时容易出现交叉的现象，影响信息的表示。而Inherit方法无论节点多少都能够避免相交。
    为了比较两种方法，对同一组拥有9个节点的子树结构数据，给出固定比例法和Inherit法分别确定的AreaArc，如图4与图5所示。从A、B、C、D四个点供分配的扇形区域上看，固定比例法在第二层出现了交叉，这是一个较为严重的缺陷。Inherit法虽然出现了收缩现象，但无交叉。因此Inherit法较固定比例法优越一些。

图4　固定比例法确定的区域范围

图5　Inherit法确定的区域范围

　　4、绘制实现
    绘制实现依照基本思路是：从根节点出发深度优先遍历，采用递归调用子树布局程序绘制。
    根节点的位置可以先放画布中心，待所有点布局完成后，可根据需要对所有点整体进行适当平移。
    子树布局的主要步骤如下：
　　1) 确定可供分配的区域范围
　　2) 按子树的节点数依照一定的规律对子节点排序
　　3) 按排好的顺序，处理子节点。
　　① 依照该节点为根的子树节点数的多少，分配区域范围α 
　　② 确定该节点的θ
　　③ 计算各子节点坐标
　　④ 布局该节点为根的子树
    其中，可供分配区域范围的角度，根节点与非根节点是有差别的。对于根节点，可以根据需要手工确定。例如要使树呈中心辐射状布局，AreaArc可以取360°的圆形区域。要使树自顶向下，或者自底向上布局，可以限制为一定角度的扇形区域，如180°。
    对于非根节点，由于子树的根有一条连接到父节点的连线，在多数情况下，非根节点的左右又有兄弟节点。所以在处理时，其可供分配的区域范围角度大小，需要按固定比例法或Inherit法计算。

　　5、实验结果
    为了验证这个算法的正确性和有效性，采用Java Server Page编制实验程序，对同一组数据分别用两种方式绘图，最后对绘图结果进行了验证、比较分析。
实验中的数据随机产生，限定了产生的随机距离在10－50之间，显然，距离范围的限定对实验结果的说服力没有影响。
    实验中分别对10个点、20个点、30个点、50个点、100个点的情况下，两种方式绘出的树形图进行了分析对比（固定比例法中r 取0.4）。实验结果显示当节点数达到30个以上时，固定比例法开始出现交叉，当达到50个以上时交叉出现的频率较高。而Inherit法却没有出现交叉，在树形的舒展度和美观上也是不错的。在30个节点的情况下，固定比例法实验程序生成的树形图如图6所示， Inherit法实验程序生成的树形图如图7所示。从图6中明显出现了两处交叉。

　　6、结束语
    Inherit法可以无交叉地绘制赋权树形图，在信息可视化当中可以较好地用节点间距离表示信息。在使用Inherit法确定AreaArc时，由于不会相交，

图6Inherit法结果图（30个节点）

图7固定比例法结果图（30个节点）

    可以从美观均匀角度考虑，采用两端少中间多的规律排序。这种排序方式非常适合扇形区域的特点，将节点最多的子树安排在最中间，而节点较少的子树安排在扇形靠近边界的地方，使得整体布局更加的均匀美观。不过，Inherit法在绘制节点较多的多层树形时，在末端也出现了一定的收缩现象。但信息可视化中的鱼眼技术、过滤技术、局部放大技术都可以很好地完善显示效果。综上所述，在赋权树形图的绘制和布局上，Inherit法是一种较好的绘制布局方法。

　　参考文献
　　[1] 刘光奇,张霭珠,胡美琛. 离散数学[M] . 上海:复旦大学出版社,1988
　　[2] 梁兴建，王小玲.利用Java Applet 动态绘制树型结构图形[J]. 四川理工学院学报（自然科学版）.2006.19（1）:67~70
　　[3] Fruchterman T. M. J , Reingold E. M. . Graph drawing by　force-directed placement. Software-Practice and Experience ,1991 , 21(11) : 1129～1164
　　[4] 管贻生.Java高级实用编程[M].清华大学出版社.2004-01
[5] Analysis and Visualization of Network Data using JUNG