commit b5b0f79be0801c80da6cf96fa48cc0bbc6c3c7af
parent fdf4491339a8d71d8d7666d850483918bb8dc776
Author: olikru <olikru@tkruger.se>
Date: Fri, 12 Jan 2024 13:47:26 +0100
added unit tests and bfs
Diffstat:
| M | graph.c | | | 51 | +++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | graph.h | | | 85 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | test_graph.c | | | 71 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- |
3 files changed, 205 insertions(+), 2 deletions(-)
diff --git a/graph.c b/graph.c
@@ -1,5 +1,56 @@
#include "graph.h"
+void graph_bfs_init(graph_bfs_t *bfs, graph_t *g, const uint64_t v) {
+ bfs->queued = calloc(g->n, sizeof(*(bfs->queued)));
+// struct bfs_listhead head = SIMPLEQ_HEAD_INITIALIZER(head);
+ bfs->queue = (struct bfs_listhead) SIMPLEQ_HEAD_INITIALIZER(bfs->queue);
+
+ bfs_list_entry_t *vx = malloc(sizeof(*vx));
+ vx->x = v;
+ SIMPLEQ_INSERT_HEAD(&(bfs->queue), vx, entries);
+ bfs->queued[v] = 1;
+}
+
+void graph_bfs_clear(graph_bfs_t *bfs) {
+ bfs_list_entry_t *t;
+ free(bfs->queued);
+
+ // clear the remaining elements of queue
+ while (!SIMPLEQ_EMPTY(&(bfs->queue))) {
+ t = SIMPLEQ_FIRST(&(bfs->queue));
+ SIMPLEQ_REMOVE_HEAD(&(bfs->queue), entries);
+ free(t);
+ }
+}
+
+#include <stdio.h>
+
+uint64_t graph_bfs_next(graph_bfs_t *bfs, const graph_t *g) {
+ if (SIMPLEQ_EMPTY(&(bfs->queue)))
+ return UINT64_MAX;
+
+ uint64_t w;
+
+ bfs_list_entry_t *t;
+ bfs_list_entry_t *head = SIMPLEQ_FIRST(&(bfs->queue));
+ SIMPLEQ_REMOVE_HEAD(&(bfs->queue), entries);
+ uint64_t res = head->x;
+
+ size_t i;
+ for(i = 0; i < (g->nbrs[res]).nmemb; i++) {
+ w = (g->nbrs[res]).data[i];
+ if(bfs->queued[w] == 0) {
+ t = malloc(sizeof(*t));
+ t->x = w;
+ SIMPLEQ_INSERT_TAIL(&(bfs->queue), t, entries);
+ bfs->queued[w] = 1;
+ }
+ }
+
+ free(head);
+ return res;
+}
+
void graph_init(graph_t *g, const size_t n) {
g->n = n;
g->nbrs = malloc(n * sizeof(*(g->nbrs)));
diff --git a/graph.h b/graph.h
@@ -1,6 +1,7 @@
#ifndef GRAPH_H
#define GRAPH_H
+#include <sys/queue.h>
#include "stack_u64.h"
typedef struct {
@@ -8,8 +9,92 @@ typedef struct {
stack_u64_t *nbrs;
} graph_t;
+typedef SIMPLEQ_HEAD(bfs_listhead, bfs_list_entry) bfs_queue_head_t;
+
+typedef struct bfs_list_entry {
+ size_t x;
+ SIMPLEQ_ENTRY(bfs_list_entry) entries;
+} bfs_list_entry_t;
+
+typedef struct {
+ uint8_t *queued;
+ bfs_queue_head_t queue;
+} graph_bfs_t;
+
+/**
+ * Intialises a BFS struct
+ *
+ * Initialises a BFS struct which can be used for traversing the
+ * graph in BFS order, starting from the vertex v. This function
+ * allocates memory that needs to be cleared and freed.
+ *
+ * @param bfs pointer to the bfs struct that stores the state
+ * @param g the graph to preform BFS on
+ * @param v the vertex to start at
+ */
+void graph_bfs_init(graph_bfs_t *bfs, graph_t *g, const uint64_t v);
+
+/**
+ * Clears a BFS struct
+ *
+ * @param bfs pointer to the BFS struct to clear
+ */
+void graph_bfs_clear(graph_bfs_t *bfs);
+
+/**
+ * Get the next element in BFS search
+ *
+ * Function for getting the next vertex from a graph ordered by some BFS
+ * order, represented by an graph_bfs_t. This removes an element from
+ * the stored queue, and returns it (and updates the queue as needed).
+ * If there are no more vertices to visit this function returns
+ * UINT64_MAX. Note that the BFS struct is not cleared by this function,
+ * so this has to be done manually.
+ *
+ * @param bfs
+ * a bfs search struct representing the current state of a bfs search
+ * @param g
+ * the graph to traverse
+ */
+uint64_t graph_bfs_next(graph_bfs_t *bfs, const graph_t *g);
+
+/**
+ * Initialise a new graph
+ *
+ * Initialises a new graph on n vertices. The vertex set will be [n],
+ * and the graph is initialised without any edges. The graph is
+ * represented in terms of neighbour lists. Graph is always considered
+ * to be undirected, but multiple edges and loops are allowed (i.e. more
+ * properly it is a multigraph).
+ *
+ * @param g pointer to the graph to inialise
+ * @param n the size (number of vertices) of the graph to initialise
+ */
void graph_init(graph_t *g, const size_t n);
+
+/**
+ * Clear a graph
+ *
+ * This assumes that g points to a graph that has been initialized.
+ *
+ * @param g pointer to the graph to clear
+ */
void graph_clear(graph_t *g);
+
+/**
+ * Add an edge to a graph
+ *
+ * This function adds an edge between vertices v and w in the graph g.
+ * The vertex v is added to the neighbour list of w and the vertex w is
+ * added to the neighbour list of v. This function can be called
+ * multiple times with the same arguments to add multiple edges between
+ * the same pair of vertices. If v == w we add a loop to the graph at
+ * vertex v.
+ *
+ * @param g pointer to the graph in which we add the edge
+ * @param v one of the vertices
+ * @param w the other of the vertices (may be same as v)
+ */
void graph_add_edge(graph_t *g, const size_t v, const size_t w);
#endif
diff --git a/test_graph.c b/test_graph.c
@@ -1,8 +1,75 @@
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
-#include "fheap.h"
+#include "graph.h"
+
+static void test_graph_maker() {
+ graph_t g;
+ graph_init(&g, 10);
+
+ // create Petersen graph
+ graph_add_edge(&g, 0, 1);
+ graph_add_edge(&g, 0, 4);
+ graph_add_edge(&g, 0, 5);
+ graph_add_edge(&g, 1, 2);
+ graph_add_edge(&g, 1, 6);
+ graph_add_edge(&g, 2, 3);
+ graph_add_edge(&g, 2, 7);
+ graph_add_edge(&g, 3, 4);
+ graph_add_edge(&g, 3, 8);
+ graph_add_edge(&g, 4, 9);
+ graph_add_edge(&g, 5, 7);
+ graph_add_edge(&g, 7, 9);
+ graph_add_edge(&g, 9, 6);
+ graph_add_edge(&g, 6, 8);
+ graph_add_edge(&g, 8, 5);
+
+ graph_clear(&g);
+}
+
+static void test_graph_bfs() {
+ graph_t g;
+ graph_init(&g, 10);
+
+ // create Petersen graph
+ graph_add_edge(&g, 0, 1);
+ graph_add_edge(&g, 0, 4);
+ graph_add_edge(&g, 0, 5);
+ graph_add_edge(&g, 1, 2);
+ graph_add_edge(&g, 1, 6);
+ graph_add_edge(&g, 2, 3);
+ graph_add_edge(&g, 2, 7);
+ graph_add_edge(&g, 3, 4);
+ graph_add_edge(&g, 3, 8);
+ graph_add_edge(&g, 4, 9);
+ graph_add_edge(&g, 5, 7);
+ graph_add_edge(&g, 7, 9);
+ graph_add_edge(&g, 9, 6);
+ graph_add_edge(&g, 6, 8);
+ graph_add_edge(&g, 8, 5);
+
+ uint64_t expected[10] = {0, 1, 4, 5, 2, 6, 3, 9, 7, 8};
+ uint64_t t;
+ size_t i;
+
+ graph_bfs_t bfs;
+ graph_bfs_init(&bfs, &g, 0);
+
+ for(i = 0; i < 10; i++) {
+ t = graph_bfs_next(&bfs, &g);
+ assert(t == expected[i]);
+ }
+
+ assert(graph_bfs_next(&bfs, &g) == UINT64_MAX);
+
+ graph_bfs_clear(&bfs);
+
+ graph_clear(&g);
+}
int main() {
- printf("test unimplemented\n");
+ test_graph_maker();
+ test_graph_bfs();
+
+ printf("tests ok\n");
}
