commit 001cb7a10b5d360fde70d13c80fa129f6105115d
parent 3bc50e2ea2a8d4fa3d30d74e8c055b65da0ef01c
Author: mjkloeckner <martin.cachari@gmail.com>
Date: Sun, 29 Jan 2023 18:04:31 -0300
added stack data structure to use in depth first search
Diffstat:
| M | main.c | | | 70 | ++++++++++++++++++++++++++++++++++------------------------------------ |
| A | stack.c | | | 44 | ++++++++++++++++++++++++++++++++++++++++++++ |
| A | stack.h | | | 25 | +++++++++++++++++++++++++ |
3 files changed, 103 insertions(+), 36 deletions(-)
diff --git a/main.c b/main.c
@@ -4,6 +4,8 @@
#include <stdlib.h>
#include <stdbool.h>
+#include "stack.h"
+
#define GRAPH_INITIAL_ALLOC 5
#define GRAPH_GROWTH_FACTOR 2
@@ -11,8 +13,8 @@
#define VERTEX_EDGES_GROWTH_FACTOR 1
typedef struct Vertex Vertex;
-typedef void (*Vertex_getter)(Vertex *x, void *data);
-typedef void (*Vertex_setter)(Vertex *x, void *data);
+typedef void (*Vertex_getter)(const Vertex *x, void *data);
+typedef void (*Vertex_setter)(Vertex *x, const void *data);
struct Vertex {
unsigned int edges_no, edges_alloc;
@@ -31,19 +33,20 @@ typedef struct {
/* Functions declaration */
void graph_new(Graph **G);
-void graph_print(Graph *G);
-void graph_print_gv(Graph *G);
-void graph_dfs(Graph *G, Vertex *v);
+void graph_print(const Graph *G);
+void graph_print_gv(const Graph *G);
+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);
void graph_destroy(Graph *G);
-void vertex_new(Vertex **x, Vertex_getter getter, Vertex_setter setter);
+void vertex_new(Vertex **x, const Vertex_getter getter,
+ const Vertex_setter setter);
void vertex_destroy(Vertex *x);
void vertex_add_edge(Vertex *x, Vertex *edge);
void vertex_rm_edge(Vertex *x, Vertex *edge);
-void vertex_get_value(Vertex *x, void *data);
-void vertex_set_value(Vertex *x, void *data);
+void vertex_get_value(const Vertex *x, void *data);
+void vertex_set_value(Vertex *x, const void *data);
void vertex_get_adjacents(Vertex *x);
bool vertex_is_adjacent(Vertex *x, Vertex *y);
@@ -79,7 +82,7 @@ void graph_destroy(Graph *G) {
}
/* TODO: make print functions generic (data type independent) */
-void graph_print(Graph *G) {
+void graph_print(const Graph *G) {
int x;
size_t i, j;
Vertex *v;
@@ -100,7 +103,7 @@ void graph_print(Graph *G) {
puts("}");
}
-void graph_print_gv(Graph *G) {
+void graph_print_gv(const Graph *G) {
int x;
size_t i, j;
Vertex *v;
@@ -129,42 +132,37 @@ void graph_print_gv(Graph *G) {
/* non-recursive Depth-First Search */
/* TODO: implement a stack data structure */
-void graph_dfs(Graph *G, Vertex *v) {
+void graph_dfs(const Graph *G, const Vertex *v) {
/* let S be a stack */
- Vertex **S = calloc(100, sizeof(Vertex *));
- size_t i = 0;
+ /* Vertex **S = calloc(100, sizeof(Vertex *)); */
+ Stack *S;
+ Vertex *aux;
int x;
- /* S.push(v) */
- S[i++] = v;
+ stack_new(&S, sizeof(Vertex *));
+ stack_push(S, &v);
- /* while S is not empty do */
- while(i) {
- /* v = S.pop() */
- S[i] = NULL;
- v = S[--i];
+ while(S->len) {
+ stack_pop(S, &aux);
- /* if v is not labeled as discovered then */
- if (!v->visited) {
- /* label v as discovered */
- v->visited = true;
+ if (!aux->visited) {
+ aux->visited = true;
- vertex_get_value(v, &x);
+ vertex_get_value(aux, &x);
printf("%d -> ", x);
- /* for all edges from v to w in G.adjacentEdges(v) do */
- for(size_t j = 0; j < v->edges_no; j++) {
- /* S.push(w) */
- S[i++] = v->edges[j];
- vertex_get_value(v->edges[j], &x);
- printf("%d%s", x, (j < (v->edges_no - 1)) ? " -> " : "");
+ 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("\n");
}
}
}
-void vertex_new(Vertex **x, Vertex_getter getter, Vertex_setter setter) {
+void vertex_new(Vertex **x, const Vertex_getter getter,
+ const Vertex_setter setter) {
(*x) = malloc(sizeof(Vertex));
(*x)->edges_no = 0;
(*x)->edges_alloc = 0;
@@ -193,20 +191,20 @@ void vertex_add_edge(Vertex *x, Vertex *edge) {
x->edges[x->edges_no++] = edge;
}
-void vertex_get_value(Vertex *x, void *data) {
+void vertex_get_value(const Vertex *x, void *data) {
x->vertex_getter(x, data);
}
-void vertex_set_value(Vertex *x, void *data) {
+void vertex_set_value(Vertex *x, const void *data) {
x->vertex_setter(x, data);
}
/* type specific functions */
-void vertex_getter(Vertex *x, void *data) {
+void vertex_getter(const Vertex *x, void *data) {
*(int *)data = *(int *)x->data;
}
-void vertex_setter(Vertex *x, void *data) {
+void vertex_setter(Vertex *x, const void *data) {
int *i = malloc(sizeof(int));
*i = *(int *)data;
x->data = i;
diff --git a/stack.c b/stack.c
@@ -0,0 +1,44 @@
+/* Stack implementation using a vector to store the elements */
+
+#include "stack.h"
+
+#include <stdio.h>
+#include <string.h>
+
+void stack_new(Stack **S, size_t mem_width) {
+ (*S) = malloc(sizeof(Stack));
+ (*S)->vector = malloc(sizeof(Stack *) * STACK_INITIAL_ALLOC);
+ (*S)->mem_width = mem_width;
+ (*S)->mem_alloc = STACK_INITIAL_ALLOC;
+ (*S)->len = 0;
+}
+
+/* generates a copy of the element an push it into stack
+ * does not check if elem is valid type */
+void stack_push(Stack *S, const void *elem) {
+ if(S->mem_alloc == S->len)
+ S->vector = realloc(S->vector,
+ (S->mem_alloc *= STACK_GROWTH_FACTOR) * sizeof(Stack *));
+
+ S->vector[S->len] = malloc(S->mem_width);
+ memcpy(S->vector[S->len++], elem, S->mem_width);
+}
+
+void stack_peek(const Stack *S, void *data) {
+ data = S->len ? S->vector[S->len - 1] : NULL;
+}
+
+void stack_pop(Stack *S, void *data) {
+ memcpy(data, S->vector[--S->len], S->mem_width);
+ free(S->vector[S->len]);
+}
+
+bool stack_is_empty(const Stack *S) {
+ return S->len;
+}
+
+void stack_destroy(Stack *S) {
+ free(S->vector);
+ free(S);
+}
+
diff --git a/stack.h b/stack.h
@@ -0,0 +1,25 @@
+#ifndef STACK_H_
+#define STACK_H_
+
+#include <stdlib.h>
+#include <stdbool.h>
+
+#define STACK_INITIAL_ALLOC 10
+#define STACK_GROWTH_FACTOR 2
+
+typedef struct Stack Stack;
+
+struct Stack {
+ void **vector;
+ size_t len, mem_alloc, mem_width;
+};
+
+void stack_new(Stack **S, size_t mem_width);
+void stack_push(Stack *S, const void *elem);
+void stack_peek(const Stack *S, void *data);
+void stack_pop(Stack *S, void *data);
+void stack_destroy(Stack *S);
+bool stack_is_empty(const Stack *S);
+
+
+#endif
