雷达图和加权图布局算法的研究与实现

摘要

图是一个抽象数据结构，常用于为信息结构建模。图能够为现实世界中对象的信息建模，表示对象之间的关联关系。近年来，对信息技术可视化的研究越来越广泛，信息技术可视化也在各个领域中得到越来越广泛的应用。图布局是利用图结构解决现实世界中信息可视化问题的一种重要技术。
　　图布局问题主要解决的是图中节点的布局问题。用图布局算法，将散乱的信息用一种清晰的方式展示。用图布局算法绘制的图形需要满足图布局的美学标准，这对算法的设计有较高的要求。算法的效率也是要解决的主要问题之一。在图布局算法中还要考虑布局规模和布局约束问题，要满足实际应用的需求。
　　本文研究和实现了两种图的布局算法:雷达图布局算法与加权图布局算法。
　　雷达图用于表示现实世界中实体之间的传递关联关系。在一个图的布局中，选定一个主节点，从这个主节点开始逐级向外辐射，形成若干个雷达环。除主节点外，其它节点按关联的层次分布在各个雷达环上，雷达图布局算法展示了这种传递关联关系。
　　目前文献中研究的图布局算法基本上都是基于无权图的。本文给出了加权图的图布局算法，既考虑了常规图布局算法中节点的均匀分布问题，也考虑了加权图中边的权重展示问题，在布局中从常规的等长边展示改变为考虑边长与权重按照比例展示。
　　在图布局算法的研究和开发过程中，对算法的可行性和可用性反复进行了测试和修改，最终得到了可行实用的程序。
　　为了使编写的程序能结合实际的应用，编写了算法程序的应用接口。使本文开发的图布局算法程序能正确地被应用程序调用。
　　最后，在论文中给出了本文两个图布局算法的应用例子。

目录

声明

摘要

第一章 绪论

1．1 概述

1．2 研究背景与意义

1．3 国内外研究现状

1．4 论文研究内容

1．5 论文组织结构

第二章 图的可视化概念

2．1 概述

2．2 图论基础

2．3 图的可视化研究

2．4 图可视化的任务

2．5 图布局的美学标准

2．6 本章小结

第三章 雷达图的研究与实现

3．1 概述

3．2 雷达图的概念

3．3 最小生成树

3．4 雷达图节点位置计算

3．5 绘制雷达图算法

3．6 本章小结

第四章 加权图的图布局

4．1 概述

4．2 图布局的弹力模型

4．3 FR算法与KK算法

4．3．1 FR布局算法

4．3．2 KK布局算法

4．4 加权图的图布局

4．4．1 加权图的布局问题

4．4．2 加权图的布局设计

4．4．3 加权图的布局算法

4．5 本章小结

第五章 算法实现与应用

5．1 概述

5．2 开发环境与工具

5．3 图布局的初始化算法

5．3．1 随机算法

5．3．2 椭圆算法

5．3．3 质心算法

5．4 雷达图和加权图应用举例

5．5 本章小结

第六章 总结与展望

6．1 工作总结

6．2 展望

参考文献

致谢