wdg

commit bf658d3664a07888351c5ed61901d167eecaa2c0
Author: olikru <olikru@tkruger.se>
Date:   Mon,  8 Jan 2024 15:13:19 +0100

initial

Diffstat:
A
Makefile
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
A
README
 | 
5
+++++
A
TODO
 | 
2
++
A
test_wdg.c
 | 
8
++++++++
A
wdg.c
 | 
75
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
wdg.h
 | 
18
++++++++++++++++++

6 files changed, 151 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,43 @@
+.SUFFIXES: .c .o .so
+CC=clang
+CFLAGS+=-std=c99 -pedantic -Wall -Werror -Wstrict-prototypes
+CFLAGS+=-Wmissing-prototypes -Wmissing-declarations -Wshadow
+CFLAGS+=-Wpointer-arith -Wcast-qual -Wsign-compare
+CFLAGS+=-O2 -g
+CFLAGS+=-fstack-protector-all -Wtype-limits -fno-common
+CFLAGS+=-fno-builtin
+CFLAGS+=-I/usr/local/include
+
+CFLAGS+=-I$(HOME)/.local/include
+LFLAGS+=-L$(HOME)/.local/lib -lfheap -lstack_u64
+
+INSTALL_PATH=$(HOME)/.local
+BUILD=build
+
+TEST_SOURCE=test_wdg.c
+HEADER=wdg.h
+OBJS=wdg.o
+SHARED=wdg.so
+LIBSHARED=libwdg.so
+
+all: build $(OBJS) $(SHARED) test
+
+.c.o:
+	$(CC) $(CFLAGS) -c $< -o $(BUILD)/$@
+
+.o.so:
+	$(CC) -shared -fPIC $(BUILD)/$< -o $(BUILD)/$@ $(LFLAGS)
+
+test: $(TEST_SOURCE)
+	$(CC) $(CFLAGS) -o $(BUILD)/test $(TEST_SOURCE) $(BUILD)/$(OBJS) $(LFLAGS)
+
+build:
+	mkdir -p $(BUILD)
+
+install:
+	cp $(BUILD)/$(SHARED) $(INSTALL_PATH)/lib/$(LIBSHARED)
+	chmod 644 $(INSTALL_PATH)/lib/$(LIBSHARED)
+	cp $(HEADER) $(INSTALL_PATH)/include/
+
+clean:
+	rm -rf $(BUILD)
diff --git a/README b/README
@@ -0,0 +1,5 @@
+wdg
+===
+
+Weighted directed graph type with some related functions. In particular
+one can Dijkstra it.
diff --git a/TODO b/TODO
@@ -0,0 +1,2 @@
+* Implement unit tests
+* Documentation
diff --git a/test_wdg.c b/test_wdg.c
@@ -0,0 +1,8 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "fheap.h"
+
+int main() {
+  printf("test unimplemented\n");
+}
diff --git a/wdg.c b/wdg.c
@@ -0,0 +1,75 @@
+#include "wdg.h"
+
+void wdg_init(wdg_t *g, const size_t n) {
+  g->n = n;
+  g->nbrs = malloc(n * sizeof(*(g->nbrs)));
+  g->weight = malloc(n * sizeof(*(g->weight)));
+
+  size_t i;
+  for (i = 0; i < n; i++) {
+    stack_u64_init(&g->nbrs[i]);
+    stack_u64_init(&g->weight[i]);
+  }
+}
+
+void wdg_clear(wdg_t *g) {
+  size_t i;
+  for (i = 0; i < g->n; i++) {
+    stack_u64_clear(&g->nbrs[i]);
+    stack_u64_clear(&g->nbrs[i]);
+  }
+  free(g->nbrs);
+  free(g->weight);
+}
+
+void wdg_add_edge(wdg_t *g, const size_t v, const size_t w, uint64_t weight) {
+  stack_u64_push(&g->nbrs[v], w);
+  stack_u64_push(&g->weight[v], weight);
+}
+
+uint64_t wdg_dijkstra(wdg_t *g, const size_t source, const size_t target) {
+  size_t i;
+  uint64_t dist[g->n];
+  dist[source] = 0;
+  size_t prev[g->n];
+
+  fheap_t q;
+  fheap_init(&q);
+
+  size_t vertices[g->n];
+  fnode_t *qvertex[g->n];
+
+  for (i = 0; i < g->n; i++) {
+    vertices[i] = i;
+    if (i != source) {
+      dist[i] = UINT64_MAX;
+      prev[i] = SIZE_MAX;
+    }
+
+    qvertex[i] = fheap_insert(&q, dist[i], &(vertices[i]));
+  }
+
+  void *up;
+  size_t u, v;
+  uint64_t alt;
+  while (q.n > 0) {
+    size_t value = fheap_extract_min(&up, &q);
+    u = *(size_t *)up;
+    if (u == target)
+      break;
+    if (value == UINT64_MAX)
+      break;
+
+    for (i = 0; i < (g->nbrs[u]).nmemb; i++) {
+      v = (g->nbrs[u]).data[i];
+      alt = dist[u] + (g->weight[u]).data[i];
+      if (alt < dist[v]) {
+        dist[v] = alt;
+        prev[v] = u;
+        fheap_decrease_value(&q, qvertex[v], alt);
+      }
+    }
+  }
+
+  return dist[target];
+}
diff --git a/wdg.h b/wdg.h
@@ -0,0 +1,18 @@
+#ifndef WDG_H
+#define WDG_H
+
+#include <fheap.h>
+#include <stack_u64.h>
+
+typedef struct {
+  size_t n;
+  stack_u64_t *nbrs;
+  stack_u64_t *weight;
+} wdg_t;
+
+void wdg_init(wdg_t *g, const size_t n);
+void wdg_clear(wdg_t *g);
+void wdg_add_edge(wdg_t *g, const size_t v, const size_t w, uint64_t weight);
+uint64_t wdg_dijkstra(wdg_t *g, const size_t source, const size_t target);
+
+#endif