GT-ITM生成的图结构说明

最近做网络实验需要用GT-ITM生成拓扑图，搜索了一下网上所有的资料基本都是在谈gt-itm如何与ns2结合生成实验用的拓扑图，而实际上gt-itm是用来生成网络拓扑图的工具，只要了解了gt-itm生成的图的具体结构，自己可以写代码将gt-itm生成的图表示出来，而不一定要借助于ns2工具。
    gt-itm主要生成两种形式的图，Random Graph Models和Transit-Stub Models，关于其生成图的原理，专门有论文论述，这里也不再详述了，简单来说本文的内容是如何根据gt-itm产生的图文件，还原出图的数据结构，因为这也是初学时最困扰我的东西。
    gt-itm的图结构主要是借助Standard GraphBase的形式表示，Standard GraphBase也是个很复杂的东西，好像knuth整整用了一本书 来阐述它，这里仅简单介绍一下要用到的部分。最好的方法就是从源代码入手，先看一下gt-itm中包含的gb_graph.h文件，列一下要用到的数据结构：
       

typedef union{
     struct vertex_struct *V;
     struct arc_struct *A;
     struct graph_struct *G;
     char *S;
     long I;
}util;

/* 顶点结构 */
typedef struct vertex_struct{
     struct arc_struct *arcs;
     char *name;
     util u,v,w,x,y,z;
}Vertex;

/* 弧结构 */
typedef struct arc_struct{
     struct vertex_struct *tip;
     struct arc_struct *next;
     long len;
     util a,b;
}Arc;

/* 图结构 */
typedef struct graph_struct{
     Vertex*vertices;
     long n;
     long m;
     char id[ID_FIELD_SIZE];
     char util_types[15];
     Area data;
     Area aux_data;
     util uu,vv,ww,xx,yy,zz;
}Graph;

   由此我们知道gt-itm生成的图是用邻接链表的形式表示出来的。
   看一下转换文件代码sgb2alt.c，这段代码的目的，是将由itm命令直接生成的.gb扩展名文件表示的图转换成.alt扩展名文件表示的图，.alt文件非常好理解，就是普通的形式。注意到代码中有这样一个函数：restore_graph，这个函数非常关键，其实也是sgb中定义的函数，它的引用文件是gb_save.h，在gt-itm中只是包含了头文件，没有函数定义，因此只有将sgb的代码下载下来，打开gb_save.w文件仔细阅读，这样所有的关于图生成与保存的全部疑问都解决了，这里仅仅是把其中的关键部分翻译一下，为了清楚的说明，以下面的文件为例，这也是gt-itm自带的样例文件
      

* GraphBase graph (util_types ZZZIIZIZIZZZZZ,14V,102A)
"geo(0,{10,10,3,0.200,0.000,0.000})",10,28,10
* Vertices
"0",A4,3,4
"1",A6,8,6
"2",A8,7,6
"3",A14,6,0
"4",A18,8,1
"5",A22,0,3
"6",A17,4,0
"7",A24,3,6
"8",A26,1,5
"9",A27,7,2

