设计原理designprinciples.ppt

基于力导向的图显示 没有原生的顺序，怎么办？ 使用物理模型：边=弹簧；节点=互斥质点 产生漂亮的图显示结果 Highschool dating network 力导向的图显示 非常灵活，对各种类型的图都能生成较好的显示效果 能添加自定义的力 相对容易实现 在计算斥力的循环中，每次迭代的计算复杂度为O(N2) 往往生成局部最优解 图的其它节点链显示方式 正交图 非常适用于显示UML图 算法复杂 环形排列 强调环形的拓扑结构 在社交网络图中广泛采用 嵌套排列 递归式地应用图排列算法 适用于具有层次结构的图 节点链图显示 可理解的视觉映射 能够表现图的总体结构、簇、路径 灵活，有许多变种 几乎所有直观算法的复杂度O(N2) 对于密集的图不是很适用 基于矩阵的图显示 显示图的邻接矩阵而不是节点链 识别出矩阵的模式 矩阵表示 非常适用于密集的图 视觉伸缩性强 能展示图的模式 可视化结果比较抽象 难以跟踪出路径 基于属性的图可视化 除了使用节点的连接关系以外，还使用各个节点的属性 基于节点的属性进行排列 代价小 与应用领域直接相连 难以从多个分离视图中拼凑出总体结构 有时候是不可行的 枢轴图(pivotGraph) 基于属性值“卷制”而成 对于二维情形能同时往两个方向进行卷制 通过观察边的权重能识别图的模式 词组网络 数据可视化基础树与网络 陈为 chenwei@ /home/chenwei/visclass 树与网络 网站图 树的可视化 定义：图 图G由一个顶点（或节点）集合V和一个边集合E组成 每条边exy=(x, y)连接图G的两个顶点x, y 例如：V={1,2,3,4}, E={(1,2),(1,3),(2,3),(3,4),(4,1)} 一组定义 有向图 无向图 加权图 非连通图 顶点的度 回路 无回路图 无回路连通图（树） 具有根结点的树 节点的深度 绘制有根节点的树 递归的方法 可行方案 缩进法 节点链 包含法 分层法 基于缩进 快速并易于实现 可以使用纯文本（或HTML） 浏览大数据时需要很多滚动操作 容易失去上下文 节点链图 简单的递归实现 节点链图的问题 节点数随着深度增加曾几何级数增长 解决方案 将节点在双曲空间分布（节点数仍然随深度曾几何级数增长！） 使用变形 对节点进行过滤 海象（双曲空间） 鱼眼变形 DOI树（节点过滤） Enclosure 为了表达节点的父-子关系，将子节点整个封装在父节点中 树图(Treemaps) 假设每个叶节点具有一个“尺寸”属性（例如磁盘中的文件，或者机构图中的薪水等） 父节点的尺寸是所有子节点尺寸之和 树图的问题 逐级纵横切割细分会产生狭长的四边形 难以与内部节点交互 分层显示 与节点链图相似，但是省略边的绘制 一个方向表示深度 在另一个方向上递归式排列 单词树 网络 图的显示 节点链式显示 分层显示/Sugiyama 力导向 其它 矩阵显示 基于属性的显示 Sugiyama类显示 非常适用于显示具有原生顺序的树 图的“深度”映射到某一坐标轴上 UNIX族谱 Sugiyama 美观、可读性好、自然的自上而下排列 相对快速（依赖于在最小化边交叉时所采用的启发式算法） 不适用于显示不具有原生自顶向下顺序的图 难以实现（可以使用免费的库graphviz, ）