Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3235761
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8557
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: LINUX

2013-03-01 22:24:18

    任何一本讲到图算法的算法书,都会讲到图的表示方法有两种

    1 邻接矩阵 ,对于N个点的图,需要N×N的矩阵表示点与点之间是否有边的存在。这种表示法的缺点是浪费空间,尤其是对于N×N的矩阵是稀疏矩阵,即边的数目远远小于N×N的时候,浪费了巨大的存储空间。

                                                

    2 邻接链表,对于任何一个node A,外挂一个邻接链表,如果存在 A->X这样的边,就将X链入链表。 这种表示方法的优点是节省空间,缺点是所有链表都存在的缺点,地址空间的不连续造成缓存命中降低,性能有不如临界矩阵这样的数组。

                                  

    一直以来,我也是觉得,鱼和熊掌不可兼得,这是无可奈何的事情。直到我看到了一份比较完美的code。他有动态分配的数组来存放邻接节点。一起欣赏下这份代码吧。年前我第一次看到这份代码的时候,激动的我晚上半天睡不着觉。平时自己写的代码,一板一眼,虽说功能无误,总少了那么几分灵气。看了C算法,也算对图的表示方法知道一些,却写不出这么优美的代码:

    我以前觉得,自己大量练习联系写代码是学习编程的最好的方法,是最开但是看了这份代码后,觉得,学习前辈高人优秀的代码,是提高自己的一条捷径,对我们这些普通的coder而言,我们看代码的时间是超过写代码的时间的。阅读前辈优秀代码,会更快的提升自己的编程能力。对于初学者尤其是这样,这也是进入一个优秀的开发team的重要性,能更快的成长。

    欣赏代码Yale大学前辈的代码吧。

  1. #ifndef __GRAPH_H__
  2. #define __GRAPH_H__

  3. typedef struct graph *Graph;

  4. Graph graph_create(int n);
  5. void graph_destroy(Graph);
  6. void graph_add_edge(Graph, int source, int sink);
  7. int graph_vertex_count(Graph);
  8. int graph_edge_count(Graph);
  9. int graph_out_degree(Graph, int source);
  10. int graph_has_edge(Graph, int source, int sink);
  11. void graph_foreach(Graph g, int source,
  12.         void (*f)(Graph g, int source, int sink, void *data),
  13.         void *data);

  14. #endif
  1. #include <stdlib.h>
  2. #include <assert.h>

  3. #include "graph.h"

  4. /* basic directed graph type */
  5. /* the implementation uses adjacency lists
  6.  * represented as variable-length arrays */

  7. /* these arrays may or may not be sorted: if one gets long enough
  8.  * and you call graph_has_edge on its source, it will be */

  9. struct graph {
  10.     int n;                                             /* number of vertices */
  11.     int m;                                             /* number of edges */
  12.     struct successors {
  13.         int d;                                         /* number of successors */
  14.         int len;                                       /* number of slots in array */
  15.         char is_sorted;                                /* true if list is already sorted */
  16.         int list[1];                                  
                                                           /* actual list of successors */
  17.     } *alist[1];
  18. };

  19. /* create a new graph with n vertices labeled 0..n-1 and no edges */
  20. Graph
  21. graph_create(int n)
  22. {
  23.     Graph g;
  24.     int i;

  25.     g = malloc(sizeof(struct graph) + sizeof(struct successors *) * (n-1));
  26.     assert(g);

  27.     g->n = n;
  28.     g->m = 0;

  29.     for(i = 0; i < n; i++) {
  30.         g->alist[i] = malloc(sizeof(struct successors));
  31.         assert(g->alist[i]);

  32.         g->alist[i]->d = 0;
  33.         g->alist[i]->len = 1;
  34.         g->alist[i]->is_sorted= 1;
  35.     }
  36.     
  37.     return g;
  38. }

  39. /* free all space used by graph */
  40. void
  41. graph_destroy(Graph g)
  42. {
  43.     int i;

  44.     for(i = 0; i < g->n; i++) free(g->alist[i]);
  45.     free(g);
  46. }

  47. /* add an edge to an existing graph */
  48. void
  49. graph_add_edge(Graph g, int u, int v)
  50. {
  51.     assert(u >= 0);
  52.     assert(u < g->n);
  53.     assert(v >= 0);
  54.     assert(v < g->n);

  55.     /* do we need to grow the list? */
  56.     while(g->alist[u]->d >= g->alist[u]->len) {
  57.         g->alist[u]->len *= 2;
  58.         g->alist[u] =
  59.             realloc(g->alist[u],
  60.                 sizeof(struct successors) + sizeof(int) * (g->alist[u]->len - 1));
  61.     }

  62.     /* now add the new sink */
  63.     g->alist[u]->list[g->alist[u]->d++] = v;
  64.     g->alist[u]->is_sorted = 0;

  65.     /* bump edge count */
  66.     g->m++;
  67. }

  68. /* return the number of vertices in the graph */
  69. int
  70. graph_vertex_count(Graph g)
  71. {
  72.     return g->n;
  73. }

  74. /* return the number of vertices in the graph */
  75. int
  76. graph_edge_count(Graph g)
  77. {
  78.     return g->m;
  79. }

  80. /* return the out-degree of a vertex */
  81. int
  82. graph_out_degree(Graph g, int source)
  83. {
  84.     assert(source >= 0);
  85.     assert(source < g->n);

  86.     return g->alist[source]->d;
  87. }

  88. /* when we are willing to call bsearch */
  89. #define BSEARCH_THRESHOLD (10)

  90. static int
  91. intcmp(const void *a, const void *b)
  92. {
  93.     return *((const int *) a) - *((const int *) b);
  94. }

  95. /* return 1 if edge (source, sink) exists), 0 otherwise */
  96. int
  97. graph_has_edge(Graph g, int source, int sink)
  98. {
  99.     int i;

  100.     assert(source >= 0);
  101.     assert(source < g->n);
  102.     assert(sink >= 0);
  103.     assert(sink < g->n);

  104.     if(graph_out_degree(g, source) >= BSEARCH_THRESHOLD) {
  105.         /* make sure it is sorted */
  106.         if(! g->alist[source]->is_sorted) {
  107.             qsort(g->alist[source]->list,
  108.                     g->alist[source]->d,
  109.                     sizeof(int),
  110.                     intcmp);
  111.         }
  112.         
  113.         /* call bsearch to do binary search for us */
  114.         return
  115.             bsearch(&sink,
  116.                     g->alist[source]->list,
  117.                     g->alist[source]->d,
  118.                     sizeof(int),
  119.                     intcmp)
  120.             != 0;
  121.     } else {
  122.         /* just do a simple linear search */
  123.         /* we could call lfind for this, but why bother? */
  124.         for(i = 0; i < g->alist[source]->d; i++) {
  125.             if(g->alist[source]->list[i] == sink) return 1;
  126.         }
  127.         /* else */
  128.         return 0;
  129.     }
  130. }

  131. /* invoke f on all edges (u,v) with source u */
  132. /* supplying data as final parameter to f */
  133. void
  134. graph_foreach(Graph g, int source,
  135.     void (*f)(Graph g, int source, int sink, void *data),
  136.     void *data)
  137. {
  138.     int i;

  139.     assert(source >= 0);
  140.     assert(source < g->n);

  141.     for(i = 0; i < g->alist[source]->d; i++) {
  142.         f(g, source, g->alist[source]->list[i], data);
  143.     }
  144. }

    这是一份PineWiki网站里面提供的一份图的表示的代码,实现的很优美吧?动态分配数组,长度可以扩展,既不浪费空间,有不会带来性能损失。

    除此外,graph_foreach这种思想也很不错啊。最近学习了一段时间的Lisp,这种传递函数作用到每一个元素上的方法,相当于Lisp中的mapcar,让人不仅拍案叫绝,很容易就能扩展出很好的功能。(当然也不是完全没瑕疵,比如realloc没有判断失败的情景,白璧微瑕)
    既然是图的表示,我们当然很希望能够看到可视化的图。我看Land of Lisp一书中,学到了Linux下的neato 命令。 Linux下有工具帮助生成图的图片,可以满足我们可视化的需求。

    先看下测试代码。

  1. #include <stdio.h>
  2. #include <assert.h>

  3. #include "graph.h"

  4. #define TEST_SIZE (6)

  5.  static void
  6. match_sink(Graph g, int source, int sink, void *data)
  7. {
  8.     assert(data && sink == *((int *) data));
  9. }

  10. static int node2dot(Graph g)
  11. {
  12.     assert(g != NULL);
  13.     return 0;
  14. }

  15. static void print_edge2dot(Graph g,int source, int sink, void *data)
  16. {
  17.     fprintf(stdout,"%d->%d;n",source,sink);
  18. }
  19. static int edge2dot(Graph g)
  20. {
  21.     assert( NULL);
  22.     int idx = 0;
  23.     int node_cnt = graph_vertex_count(g);
  24.     for(idx = 0;idx<node_cnt; idx++)
  25.     {
  26.         graph_foreach(g,idx,print_edge2dot,NULL);
  27.     }
  28.     return 0;
  29. }

  30. int graph2dot(Graph g)
  31. {
  32.     fprintf(stdout,"digraph{");
  33.     node2dot(g);
  34.     edge2dot(g);
  35.     fprintf(stdout,"}n");
  36.     return 0;
  37. }

  38. int main(int argc, char **argv)
  39. {
  40.     Graph g;
  41.     int i;
  42.     int j;

  43.     g = graph_create(TEST_SIZE);

  44.     assert(graph_vertex_count(g) == TEST_SIZE);

  45.     /* check it's empty */
  46.     for(i = 0; i < TEST_SIZE; i++) {
  47.         for(j = 0; j < TEST_SIZE; j++) {
  48.             assert(graph_has_edge(g, i, j) == 0);
  49.         }
  50.     }

  51.     /* check it's empty again */
  52.     for(i = 0; i < TEST_SIZE; i++) {
  53.         assert(graph_out_degree(g, i) == 0);
  54.         graph_foreach(g, i, match_sink, 0);
  55.     }

  56.     /* check edge count */
  57.     assert(graph_edge_count(g) == 0);

  58.     for(i = 0; i < TEST_SIZE; i++) {
  59.         for(j = 0; j < TEST_SIZE; j++) {
  60.             if(i < j) graph_add_edge(g, i, j);
  61.         }
  62.     }


  63.     for(i = 0; i < TEST_SIZE; i++) {
  64.         for(j = 0; j < TEST_SIZE; j++) {
  65.             assert(graph_has_edge(g, i, j) == (i < j));
  66.         }
  67.     }

     assert(graph_edge_count(g) == (TEST_SIZE*(TEST_SIZE-1)/2));

  1.     graph2dot(g);
  2.     /* free it
  3.      * */
  4.     graph_destroy(g);

  5.     return 0;
  6. }

    我们这个测试程序基本测试了graph的API,同时利用graph_foreach函数的高效扩展性,输出了dot文件格式的文件我们看下执行结果。

  1. root@manu:~/code/c/self/graph_2# gcc -o test generate_graph.c graph.c
  2. root@manu:~/code/c/self/graph_2# ./test >test.dot
    在我的Ubuntu下面用XDot可以看到test.dot已经是个图形文件了。图形如下:


    当然了,我们也可以用 dot命令绘制出PNG格式的图片来:

  1. root@manu:~/code/c/self/graph_2# dot -T png -o graph_test.png test.dot
    我们可以看到在当前目录下产生了一个文件名为graph_test.png的PNG格式的图片。打开看下和上面的图是一致的。我就不贴图了。

    对dot感兴趣的筒子,可以继续阅读『dot 学习笔记』二. 记录 Shell 的变迁


参考文献:

1  Land of Lisp

2 PineWiki

3 算法:C语言实现。

阅读(15357) | 评论(1) | 转发(4) |
给主人留下些什么吧!~~

Debroon2020-03-11 16:30:07

Linux下有工具帮助生成图的图片,大佬,这个工具是啥?generate_graph.c这个文件电脑里没有。