main.c - graph - unidirected graph implementation using adjacency list

main.c (6892B)
Line numbers
   1 /* Graph implementation in C with adjacency list */
   2 
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <stdbool.h>
   6 
   7 #include "stack.h"
   8 #include "queue.h"
   9 
  10 #define GRAPH_INITIAL_ALLOC 5
  11 #define GRAPH_GROWTH_FACTOR 2
  12 
  13 #define VERTEX_EDGES_INITIAL_SIZE 1
  14 #define VERTEX_EDGES_GROWTH_FACTOR 1
  15 
  16 typedef struct Vertex Vertex;
  17 typedef void (*Vertex_getter)(const Vertex *x, void *data);
  18 typedef void (*Vertex_setter)(Vertex *x, const void *data);
  19 
  20 struct Vertex {
  21     unsigned int edges_no, edges_alloc;
  22     void *data;
  23     bool visited;
  24     Vertex_getter vertex_getter;
  25     Vertex_setter vertex_setter;
  26     Vertex **edges;
  27 };
  28 
  29 typedef struct {
  30     Vertex **vertices;
  31     unsigned int vertices_no, vertices_alloc;
  32 } Graph;
  33 
  34 
  35 /* Functions declaration */
  36 void graph_new(Graph **G);
  37 void graph_print(const Graph *G);
  38 void graph_print_gv(const Graph *G);
  39 void graph_bfs(const Graph *G, const Vertex *v);
  40 void graph_dfs(const Graph *G, const Vertex *v);
  41 void graph_add_vertex(Graph *G, Vertex *v);
  42 void graph_rm_vertex(Graph *G, Vertex *v);
  43 void graph_destroy(Graph *G);
  44 
  45 void vertex_new(Vertex **x, const Vertex_getter getter,
  46         const Vertex_setter setter);
  47 void vertex_destroy(Vertex *x);
  48 void vertex_add_edge(Vertex *x, Vertex *edge);
  49 void vertex_rm_edge(Vertex *x, Vertex *edge);
  50 void vertex_get_value(const Vertex *x, void *data);
  51 void vertex_set_value(Vertex *x, const void *data);
  52 void vertex_get_adjacents(Vertex *x);
  53 bool vertex_is_adjacent(Vertex *x, Vertex *y);
  54 
  55 
  56 /* Functions definition */
  57 void graph_new(Graph **G) {
  58     (*G) = malloc(sizeof(Graph));
  59     (*G)->vertices_no = 0;
  60     (*G)->vertices = NULL;
  61 }
  62 
  63 void graph_add_vertex(Graph *G, Vertex *v) {
  64     /* add memory if needed */
  65     if (G->vertices == NULL) {
  66         G->vertices_alloc = GRAPH_INITIAL_ALLOC;
  67         G->vertices = malloc(sizeof(Vertex *) * GRAPH_INITIAL_ALLOC);
  68     }
  69     else if (G->vertices_alloc == G->vertices_no) {
  70         G->vertices_alloc = G->vertices_alloc * GRAPH_GROWTH_FACTOR;
  71         G->vertices = realloc(G->vertices,
  72                 sizeof(Vertex *) * G->vertices_alloc);
  73     }
  74 
  75     G->vertices[G->vertices_no++] = v;
  76 }
  77 
  78 void graph_destroy(Graph *G) {
  79     for(size_t i = 0; i < G->vertices_no; i++)
  80         vertex_destroy(G->vertices[i]);
  81 
  82     free(G->vertices);
  83     free(G);
  84 }
  85 
  86 /* TODO: make print functions generic (data type independent) */
  87 void graph_print(const Graph *G) {
  88     int x;
  89     size_t i, j;
  90     Vertex *v;
  91 
  92     puts("strict graph G {");
  93 
  94     for(i = 0; i < G->vertices_no; i++) {
  95         v = G->vertices[i];
  96         vertex_get_value(v, &x);
  97         printf("    %d%s", x, v->edges_no ? " -- " : "\n");
  98 
  99         for(j = 0, printf("{"); j < v->edges_no; j++) {
 100             vertex_get_value(v->edges[j], &x);
 101             printf("%d%s", x, (j < (v->edges_no - 1)) ? ", " : "}");
 102         }
 103         printf("\n");
 104     }
 105     puts("}");
 106 }
 107 
 108 void graph_print_gv(const Graph *G) {
 109     int x;
 110     size_t i, j;
 111     Vertex *v;
 112 
 113     puts("strict graph G {\n"
 114         "    rankdir=RL;\n"
 115         "    node [ shape=circle,\n"
 116             "            penwidth=2.0, \n"
 117             "            fontname=\"DejaVu Sans Mono\", \n"
 118             "            fontsize=20.0 ]\n"
 119         "    edge [ penwidth=2.0 ]\n");
 120 
 121     for(i = 0; i < G->vertices_no; i++) {
 122         v = G->vertices[i];
 123         vertex_get_value(v, &x);
 124         printf("    %d%s", x, v->edges_no ? " -- " : "\n");
 125 
 126         for(j = 0, printf("{"); j < v->edges_no; j++) {
 127             vertex_get_value(v->edges[j], &x);
 128             printf("%d%s", x, (j < (v->edges_no - 1)) ? ", " : "}");
 129         }
 130         printf("\n");
 131     }
 132     puts("}");
 133 }
 134 
 135 /* non-recursive Depth-First Search */
 136 void graph_dfs(const Graph *G, const Vertex *v) {
 137     Stack *S;
 138     Vertex *aux;
 139     int x;
 140 
 141     stack_new(&S, sizeof(Vertex *));
 142     stack_push(S, &v);
 143 
 144     puts("strict digraph G {");
 145     while(S->len) {
 146         stack_pop(S, &aux);
 147 
 148         if (!aux->visited) {
 149             aux->visited = true;
 150             vertex_get_value(aux, &x);
 151             printf("    %d -> {", x);
 152 
 153             for(size_t j = 0; j < aux->edges_no; j++) {
 154                 stack_push(S, &(aux->edges[j]));
 155                 vertex_get_value(aux->edges[j], &x);
 156                 printf("%d%s", x, (j < (aux->edges_no - 1)) ? "," : "}");
 157             }
 158             printf("\n");
 159         }
 160     }
 161     puts("}");
 162 }
 163 
 164 /* non-recursive Breadth-First Search */
 165 void graph_bfs(const Graph *G, const Vertex *v) {
 166     Queue *Q;
 167     Vertex *aux;
 168     int x;
 169 
 170     queue_new(&Q, sizeof(Vertex *));
 171     queue_enqueue(Q, &v);
 172 
 173     puts("strict digraph G {");
 174     while(queue_is_empty(Q)) {
 175         queue_dequeue(Q, &aux);
 176         if(!aux->visited) {
 177             aux->visited = true;
 178             vertex_get_value(aux, &x);
 179             printf("    %d -> {", x);
 180             for(size_t j = 0; j < aux->edges_no; j++) {
 181                 vertex_get_value(aux->edges[j], &x);
 182                 printf("%d%s", x, (j < (aux->edges_no - 1)) ? "," : "}");
 183                 if(!aux->edges[j]->visited)
 184                     queue_enqueue(Q, &(aux->edges[j]));
 185             }
 186             printf("\n");
 187         }
 188     }
 189     puts("}");
 190 }
 191 
 192 void vertex_new(Vertex **x, const Vertex_getter getter,
 193         const Vertex_setter setter) {
 194     (*x) = malloc(sizeof(Vertex));
 195     (*x)->edges_no = 0;
 196     (*x)->edges_alloc = 0;
 197     (*x)->visited = false;
 198     (*x)->vertex_getter = getter;
 199     (*x)->vertex_setter = setter;
 200     (*x)->data = NULL;
 201     (*x)->edges = NULL;
 202 }
 203 
 204 /* does not destroy adjacent vertices nor edges */
 205 void vertex_destroy(Vertex *x) {
 206     free(x->data);
 207     free(x->edges);
 208     free(x);
 209 }
 210 
 211 void vertex_add_edge(Vertex *x, Vertex *edge) {
 212     if (x->edges == NULL)
 213         x->edges = malloc(sizeof(Vertex) * VERTEX_EDGES_INITIAL_SIZE);
 214 
 215     else if (x->edges_no == x->edges_alloc)
 216         x->edges = realloc(x->edges,
 217                 (x->edges_alloc *= VERTEX_EDGES_GROWTH_FACTOR));
 218 
 219     x->edges[x->edges_no++] = edge;
 220 }
 221 
 222 void vertex_get_value(const Vertex *x, void *data) {
 223     x->vertex_getter(x, data);
 224 }
 225 
 226 void vertex_set_value(Vertex *x, const void *data) {
 227     x->vertex_setter(x, data);
 228 }
 229 
 230 /* type specific functions */
 231 void vertex_getter(const Vertex *x, void *data) {
 232     *(int *)data = *(int *)x->data;
 233 }
 234 
 235 void vertex_setter(Vertex *x, const void *data) {
 236     int *i = malloc(sizeof(int));
 237     *i = *(int *)data;
 238     x->data = i;
 239 }
 240 
 241 
 242 int main (void) {
 243     Graph *graph;
 244     Vertex *v;
 245 
 246     graph_new(&graph);
 247 
 248     int x;
 249     size_t i;
 250 
 251     for(i = 0, x = 1; i < 6; i++, x++) {
 252         vertex_new(&v, vertex_getter, vertex_setter);
 253         graph_add_vertex(graph, v);
 254         vertex_set_value(graph->vertices[i], &x);
 255     }
 256 
 257     vertex_add_edge(graph->vertices[0], graph->vertices[1]);
 258     vertex_add_edge(graph->vertices[0], graph->vertices[4]);
 259 
 260     vertex_add_edge(graph->vertices[1], graph->vertices[0]);
 261     vertex_add_edge(graph->vertices[1], graph->vertices[2]);
 262     vertex_add_edge(graph->vertices[1], graph->vertices[4]);
 263 
 264     vertex_add_edge(graph->vertices[4], graph->vertices[0]);
 265     vertex_add_edge(graph->vertices[4], graph->vertices[1]);
 266     vertex_add_edge(graph->vertices[4], graph->vertices[3]);
 267 
 268     vertex_add_edge(graph->vertices[2], graph->vertices[1]);
 269     vertex_add_edge(graph->vertices[2], graph->vertices[3]);
 270 
 271     vertex_add_edge(graph->vertices[3], graph->vertices[2]);
 272     vertex_add_edge(graph->vertices[3], graph->vertices[4]);
 273     vertex_add_edge(graph->vertices[3], graph->vertices[5]);
 274 
 275     vertex_add_edge(graph->vertices[5], graph->vertices[3]);
 276 
 277     /* graph_bfs(graph, graph->vertices[0]); */
 278     /* graph_dfs(graph, graph->vertices[0]); */
 279     /* graph_print_gv(graph); */
 280 
 281     graph_destroy(graph);
 282     return 0;
 283 }