写点什么

跟 Alexander Smirnov 聊图形可视化

2014 年 2 月 17 日

老话说, “一图抵千言”,在处理复杂的业务数据时,这句话更是至理名言。为了帮助用户理解他们看到的东西,开发人员经常要求助于柱状图和饼图。但那只适用于离散数据;要表示数据之间的联系时,需要用其它工具。为了深入探讨这一主题,我们访问了 Alexander Smirnov, GraphX 的创作者,让他来向我们解释图形可视化是什么,以及如何使用它。

Alexander Smirnov: 我们先来定义一下图形是什么。图形是一组对象(节点)的表示,其中有些对象通过某种联系连接在一起。所以图形可视化的主要任务是以对用户友好的、可理解的方式显示这样的数据。比如说,如果你有一个树状数学图,你应该想用树节点布局显示它。或者说,如果你要显示大量有很多联系的无结构数据(比如 Twitter 或 Facebook 的用户连接),你可能会希望使用一些特殊的布局,一种能帮你取得最大可读性的任何数据展示方法。

(点击图片可以放大)

所以在这一点上,为了完美地实现图形可视化,我们必须解决三个问题:创建节点布局,消除节点重叠,提供有效的边路由算法。

首先,我们要为图形创建节点布局。这个布局定义了图形中所有节点会如何显示的主要模式和逻辑。GraphX 提供了很多预定义的布局算法,可以直接使用,比如说, Tree 或Circular 算法会用树形或环形显示节点。

(点击图片可以放大)

第二个任务是消除节点重叠。在这项任务中,我们力求更精确地计算出布局中每个节点位置,确保它们彼此之间没有任何重叠,所有节点都清晰可见。

第三个,也是最后一个任务,是在我们的布局中显示节点间的联系。最简单的实现方法是把所有联结的节点用直线连起来,但对于很多复杂的布局而言,这可能不具有可行性。所以我们必须执行一个被称之为“边路由”的任务,为所有连接计算优化路径。GraphX 提供了一些预定义的边路由算法,可以绕过域上的节点或执行边捆绑技术。

(点击图片可以放大)

InfoQ: 在计算机科学中,我们倾向于命名和研究众所周知的排序算法。有众所周知的图形布局和边路由算法吗?

Alexander Smirnov: 我认为最有名的图形布局算法是 Fruchterman-Reingold (FR) 力导向 (或基于能量的) 布局算法。力导向算法的主要目的是把图形节点放在二维或三维空间中,基于它们的相对位置在这些节点中间进行力的分配,这样所有的边都或多或少地变成了等长的,并且尽可能地减少边的交叉。通常来说,大量的力导向图形布局看起来就像飞溅的颜料:)

在 FR 算法中,力向量之和决定了节点应该向哪个方向移动。步宽是一个决定节点单步应该移动多远的常量。当系统的能量达到最小时,节点停止移动,系统达到了它的平衡状态。这种算法的缺点是如果我们定义的步宽是常量,则根本无法保证系统会达到平衡状态。T.M.J. Fruchterman 和 E.M. Reingold 引入了一个"全局温度",控制节点移动的步宽和算法的终止。步宽跟温度成正比,所以如果温度高,节点移动的就快(即每一步的距离都比较远)。所有节点的温度都是一样的,并且每次遍历都会降温。一旦节点停止移动,系统就会终止。

InfoQ: 您能解释下边捆绑是什么吗?

Alexander: 边捆绑是一项边路由改善技术,把向同一个方向前进的边捆绑在一起。它通过减少大图形上不可避免的视觉杂波改善图形的可视化,这样可以发现高层的边模式,只要看一下就能得到图形的总体概况。

边捆绑算法实现了力导向技术,吸引中间边路由指向彼此。因此这一结果被称为边管道,看图时很容易注意到。GraphX 还实现了边弯曲技术,通过让中间边路由点之间的边连接更平滑而使边更好看。

没有边捆绑

(点击图片可以放大)

有边捆绑

(点击图片可以放大)

InfoQ: GraphX 是基于比较老的 Graph#库的。您也参与了那个项目吗?

Alexander: 不,我没参与过。但在自己的工作中,我逐渐熟悉了 Graph#的代码,现在我尽我所能回答用户在 CodePlex 的 Graph#版块上提出的问题。

InfoQ: Graph#中的什么问题促使你编写了 GraphX?

Alexander: 首先是因为它过时了。并且通常你并不知道它是什么意思: 没有产品支持,没有错误修订,没有改进,等等。但在我试着完成一个类似的任务时,遇到的主要问题是性能问题和库的可扩展性。

