graph.c (1734B)
1 #include "graph.h" 2 3 void graph_bfs_init(graph_bfs_t *bfs, graph_t *g, const uint64_t v) { 4 bfs->queued = calloc(g->n, sizeof(*(bfs->queued))); 5 // struct bfs_listhead head = SIMPLEQ_HEAD_INITIALIZER(head); 6 bfs->queue = (struct bfs_listhead) SIMPLEQ_HEAD_INITIALIZER(bfs->queue); 7 8 bfs_list_entry_t *vx = malloc(sizeof(*vx)); 9 vx->x = v; 10 SIMPLEQ_INSERT_HEAD(&(bfs->queue), vx, entries); 11 bfs->queued[v] = 1; 12 } 13 14 void graph_bfs_clear(graph_bfs_t *bfs) { 15 bfs_list_entry_t *t; 16 free(bfs->queued); 17 18 // clear the remaining elements of queue 19 while (!SIMPLEQ_EMPTY(&(bfs->queue))) { 20 t = SIMPLEQ_FIRST(&(bfs->queue)); 21 SIMPLEQ_REMOVE_HEAD(&(bfs->queue), entries); 22 free(t); 23 } 24 } 25 26 #include <stdio.h> 27 28 uint64_t graph_bfs_next(graph_bfs_t *bfs, const graph_t *g) { 29 if (SIMPLEQ_EMPTY(&(bfs->queue))) 30 return UINT64_MAX; 31 32 uint64_t w; 33 34 bfs_list_entry_t *t; 35 bfs_list_entry_t *head = SIMPLEQ_FIRST(&(bfs->queue)); 36 SIMPLEQ_REMOVE_HEAD(&(bfs->queue), entries); 37 uint64_t res = head->x; 38 39 size_t i; 40 for(i = 0; i < (g->nbrs[res]).nmemb; i++) { 41 w = (g->nbrs[res]).data[i]; 42 if(bfs->queued[w] == 0) { 43 t = malloc(sizeof(*t)); 44 t->x = w; 45 SIMPLEQ_INSERT_TAIL(&(bfs->queue), t, entries); 46 bfs->queued[w] = 1; 47 } 48 } 49 50 free(head); 51 return res; 52 } 53 54 void graph_init(graph_t *g, const size_t n) { 55 g->n = n; 56 g->nbrs = malloc(n * sizeof(*(g->nbrs))); 57 58 size_t i; 59 for (i = 0; i < n; i++) 60 stack_u64_init(&g->nbrs[i]); 61 } 62 63 void graph_clear(graph_t *g) { 64 size_t i; 65 for (i = 0; i < g->n; i++) 66 stack_u64_clear(&g->nbrs[i]); 67 free(g->nbrs); 68 } 69 70 void graph_add_edge(graph_t *g, const size_t v, const size_t w) { 71 stack_u64_push(&g->nbrs[v], w); 72 stack_u64_push(&g->nbrs[w], v); 73 }