Tag Archives: linked list

学习graphviz:画双向队列或者双向链表

我在这篇文章《深入理解FreeBSD中的TAILQ》中需要画队列图举例子,想到的画图工具就是微软的visio,dia,diagram designer,易图等这些所见即所得的画流程图的软件,但是无法画出自己想要的那种效果,或者说要画出那种效果非常难,而且很做作的感觉;于是乎,网上乱搜一番,发现了强大的graphviz软件,画出来的图想当完美;它是AT&T的开源项目,原生的类unix命令行软件,沿袭了unix的文本即一切的思想,类似Knuth教授的tex软件,用文本生成图形。

来自官方网站的介绍(http://www.graphviz.org/):

What is Graphviz?

Graphviz is open source graph visualization software. Graph visualization is a way of representing structural information as diagrams of abstract graphs and networks. It has important applications in networking, bioinformatics,  software engineering, database and web design, machine learning, and in visual interfaces for other technical domains.

我现在要画出下面这个双向队列(或者双向链表)来学习graphviz。

说明(详细信息请见《深入理解FreeBSD中的TAILQ》):

1.这个队列头是queue_head,tqh_first指针指向第一个元素,tqh_last是一个二级指针,是最后一个元素1的tqe_next的地址。数据结构如下所示:

struct int_head {
    struct int_node *tqh_first; /* first element */
    struct int_node **tqh_last; /* addr of last next element */
} queue_head;

2.队列中的元素结构体如下:tqe_next是指向下一个元素的指针,tqe_prev是二级指针,是前一个元素的tqe_next的地址。

struct int_node{
    int num;
    struct int_node *tqe_next;  /* next element */
    sturct int_node **tqe_prev; /* address of previous next element */
};

先来一个简单的,画队列头的代码:

digraph g {
graph [
rankdir = "LR"
];
node [
fontsize = "20"
fontname = "Times-Italic"
shape = "record"
];

head [label = " tqh_first|  tqh_last"];
queue_head [label="queue_head",shape=plaintext];
head:last ->head:first;
head:first ->NULL;
head:last -> queue_head[style=invis,constraint=false];
}

生成这样的图:

解释:
这个图g中有3个节点:第一个节点叫做head,形状是record(可以分层,类似struct),第一层first的文字是tqh_first,第二层的文字是tqh_last;第二个几点叫做queue_head,形状是plaintext,也就是只有文字没有边框;第三个节点叫NULL。接下来是形容他们的指向关系。

下面这段代码生成开始的那个图:

digraph g {
rankdir=LR;
node [
fontsize = "20"
fontname = "Times-Italic"
shape = "record"
];

head [label = "tqh_first| tqh_last"];
first [label = " 2| tqe_next | tqe_prev"];
second [label =" 1| tqe_next | tqe_prev"];
queue_head [label = "queue_head",shape=plaintext]

head:first ->first:num[style=invis];
head ->queue_head[style=invis,constraint=false];
head:first ->first:num;
head:last ->second:next;

first:num ->second:num[style=invis,constraint=false];
first:next ->second:num;
first:prev ->head:first;

second:next ->NULL;
second:prev ->first:next;
}

解释:跟上图类似,只不过指向关系复杂一点。注意:head ->queue_head[style=invis,constraint=false];这行的目的是让queue_head在head结点的下方。

总结:这只是一个用graphviz画图的一个很简单的例子,graphviz在有很复杂的指向关系的时候,它的优势就会非常的突出,因为你不用去关心图形的拓扑细节,有了结点之间的指向关系,graphviz会自动生成相应的布局;更多内容请看下面的参考文献。


参考文献:

这里当然是最权威的文档,命令行的具体用法和图形的属性的详细信息都在这里的文档能找到;但是对于初学者来说,直接看文档可能会让你一头雾水,他们提供了一些具体的例子来学习: http://www.graphviz.org/Gallery.php

Kentbye的Flickr网络相册,这里有更多的例子,是新手入门非常好的资料;

来自icodeit的文章,这篇文章应该是国内介绍graphviz最详细的一篇文章了,强烈推荐。

  • 4.论坛

http://www.graphviz.org/forums/general-discussion

http://stackoverflow.com/

还有问题?到这两个地方问吧。