Graphviz介绍 (转载)

graphviz是贝尔实验室几个计算机牛人设计的一个开源 的图表(计算机科学中数据结构中的图)可视化项目，主要用C语言实现，主要实现了一些图布局算法。通过这些算法，可以将图中的节点在画布上比较均匀的分布，缩短节点之间的边长，并且尽量的减少边的交叉。

graphviz提供命令式的绘图方式，它提供一个dot语言 用来编写绘图脚本，然后对这个脚本进行解析，分析出其中的定点，边以及子图，然后根据属性进行绘制。具体的可以看一个例子，这个例子来自官方的文档。

Dot代码

1. digraph G {   
2.     main -> parse -> execute;   
3.     main -> init;   
4.     main -> cleanup;   
5.     execute -> make_string;   
6.     execute -> printf   
7.     init -> make_string;   
8.     main -> printf;   
9.     execute -> compare;   
10. }  

digraph G {

 main -> parse -> execute;

 main -> init;

 main -> cleanup;

 execute -> make_string;

 execute -> printf

 init -> make_string;

 main -> printf;

 execute -> compare;

}

digraph指定该图是一个有向图(directed graph)，->表示一条边，main,parse,execute等是顶点，运行出来的效果很好看，如下图：

需要注意的是，我在这个dot脚本中没有指定任何的关于图的位置的信息，布局器会自动的根据图形的类型进行布局，并最终展现出来。

再来看一个比较复杂，并且是程序员经常使用的功能，数据结构图：

Java代码

1. digraph g {   
2.     node [shape = record,height=.1];   
3.     node0[label = "<f0> |<f1> G|<f2> "];   
4.     node1[label = "<f0> |<f1> E|<f2> "];   
5.     node2[label = "<f0> |<f1> B|<f2> "];   
6.     node3[label = "<f0> |<f1> F|<f2> "];   
7.     node4[label = "<f0> |<f1> R|<f2> "];   
8.     node5[label = "<f0> |<f1> H|<f2> "];   
9.     node6[label = "<f0> |<f1> Y|<f2> "];   
10.     node7[label = "<f0> |<f1> A|<f2> "];   
11.     node8[label = "<f0> |<f1> C|<f2> "];   
12.     "node0":f2 -> "node4":f1;   
13.     "node0":f0 -> "node1":f1;   
14.     "node1":f0 -> "node2":f1;   
15.     "node1":f2 -> "node3":f1;   
16.     "node2":f2 -> "node8":f1;   
17.     "node2":f0 -> "node7":f1;   
18.     "node4":f2 -> "node6":f1;   
19.     "node4":f0 -> "node5":f1;   
20. }  

digraph g {

 node [shape = record,height=.1];

 node0[label = "<f0> |<f1> G|<f2> "];

 node1[label = "<f0> |<f1> E|<f2> "];

 node2[label = "<f0> |<f1> B|<f2> "];

 node3[label = "<f0> |<f1> F|<f2> "];

 node4[label = "<f0> |<f1> R|<f2> "];

 node5[label = "<f0> |<f1> H|<f2> "];

 node6[label = "<f0> |<f1> Y|<f2> "];

 node7[label = "<f0> |<f1> A|<f2> "];

 node8[label = "<f0> |<f1> C|<f2> "];

 "node0":f2 -> "node4":f1;

 "node0":f0 -> "node1":f1;

 "node1":f0 -> "node2":f1;

 "node1":f2 -> "node3":f1;

 "node2":f2 -> "node8":f1;

 "node2":f0 -> "node7":f1;

 "node4":f2 -> "node6":f1;

 "node4":f0 -> "node5":f1;

}

运行后的效果如下图所示：

不知道其他的程序员怎样，反正我对命令行情有独钟，比较喜欢这一类的工具。最早接触的计算机系统正是一个没有图形系统的BSD，由此对命令行的，没有界面的程序都特别感兴趣。

相关的想法

自从使用了graphviz以后，一直想着把这个好东西移植到java下来，大概的思想跟graphviz类似：

• 解析dot脚本，生成图的对象，这个图中包括节点，边以及子图等对象，这些对象上都绑定着相应的属性
• 将解析出来的图对象发送给layout engine进行处理，layout engine可以选择布局策略，比如流布局等
• 从layout engine中得到布局后的图对象，并交给image engine处理，得到最终结果，负责展示或者保存等

