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 }