那时候我要处理将近 2000 个节点的可视化,这些节点间有很多联系,而原来的 Graph# 花了很长时间也没能计算和显示出那些数据。所以我重写了代码,让它变得更快,比如把边终点计算从模板调用挪到类的代码中,并且简化了高亮逻辑,排除了很多事件调用和交互。

至于扩展问题… 这可能是我的个人观点,但 Graph#看起来扩展能力有限。在 CodePlex 上有那么多讨论,看起来很明显,但实际上需要修改 Graph#,还要了解它的代码。在创建 GraphX 的过程中,我一直在思考这个问题,我做了一个灵活的架构,这类问题大部分都已经解决了,不需要挖掘类库的内部代码。

不管怎么说,Graph#是一个杰出的作品,特别是在图形算法实现方面。

InfoQ: 哇,2000 个节点看起来相当多。您认为上限是多少,在屏幕乱到用户无法理解之前可以渲染多少个节点?

Alexander: 这个问题在很大程度上取决于最终用户想要用图形解决什么问题。比如说,当你想显示 Twitter 用户间的总体连接方式时,一般需要显示海量的节点和联系。将 LinLog 布局算法和边捆绑技术结合起来,你可以极大避免屏幕混乱,并且能得到图形概览,可以看到不同的用户组跟其余连接是分离开的。从另一方面来看,如果你用树形布局显示相同的 Twitter 连接,你会得到一个非常巨大的结构化图形,因为图形节点非常小,所以图形概览让人根本无法看懂。

你必须决定自己想达成什么目标,以及什么布局或边路由算法更适合你的任务。GraphX 为最终用户提供很多预定义的算法,以及轻松实现定制算法的能力,并且可以把它们用在 GraphX 引擎内。

所以你看,GraphX 有一些可帮助处理屏幕混乱的工具,可以说能渲染的准确节点数量取决于要解决问题所选择的方式。

InfoQ: 您在 GraphX 中用 Graph# 的代码了吗,还是只用了其中的概念?

Alexander: 好吧,我想我可以回答是的和是的。大部分算法代码都是来自于 Graph#的,原封不动,只是改了一些外部接口。我不想在那些已经实现了的东西上浪费时间,而是把主要精力集中在新的代码架构概念上。我从 Graph#上借鉴了一些在我看来合理的概念。我竭尽所能把计算过程和渲染分开,以便可以单独改进每一部分的逻辑,但有些逻辑和可视化仍然结合的非常紧密。

InfoQ: 你对重用其它项目的代码和将其它项目作为编译库引入有什么看法?在您看来在做这两个选择时有什么特定的原因吗?

Alexander: 这个问题没有标准答案。那取决于你要从类库中得到什么。在 GraphX 中使用外部库时,两种方式都有。比如说,华丽的 YAXLib 库提供了我需要的所有串行化功能,而且它没有任何额外的组件,所以我原封不动地把它引入到了我的项目中。另一方面,我决定只在我的项目中引入 ZoomControl 和 Zoombox 的代码,以便可以在不同的情境中修改它们的行为,比如不同的缩放模式或鼠标动作。

所以总体而言,我建议你在类库满足如下条件时引用它们:

  • 它们完全满足你对功能和性能的需要
  • 它们内部没有垃圾或过剩的代码 / 组件
  • 你不太会被类库的升级困扰
  • 你不介意在你的程序文件夹中多一个 DLL 文件

否则就把它们的代码集成到你的项目中,并按你想要的方式进行定制。这两种情况无论哪一个,性能一般都不成问题,除非引用太多而延长了程序启动的时间,并且占用了更多内存。

InfoQ: 你有没有遇到过那种情况,你想合并另一个项目中的代码,但因为那些代码用了不同的许可而无法进行?

Alexander: 谢天谢地,我还没遇到过那样的状况。我相信如果要分享项目代码,应该允许人们自由地使用和修改它。作为交换,那些使用它的人应该把它的许可声明和版权包含在它们的项目中。

InfoQ: 您有把 GraphX 放到 Windows 8 商店或 Windows Phone 8 中的计划吗?

Alexander: 那还不在我的任务列表中,但很有可能。我在寻找把 GraphX 扩展到不同平台上的机会,但这是时间和认识上的问题。比如说,经过对 Silverlight 的研究,我最终认为那将耗费我大量的时间和精力,因为几乎所有的渲染和模板代码都要重构。尽管如此,在 Silverlight 和 GraphX v2 上的工作已经开始了,虽然缓慢但那是真的。

至于 Windows 8 和 WP8,我可以说我很有兴趣去了解这些平台,因为我还没在上面做过任何东西。它们很有创新性,并且用了跟 WPF 相似的技术,所以它一定很有趣,并且跟其它可用方案比应该更简单。

InfoQ: 如果想在网站上做出类似的可视化效果,你应该做什么呢?