* Arcs
V2,0,4,0
V0,0,4,0
V4,A0,6,0
V0,0,6,0
V9,A2,4,0
V0,0,4,0
V8,0,7,0
V1,0,7,0
V6,A1,7,0
V2,0,7,0
V5,0,7,0
V3,0,7,0
V8,A10,7,0
V3,A7,7,0
V9,A12,2,0
V3,A5,2,0
V6,A3,4,0
V4,A9,4,0
V7,A16,7,0
V4,0,7,0
V7,A11,4,0
V5,A19,4,0
V9,A20,7,0
V5,A15,7,0
V9,A21,6,0
V7,A23,6,0
V9,A13,7,0
V8,A25,7,0

   假设定义一个指向图结构的指针Graph *g, 则这里的g->util_types的值是ZZZIIZIZIZZZZZ，前六个对应的是Vertex结构中的util型变量，后面两个对应的是Arc结构中的util型变量，最后六个对应的是Graph结构中的util型变量，Z表明忽略此变量的值，用具体的例子来说，"ZZZIIZ"表明Vertex结构的util变量只有x, y有效，共用体取值均为变量I，至于util这个变量究竟有什么用，如果我们只是要使用图的拓扑结构，其实没有必要了解。后面的14V,102A表明图最多有14个顶点，102条边，同样也没有很大的意义。
   再看第二行，"id"字段标示图的生成规则，可以不用管，后面的三个变量10, 28, 10分别说一下，它们分别对应于g->n, g->m,    g->uu.I变量，表示生成的图有10个顶点，28条边，最后的util结构同样不需要理解，说明一下，如果util_types的最后六位是这种形式“SZZZZZ”，则对应变量是g->uu.S, 则最后一个10的值有可能要换成字符。
   下面就是顶点与弧的描述，可以回忆一下数据结构中图的邻接链表存储形式，当前定义的图结构与此非常类似，具体看一下文件中的Vertices表示，假设有Vertex变量v, 则从左到右依次是v->name, v->arcs(文件中是顶点指向的第一条弧), v->x.I, v->y.I, 后面两个变量同样不样管它。再看Arcs结构，我们看定义知道，所有弧结构均是用链表串联起来的，文件中从左到右依次是弧的tip结点，弧所指向的下一条结点（为0表示下一条结点为空），弧长，最后一个字段是arc->a.I，例子中都是0.
    这样说可能仍然难以理解，下面就将示例中的图用简单的图结构表示出来(图比较简略，看图时大家尽量回忆图的邻接链表存储形式，如果我有空再画更清晰的图）以便于理解：
    结点 "0":  A4
     0 ----> 9 ----> 4 ----> 2     A4: 0 ----> 9   A2: 0 ----> 4  A0: 0 ----> 2
    结点 "1":  A6
     1 ----> 8    A6: 1 ----> 8
    结点 "2":  A8
     2 ----> 6 ----> 0        A8: 2 ----> 6  A1: 2 ----> 0
    结点 "3":  A14
     3 ----> 9 ----> 8 ----> 5     A14: 3 ----> 9    A12: 3 ----> 8    A10: 3 ----> 5
    结点 "4":  A18
     4 ----> 7 ----> 6 ----> 0     A18: 4 ----> 7    A16: 4 ----> 6    A3: 4 ----> 0
    结点 "5":  A22
     5 ----> 9 ----> 7 ----> 3     A22: 5 ----> 9    A20: 5 ----> 7    A11: 5 ----> 3
    结点 "6":  A17
     6 ----> 4 ----> 2        A17: 6 ----> 4     A9:  6---->2
    结点 "7":  A24
     7 ----> 9 ----> 5 ----> 4       A24: 7 ----> 9    A21: 7 -----> 5   A19: 7 ----> 4
    结点 "8":  A26
     8 ----> 9 ----> 3 ----> 1      A26: 8 ----> 9   A13: 8 ----> 3    A7: 8 ----> 1
    结点 "9":  A27
     9 ----> 8 ----> 7 ----> 5 ----> 3 ----> 0   A27: 9 ----> 8  A25: 9 ----> 7   A23: 9 ----> 5  A15: 9 ----> 3   A5: 9 ----> 0
   以上内容其实是解释了.gb文件的内容，顺带了解一下standard graphbase的存储结构，其实最简单的得到拓扑的方法是用.alt文件中的内容，看一下以上拓扑图对应的.alt文件内容：
      

GRAPH (#nodes #edges id uu vv ww xx yy zz):
10 28 geo(0,{10,10,3,0.200,0.500,0.500}) 10

VERTICES (index name u v w x y z):
0 0 3 4
1 1 8 6
2 2 7 6
3 3 6 0
4 4 8 1
5 5 0 3
6 6 4 0
7 7 3 6
8 8 1 5
9 9 7 2

EDGES (from-node to-node length a b):
0 9 4 0
0 4 6 0
0 2 4 0
1 8 7 0
2 6 7 0
3 9 2 0
3 8 7 0
3 5 7 0
4 7 7 0
4 6 4 0
5 9 7 0
5 7 4 0
7 9 6 0
8 9 7 0

   这个理解起来可谓是一目了然，由于是无向图，所以EDGES只有14行。
   注意：gt-itm代码只能在i386操作系统上运行, 具体使用方法README文件中说得已经很清楚了。