Graph Visualization及常用工具简介

snachina

在很多算法中都需要用到图(Graph)这种数据结构，但图的计算机实现相对复杂，调试时往往无法直观的看出结果是否符合要求。图的可视化(Visualization)技术可以解决这个问题。这种技术可以将图的逻辑结构形象的在2维平面上表示出来，以进行直观的演示。比如这个demo可以形象的表达二叉排序树的插入过程。可能更重要的是，通过观察图的可视化结果，我们可以得到一些有意义的结论，从而指导进一步的工作和研究。比如下面的图(来源)是一个大程序的模块调用图。它可以直观的表示模块之间的依赖关系，从而为高效测试提供依据。这篇文将会简单介绍（Windows平台下）几种常用的GraphVisualization工具。

图1 Graph Visualization结果示例

NodeXL

NodeXL(Network Overview, Discovery and Exploration for eXceL)是一个微软的开源Graph Visualization工具。如同其他微软的优秀产品一样，学习前期上手非常快，后期又提供丰富的功能和灵活的定制性。

图2 NodeXL可视化结果示例（来源）

NodeXL的使用非常简单。它是作为一个Excel模板安装的。安装完成后打开Excel，根据NodeXLGraph新建一个xls文档就可以使用了。在Vertex工作表中填入顶点的相关信息，Edge工作表中填入边的相关信息，单击边栏中的Show Graph，一切就搞定了。各种基本操作非常直观，自动布局算法的改动，顶点的手动拖动，缩放在GUI中都可以轻松完成。而顶点和边的各种属性也可以在xls表格中更改。

其中比较亮点的功能是可以用图片作为图的顶点。这就带来了很大的灵活性。比如下图是对The Big Bang Theory某一集构建的人物关系图，边的粗细代表人物关系的密切程度。对于很密切的关系，边被着成红色。

图3 TBBT某一集的人物关系图

此外，Excel这个平台为用户集中精力在分析数据本身上提供了很大方便。点点鼠标我们就可以方便的对数据进行批量处理：排序，过滤，绘制各种图表，而不用考虑如何编写代码，如何处理GUI事件。值得一提的是，NodeXL还支持多种输入格式，除了简单的复制粘贴外，还可以直接导入流行的UCINET, GraphML的格式文件，或者最简单的邻接矩阵等。它甚至还提供了自动收集twitter，flickr上的数据并绘制图表的操作选项。

当然，NodeXL还提供了高度的可编程性。在.NET中我们可以方便的调用它在Excel中体现的全部功能。事实上，Excel的模板只是它的一个wrapper而已。

Graphviz

看完了华丽的界面，强大的GUI，与Office无缝整合，.NET支持等一些列充满微软色彩的NodeXL，下面就是来自开源界且同样强大的Graphviz。Graphviz是典型的*nix编程思想的结晶，与NodeXL相比恰如LaTeX与Word般特色鲜明。命令行，stdin输入stdout输出，自己建立了一套描述图的语言，跨平台，方便获取的源码。它的每一个特性都彰显着*nix的优雅和强大。

因为是命令行工具用文本进行输入，因此可以方便的被各种平台调用。.NET, C/C++, Java, MATLAB… 不用考虑wrapper或者P/Invoke。而它用来描述图的语言同样简洁强大。比如这样的代码就会编译生成下图所示的图：graph g { a −− b −− c; }

图4 Graphviz输出示例

各个顶点和边的属性同样可以用语言指定。唯一比较遗憾的是似乎只支持eps格式的图片做顶点。作为从Windows平台出来的人，我也不晓得一般的图片能不能转成eps，怎么转。还希望各位指教。（经过Milo Yip的指点，发现可以用一般图片做顶点，在此表示感谢！）

其他

此外，比较有名的和图相关的库还有GLEE, Quick Graph和UbiGraph。GLEE是MicrosoftResearch做的一个自动布局图（AutomaticGraph Layout）的库，NodeXL中就使用了它。Quick Graph是一个图的算法库，更偏重于图的相关算法。UbiGraph是一个非常强大的GraphVisualization的库，文章开头的二叉排序树的demo就来自于它，但由于不支持Windows而且似乎需要配置服务器所以就没能试用了。

这篇文主要介绍了Graph Visualization是什么，有什么用，以及可以调那些库来实现。感觉Graph Visualization还是一个很有意思的东西，把一些数据可视化一下说不定就会有一些有意义的发现。