dot 的语法定义比较简单，我已经用javacc构造了一个dot的分析器，现在可以从dot文件中构建出图对象出来，不过还需要进一步完善，可以看看这个BNF定义：

Java代码

1. graph -> [strict] (digraph|graph) id '{' stmt-list '}'  
2. stmt-list -> [stmt [';'] [stmt-list] ]   
3. stmt -> attr-stmt | node-stmt | edge-stmt | subgraph | id '=' id   
4. attr-stmt -> (graph | node | edge) attr-list   
5. attr-list -> '[' [a-list] ']' [attr-list]   
6. a-list -> id '=' id [','][a-list]   
7. node-stmt -> node-id [attr-list]   
8. node-id -> id [port]   
9. port -> port-location [port-angle] | port-angle [port-location]   
10. port-location -> ':' id | ':' '(' id ',' id ')'  
11. port-angle ->'@' id   
12. edge-stmt -> (node-id | subgraph) edgeRHS [attr-list]   
13. edgeRHS -> edgeop (node-id | subgraph) [edgeRHS]   
14. subgraph -> [subgraph id] '{' stmt-list '}' | subgraph id  

graph -> [strict] (digraph|graph) id '{' stmt-list '}'

stmt-list -> [stmt [';'] [stmt-list] ]

stmt -> attr-stmt | node-stmt | edge-stmt | subgraph | id '=' id

attr-stmt -> (graph | node | edge) attr-list

attr-list -> '[' [a-list] ']' [attr-list]

a-list -> id '=' id [','][a-list]

node-stmt -> node-id [attr-list]

node-id -> id [port]

port -> port-location [port-angle] | port-angle [port-location]

port-location -> ':' id | ':' '(' id ',' id ')'

port-angle ->'@' id

edge-stmt -> (node-id | subgraph) edgeRHS [attr-list]

edgeRHS -> edgeop (node-id | subgraph) [edgeRHS]

subgraph -> [subgraph id] '{' stmt-list '}' | subgraph id

(最近老是感觉时间不够用，有很多有意思的项目要做，比如要完善前几天说的那个bbms(Bus Based Message Service), 再比如修改用Swing和Smack做一个jabber的客户端jTalk，都是很有搞头的，唉，扯远了。)

当然graphviz的功能不至于此，它提供一个lib，可以用来将绘图引擎嵌入在自己的应用中。这是一个很有意义的事，我们可以不必掌握布局部分的复杂算法，把精力放在业务逻辑部分，将最后的图对象交给这个引擎来处理即可。当然，如果你正好和我一样，想了解其神奇的布局算法，不妨翻翻它的源码，欢迎交流之至。

我在周末分析了下graphviz的内部结构，并建立了一个java的项目jraph ，用来做简单的移植，主要是学习之用，其实，Java的图库还是相当丰富的，比如JGraph ，JGraphT，Prefuse，TouchGraph等等，用来做项目当然是很便捷的，但是我还是比较喜欢看着一个算法被自己实现的过程，特别是这种比较神奇的算法，哈哈。

预期中的API如下：

Java代码

1. public static void main(String[] args){   
2.     Parser parser = new GCodeParser("file.g");   
3.     GraphSet gs = parser.parse();   
4.     GraphSet layouted =    
5.         new GraphLayoutEngine(gs).layout();   
6.     ImageEngine imgEngine =    
7.         new GraphImageEngine(layouted);   
8.     imgEngine.export(0);   
9. }  

 public static void main(String[] args){

  Parser parser = new GCodeParser("file.g");

  GraphSet gs = parser.parse();

  GraphSet layouted = 

   new GraphLayoutEngine(gs).layout();

  ImageEngine imgEngine = 

   new GraphImageEngine(layouted);

  imgEngine.export(0);

 }

同graphviz一样，先调用分析器构造出图的集合GraphSet(包括多个图，每个图中包括Vertex，Edge，及SubGraph)，然后进行布局，最后将通过布局后的GraphSet绘制结果。目前完成了框架的设计部分，分析器部分基本完成，layout部分只实现了一个策略，即force-based 布局算法，不过layout engine被设计成可以插拔的模型，如果有了新的算法实现，可以很容易的整合起来。