Alexander: 哦,那取决于我应该以什么为基础。如果我用已有的 GraphX 代码,那么自然应该用 Silverlight 做可视化,因为它的渲染用的是简化过的 WPF 技术。大部分逻辑应该原封不动,但我必须从头开始做些新的控件,并且在整个项目框架中引入异步处理逻辑。

老实说我不了解其它任何用来实现图形可视化的 web 技术。我觉得 Flash 或其它相似的技术可以用来完成这项任务,但 GraphX 代码估计够呛,所以还有很多工作要做。

InfoQ:您正在为 GraphX 寻找志愿者吗?

Alexander: 当然,GraphX 很乐意看到有人加入。特别是愿意参与 GraphX 到各种平台上的移植工作的,和实现新的图形布局和边路由算法的志愿者。如果你有这方面的技能,并且愿意参与 GraphX 的改进工作,请联系我

InfoQ: 那是 GraphX 的新首页吗?或者你不想再用 CodePlex 了吗?

Alexander: 这是个新网站,我会把 GraphX 的首页放在上面,还有我其它在“Panthernet Dev Works”公司下的项目。Codeplex 仍然是主代码库和发布通知网站,但文档、下载和讨论会挪到这个新网站和论坛上。

目前我有意做自己的公司,主要从事开源和商业项目的开发。论坛上会有更多相关信息,所以感兴趣的人可以上去看看。

InfoQ: 那么您目前有多少个不同的图形界面和边路由算法?

Alexander: GraphX 目前有 11 个布局,2 个叠加移除和 3 个边路由预定义算法。而且就像我之前说过的,你可以在 GraphX 中创建和使用自己创建的算法,我们提供了接口。

算法是这个类库中最重要也是最复杂的部分。随时欢迎有用户在这方面做出贡献!

关于受访者

Alexander Smirnov, .NET 首席开发人员,目前就职于俄罗斯的"I.T. co.",主要工作领域是数据可视化和文本分析。他还参与了几个使用 C#开发移动端平台程序的项目。

原文英文链接: Introduction to Graph Visualization with Alexander Smirnov

2014 年 2 月 17 日 20:202229
用户头像

发布了 45 篇内容, 共 22.5 次阅读, 收获喜欢 3 次。

关注

评论

发布
暂无评论
发现更多内容

数字货币交易平台源码,数字货币交易所开发核心功能

13530558032

区块链支付新模式开发,USDT支付系统搭建

13530558032

42图揭秘,「后端技术学些啥」

我是程序员小贱

架构师训练营 -- 第 12 周作业

stardust20

我所在公司和大数据

2流程序员

2020-08-29-第十二周作业

路易斯李李李

所按非所得——聊一聊StandHogg漏洞

OPPO安全

安全攻防 安全 安全开发 漏洞

数字资产钱包开发,数字加密货币app搭建

13530558032

云算力挖矿平台APP,算力挖矿建设开发

13530558032

FlinkX 如何读取和写入 Clickhouse?

Apache Flink

flink

十年Java开发传奇经历:我是如何从外包逆袭成为大厂架构师的

Java成神之路

Java 程序员 面试 微服务 多线程

【Spring Boot系列】之多种依赖集成方式

TinyKing

2020-08-29-第十二周学习总结

路易斯李李李

甲方日常 5

句子

工作 随笔杂谈 日常

你真的知道什么是线程安全吗?

老胡爱分享

并发编程 线程 java 并发

cookie和session的关系看这一篇就够了

架构师修行之路

session Cookie

Docker 私有镜像仓库的搭建及认证

哈喽沃德先生

Docker 容器 微服务 镜像 容器技术

架构设计开学第一天

escray

学习 从零开始学架构 架构师预科班

Week 12 命题作业

Jeremy

oeasy教您玩转linux010201持续输出yes

o

区块链助力军事人力资源配置

CECBC区块链专委会

区块链 军事

大数据应用场景

dongge

互联网人必备知识cookie和session认证

架构师修行之路

分布式 身份认证 session Cookie

Flink SQL FileSystem Connector 分区提交与自定义小文件合并策略

Apache Flink

flink

大数据解答(一)

dony.zhang

大数据 mapreduce

kubernetes node affinity 写法

Geek_f24c45

Kubernetes

第九周

Acker飏

Atlassian Team Playbook | 用户体验画布挖掘业务价值

Atlassian

团队管理 敏捷开发 Atlassian

Week 12 学习总结

Jeremy

AtlassianTeam Playbook | 用户体验中的移情地图

Atlassian

团队管理 敏捷开发 Atlassian

微服务架构下的系统集成

码猿外

架构 微服务 系统集成

演讲经验交流会|ArchSummit 上海站

演讲经验交流会|ArchSummit 上海站

跟Alexander Smirnov聊图形可视化-InfoQ