commit 70840ab67036bfd6007dcfb41269131053752dc9
parent b99e54745f24a3eca97315343094b97d56545ee2
Author: mjkloeckner <martin.cachari@gmail.com>
Date: Tue, 31 Jan 2023 22:19:29 -0300
added queue module for breath first search
Diffstat:
| M | main.c | | | 43 | +++++++++++++++++++++++++++++++++++++++---- |
| A | queue.c | | | 64 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | queue.h | | | 29 | +++++++++++++++++++++++++++++ |
3 files changed, 132 insertions(+), 4 deletions(-)
diff --git a/main.c b/main.c
@@ -5,6 +5,7 @@
#include <stdbool.h>
#include "stack.h"
+#include "queue.h"
#define GRAPH_INITIAL_ALLOC 5
#define GRAPH_GROWTH_FACTOR 2
@@ -35,6 +36,7 @@ typedef struct {
void graph_new(Graph **G);
void graph_print(const Graph *G);
void graph_print_gv(const Graph *G);
+void graph_bfs(const Graph *G, const Vertex *v);
void graph_dfs(const Graph *G, const Vertex *v);
void graph_add_vertex(Graph *G, Vertex *v);
void graph_rm_vertex(Graph *G, Vertex *v);
@@ -139,22 +141,52 @@ void graph_dfs(const Graph *G, const Vertex *v) {
stack_new(&S, sizeof(Vertex *));
stack_push(S, &v);
+ puts("strict digraph G {");
while(S->len) {
stack_pop(S, &aux);
if (!aux->visited) {
aux->visited = true;
vertex_get_value(aux, &x);
- printf("%d -> ", x);
+ printf(" %d -> {", x);
for(size_t j = 0; j < aux->edges_no; j++) {
stack_push(S, &(aux->edges[j]));
vertex_get_value(aux->edges[j], &x);
- printf("%d%s", x, (j < (aux->edges_no - 1)) ? " -> " : "");
+ printf("%d%s", x, (j < (aux->edges_no - 1)) ? "," : "}");
}
printf("\n");
}
}
+ puts("}");
+}
+
+/* non-recursive Breadth-First Search */
+void graph_bfs(const Graph *G, const Vertex *v) {
+ Queue *Q;
+ Vertex *aux;
+ int x;
+
+ queue_new(&Q, sizeof(Vertex *));
+ queue_enqueue(Q, &v);
+
+ puts("strict digraph G {");
+ while(queue_is_empty(Q)) {
+ queue_dequeue(Q, &aux);
+ if(!aux->visited) {
+ aux->visited = true;
+ vertex_get_value(aux, &x);
+ printf(" %d -> {", x);
+ for(size_t j = 0; j < aux->edges_no; j++) {
+ vertex_get_value(aux->edges[j], &x);
+ printf("%d%s", x, (j < (aux->edges_no - 1)) ? "," : "}");
+ if(!aux->edges[j]->visited)
+ queue_enqueue(Q, &(aux->edges[j]));
+ }
+ printf("\n");
+ }
+ }
+ puts("}");
}
void vertex_new(Vertex **x, const Vertex_getter getter,
@@ -182,7 +214,7 @@ void vertex_add_edge(Vertex *x, Vertex *edge) {
else if (x->edges_no == x->edges_alloc)
x->edges = realloc(x->edges,
- x->edges_alloc + (1 * VERTEX_EDGES_GROWTH_FACTOR));
+ (x->edges_alloc *= VERTEX_EDGES_GROWTH_FACTOR));
x->edges[x->edges_no++] = edge;
}
@@ -242,7 +274,10 @@ int main (void) {
vertex_add_edge(graph->vertices[5], graph->vertices[3]);
- graph_dfs(graph, graph->vertices[0]);
+ /* graph_bfs(graph, graph->vertices[0]); */
+ /* graph_dfs(graph, graph->vertices[0]); */
+ /* graph_print_gv(graph); */
+
graph_destroy(graph);
return 0;
}
diff --git a/queue.c b/queue.c
@@ -0,0 +1,64 @@
+#include "queue.h"
+
+/* FIFO: First In First Out */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+void queue_new(Queue **Q, size_t type_size) {
+ (*Q) = malloc(sizeof(Queue));
+ (*Q)->first = NULL;
+ (*Q)->end = NULL;
+ (*Q)->type_size = type_size;
+}
+
+void queue_enqueue(Queue *Q, void *data) {
+ Node *new = malloc(sizeof(Node));
+ new->data = malloc(Q->type_size);
+ memcpy(new->data, data, Q->type_size);
+
+ if(!Q->first) Q->first = new;
+
+ if(!Q->end) Q->end = new;
+ else Q->end->next = new;
+
+ new->prev = Q->end;
+ new->next = NULL;
+ Q->end = new;
+}
+
+void queue_dequeue(Queue *Q, void *data) {
+ assert(Q->first);
+ assert(Q->end);
+
+ memcpy(data, Q->first->data, Q->type_size);
+
+ Q->first->prev = Q->first;
+ Q->first = Q->first->next;
+ if(Q->first == NULL) return;
+
+ free(Q->first->prev->data);
+ free(Q->first->prev);
+ Q->first->prev = NULL;
+}
+
+bool queue_is_empty(Queue *Q) {
+ return Q->first;
+}
+
+void queue_destroy(Queue *Q) {
+ for(Node *n = Q->first; n; n = n->next)
+ free(n->prev);
+
+ if(Q->end)
+ free(Q->end->data);
+
+ free(Q->end);
+ if(Q->first)
+ free(Q->first->data);
+
+ free(Q->first);
+ free(Q);
+}
diff --git a/queue.h b/queue.h
@@ -0,0 +1,29 @@
+#ifndef QUEUE_H_
+#define QUEUE_H_
+
+#include <stddef.h>
+#include <stdbool.h>
+
+typedef struct Node Node;
+typedef struct Queue Queue;
+
+struct Node {
+ void *data;
+ Node *next;
+ Node *prev;
+};
+
+struct Queue {
+ size_t type_size;
+ Node *first;
+ Node *end;
+};
+
+void queue_new(Queue **Q, size_t type_size);
+void queue_enqueue(Queue *Q, void *data);
+void queue_dequeue(Queue *Q, void *data);
+void queue_destroy(Queue *Q);
+
+bool queue_is_empty(Queue *Q);
+
+#endif
