射线型布局算法简述

1、可视化布局算法布局算法是整个拓扑可视化系统的核心问题,选择合适的布局策略能够更好的切合用户需要解决的问题、能够更好的进行拓扑图形的绘制和实现。布局算法主要需要解决的问题是如何确定和分配映射在显示界面上的几何图形的各个节点和边的以坐标表示的具体位置,简单的说也就是为可视化图形中的每一个节点和边分配其显示在界面上的坐标。一个适合的良好的拓扑布局算法,能够有效地避免显示出来的拓扑结构图中节点的重叠,能够大大的减少拓扑结构图中边之间的交叉,能够更加美观大方的展示出要处理的网络的拓扑结构,能够使管理人员更方便的获取网络信息、进行网络管理。拓扑绘图布局算法根据其作用和特征的不同可以分为很多不同的类别,这里

2、从网络拓扑可视化的角度出发,将整个拓扑绘图布局算法分为物理布局算法和网络布局算法两类。所谓物理布局,就是将节点的地理位置信息简单的解析为与其相对应的布局坐标,使得在拓扑图中能够清晰的发现节点的位置信息以及节点之间的相对位置和相对距离。拓扑节点相关地理位置属性的映射和展示对于与地理位置相关的网络拓扑可视化来说有着极其重要的意义,但是也正是由于物理布局算法的这个特性使得这种方法相对来说更加适用于主干网络拓扑的可视化,而对于相对细致的局部网络或者主干网络之下的子网络的可视化则显得并不合适。物理布局算法中最具代表性的方法是地理位置映射算法,很多以主干网络为研究对象的网络拓扑工具和网络拓扑系统都是采用这

3、种算法,这其中比较著名的有以平面方式解析展示网络节点地理信息的和以及在三维球体上解析展示节点地理信息的。逻辑布局算法与物理布局算法最大的不同就在于,逻辑布局算法不用去考虑节点在网络中的实际地理位置,只需要根据网络拓扑得到的具体节点的情况来设计分配节点的布局空间和布局策略。逻辑布局算法让人们在设计实现布局的过程中,可以充分的针对现实问题分析解决办法,可以充分的利用图相关算法的技术和理论进行拓扑图的布局和绘制,可以不依赖网络节点物理位置的情况,更好的关心和研究网络节点的相互关系和网络拓扑图的内在特性。逻辑拓扑布局算法是网络拓扑可视化过程中重要的实现方法,是研究网络拓扑可视化技术的重要工具, 在逻辑

4、拓扑布局算法的研究和开发过程中,产生了许多著名的布局算法,使得逻辑拓扑布局算法得到了巨大的发展。射线型布局算法射线型布局算法在一定程度上可以说是树型布局算法的极坐标形式,它要求在形成布局图之后,图中任意一个节点到中心节点的距离都是图形中两点之间的最短路径,也就是说在射线型布局算法中,中心点的选择会根据节点的度数和节点到叶节点的最短距离来综合考虑,一般会选择节点度数较大或者到叶节点最短距离最大的节点作为布局图的中心点。使用射线型布局算法,设计实现比较简单,能够清晰的展示节点数目较多的网络拓扑结构,且设备的放置不易产生重复,空间利用率较高,生成的网络拓扑结构图效果比较好,但是同样存在的问题是这种布

5、局算法也比较适合于中小型网络拓扑的绘图布局,而不太适合于大型网络拓扑的布局。射线型布局算法在具体构图实现的时候首先找到根节点,也就是等级最高的节点,将它放置在整个图的中心位置上然后寻找此根节点的子节点,将这些子节点均匀分布在以根节点为圆心的圆上这些子节点若还有子节点,则将这些子节点以它们的父节点为圆心做均匀分布最后依次递归重复第三步直至所有的节点都被遍历之后整个算法结束,算法流程图如图所示系统设计原则1. 清晰的网络层次作为拓扑图显示介质的屏幕的大小是有限的,而需要表现的网络结构却是非常复杂的,这使得在一张有限的画图上尽可能的展现网络拓扑的细节变的非常困难,而清晰的网络层次却是认识网络结构的前

6、提,所以在进行系统设计的时候,更要注意对于图像层次性的把握和处理。2. 明确的连接关系网络拓扑图应该具有良好的可读性,应该尽可能注意图中节点位置、距离等因素,以求尽可能体现出实际网络的结构信息,减少节点连线间的交叉,考虑网络中可能存在的环路情况,同时对于图中节点的类型和参数应该具有良好的表现,应该明确体现出不同设备节点之间的区别和联系。3. 良好的操作性能在一个拓扑可视化系统中应该具有良好的操作性,应该允许网络管理员或者用户对于网络拓扑图的布局、连线等进行改动和调整,而且,这些手工的改动应该能够被系统记录和保存,以保证拓扑图显示的一致性。4. 完善的交互功能拓扑可视化系统作为网络管理系统中的一

7、个可视化模块,负责将各种网络相关信息以图形化的方式直接呈现给用户,是与用户交流较多的一个部分,一个较好的拓扑可视化系统应该充分的考虑与用户的交流和反馈,应该具有良好的交互模式和友善的操作界面。射线型拓扑布局算法实现射线型布局算法与树型布局算法有很多共同的地方,同树型布局算法一样, 射线型布局算法,程序设计实现方面比较简单,能够清晰的展示节点数目较多的网络拓扑结构,在具体放置设备的时候不易产生重复,绘图空间利用率较高,它生成的网络拓扑结构图,结构清晰,层次分明,画面整洁,易于分析和理解整个网络拓扑结构。但是同树型布局算法一样,射线型拓扑布局算法存在的问题也是比较适合于中小型网络拓扑的绘图布局,而当节点数量变得很多时,射线型布局算法就显得有些不合适了,产生的拓扑图也开始变得拥挤,大大降低了拓扑图的展示效果。在射线型拓扑布局算法中,核心部分的节点坐标计算方法与树型拓扑布局算法中有所不同。在射线型拓扑布局算法中,子节点不再排布在父节点的下方呈树型结构,而是排