跟Alexander Smirnov聊图形可视化-InfoQ



 写点什么

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

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