BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

跟Alexander Smirnov聊图形可视化

| 作者 Jonathan Allen 关注 612 他的粉丝 ,译者 吴海星 关注 0 他的粉丝 发布于 2014年2月18日. 估计阅读时间: 13 分钟 | QCon上海2018 关注大数据平台技术选型、搭建、系统迁移和优化的经验。

老话说, “一图抵千言”,在处理复杂的业务数据时,这句话更是至理名言。为了帮助用户理解他们看到的东西,开发人员经常要求助于柱状图和饼图。但那只适用于离散数据;要表示数据之间的联系时,需要用其它工具。为了深入探讨这一主题,我们访问了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

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT