9 files changed, 800 insertions, 0 deletions

diff --git a/sem3/algo/workshop2/dfs/Makefile b/sem3/algo/workshop2/dfs/Makefile
new file mode 100644
index 0000000..790bb94
--- /dev/null
+++ b/sem3/algo/workshop2/dfs/Makefile
@@ -0,0 +1,41 @@
+CC = gcc
+# Enable gdb and pull include files from current dir
+CFLAGS = -ggdb -I.
+LDFLAGS = 
+
+BINARY = dfs
+BUILD_DIR = build
+
+# Capture c files 
+c_files = $(wildcard *.c)
+
+# Convert c names to corrosponding o names
+OBJ = $(patsubst %.c, $(BUILD_DIR)/%.o, $(c_files))
+
+# $@ is the %.o file and $^ is the %.c file
+$(BUILD_DIR)/%.o: %.c
+	mkdir -p $(dir $@)
+	$(CC) -c -o $@ $^ $(CFLAGS)
+
+# $@ becomes left part thus linked
+$(BINARY): $(OBJ)
+	$(CC) -o $@ $^ $(LDFLAGS)
+
+.PHONY: clean run
+
+run: $(BINARY)
+	./$(BINARY)
+
+hej.png: hej.dot
+	dot -Tpng hej.dot > hej.png
+
+hej.dot: $(BINARY)
+	./$(BINARY) > hej.dot
+
+draw: hej.png
+	nomacs hej.png
+
+clean:
+	rm -f $(OBJ) $(BINARY)
+	rm hej*
+	rmdir $(BUILD_DIR)
diff --git a/sem3/algo/workshop2/dfs/dfs b/sem3/algo/workshop2/dfs/dfs
new file mode 100755
index 0000000..0d9ff14
--- /dev/null
+++ b/sem3/algo/workshop2/dfs/dfs
diff --git a/sem3/algo/workshop2/dfs/dfs.c b/sem3/algo/workshop2/dfs/dfs.c
new file mode 100644
index 0000000..1244895
--- /dev/null
+++ b/sem3/algo/workshop2/dfs/dfs.c
@@ -0,0 +1,107 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include <time.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "graph.h"
+
+graph_t g;
+graph_t newg;
+int step;
+
+void dfs_visit(graph_t *g, vertex_t *u, bool doprint) {
+	if( doprint ) {
+		printf("dfs_visit( %s )\n", u->ref);
+	}
+	step++;
+	u->dtime = step;
+	u->color = COLOR_GRAY;
+	
+	// For every adj
+	edge_t *e = u->adj;
+	while( e ) {
+		vertex_t *v = e->to;
+		if( v->color == COLOR_WHITE ) {
+			graph_edge(&newg, v->ref, u->ref, 1);
+			dfs_visit(g, v, doprint);
+		}
+		e = e->next;
+	}
+
+	u->color = COLOR_BLACK;
+	step++;
+	u->ftime = step;
+}
+
+
+void dfs(graph_t *g, bool doprint) {
+	step = 0;
+
+	// For every edge
+	vertex_t *u = vertex_next(g, NULL);
+	while( u ) {
+		if( u->color == COLOR_WHITE ) {
+			dfs_visit(g, u, doprint);
+		}
+		u = vertex_next(g, u);
+	}
+}
+
+#define BENCH 9999
+
+int main() {
+
+	// benchmark
+
+	// Start by generating
+	for(int i = 0; i < BENCH; i++) {
+		char from[5];
+		char to[5];
+		sprintf(from, "%d", i);
+		sprintf(to, "%d", rand() % BENCH);
+		graph_edge(&g, from, to, 1);
+	}
+	FILE *f = fopen("hej.dot", "w");
+	graph_to_dot(f, &g);
+
+	{
+		// Timing start
+		clock_t t;
+		t = clock();
+
+		dfs(&g, true);
+
+		// Timing stop
+		t = clock() - t;
+		double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
+		printf("Dfs took %f seconds\n", time_taken);
+	}
+	
+	return 0;
+	
+	graph_edge(&g, "hej", "med", 1);
+	graph_edge(&g, "med", "dig", 1);
+	graph_edge(&g, "dig", "hvordan", 1);
+
+	graph_edge(&g, "det", "hvordan", 1);
+	graph_edge(&g, "hvordan", "det", 1);
+
+	graph_to_dot(stdout, &g);
+	
+	// Timing start
+	clock_t t;
+	t = clock();
+
+	// Dfs slower when printing.
+	dfs(&g, true);
+
+	// Timing stop
+	t = clock() - t;
+	double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
+	printf("Dfs took %f seconds\n", time_taken);
+
+	//graph_to_dot(stdout, &newg);
+
+	return 0;
+}
diff --git a/sem3/algo/workshop2/dfs/graph.c b/sem3/algo/workshop2/dfs/graph.c
new file mode 100644
index 0000000..0f5048c
--- /dev/null
+++ b/sem3/algo/workshop2/dfs/graph.c
@@ -0,0 +1,181 @@
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "graph.h"
+
+// Hashtable
+static unsigned int hash(char *s) {
+	uint32_t hv = 0;
+	for( int i = 0; s[i] != '\0'; i++ ) {
+		// take MSB 6 bits of hv and xors with LSB of s[i]
+		uint32_t v = ( hv >> 26 ) ^ (s[i] & 0x3f);
+
+		// Push those back on hv
+		hv = (hv << 4) | v;
+	}
+	// Return appropriate size
+	return hv % HASHSIZE;
+}
+
+
+static void table_insert(graph_t *g, vertex_t *v, char *var) {
+	unsigned int index = hash(var);
+
+	// Save old value
+	vertex_t *oldSym = g->hashtable[index];
+
+	// Make new
+	g->hashtable[index] = v;
+
+	// Link old one
+	g->hashtable[index]->next = oldSym;
+}
+
+static vertex_t *table_lookup(graph_t *g, char *var) {
+	unsigned int index = hash(var);
+	vertex_t *n = g->hashtable[index];
+
+	// Look trough list
+	while(n != NULL && strcmp(n->ref, var) != 0) {
+		n = n->next;
+	}
+
+	return n;
+}
+
+static vertex_t *create_vertex(char *ref) {
+	// Get some space TODO check for null
+	vertex_t *v = malloc(sizeof(vertex_t));
+
+	// Set values
+	v->ref = strdup(ref);
+	v->color = COLOR_WHITE;
+	v->next = NULL;
+	v->adj = NULL;
+	return v;
+}
+
+static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
+	edge_t *old = from->adj;
+
+	// Create new list node
+	edge_t *e = malloc(sizeof(edge_t));
+	e->weight = weight;
+	e->from = from;
+	e->to = to;
+
+	// Do new link
+	e->next = old;
+	if( old ) {
+		e->prev = old->prev;
+		old->prev = e;
+	} else { e->prev = NULL; }
+	
+	if( e->prev ) {
+		e->prev->next = e;
+	}
+
+	from->adj = e;
+
+	return e;
+}
+
+// For iterating edges
+edge_t *edge_next(graph_t *g, edge_t *e) {
+	if(e == NULL || e->next == NULL ) {
+		// Find next index
+		vertex_t *v = e ? e->from : NULL;
+
+		// Find next vertex
+		v = vertex_next(g, v);
+		while( v ) {
+			// Check if found
+			if( v->adj ) {
+				return v->adj;
+			}
+
+			v = vertex_next(g, v);
+		}
+
+		// No next vertex
+		return NULL;
+	}
+
+	// Not finished with this adj list
+	return e->next;
+}
+
+vertex_t *vertex_next(graph_t *g, vertex_t *v) {
+	if( v == NULL || v->next == NULL) {
+		// Go to next index in hashtable
+		int i = v ? hash(v->ref)+1 : 0;
+		for( ; i < HASHSIZE; i++) {
+			if( g->hashtable[i] ) {
+				return g->hashtable[i];
+			}
+		}
+
+		// No next
+		return NULL;
+	}
+
+	return v->next;
+}
+
+void graph_edge(graph_t *g, char *from, char *to, int weight) {
+	vertex_t *fromv, *tov;
+	// Does a exists
+	if( (fromv = table_lookup(g, from)) == NULL ) {
+		fromv = create_vertex(from);
+		table_insert(g, fromv, from);
+	}
+	// What about b
+	if( (tov = table_lookup(g, to)) == NULL ) {
+		tov = create_vertex(to);
+		table_insert(g, tov, to);
+	}
+
+	// Add edge
+	create_edge(fromv, tov, weight);
+}
+
+int graph_print_adj(graph_t *g, char *ref) {
+	vertex_t *v = table_lookup(g, ref);
+	if( v == NULL ) {
+		return 1;
+	}
+	
+	edge_t *e = v->adj;
+	printf("[ ");
+	while(e && e->from->ref == ref) {
+		printf("%s[%d] ", e->to->ref, e->weight);
+		e = e->next;
+	}
+	printf("]\n");
+
+	return 0;
+}
+
+int graph_to_dot(FILE *f, graph_t *g) {
+	// print pre stuff
+	fprintf(f, "digraph coolgraph {\n");
+
+	// Label all nodes
+	vertex_t *v = vertex_next(g, NULL);
+	while( v ) {
+		fprintf(f, "%s [label=\"%s\"];\n", v->ref, v->ref);
+		v = vertex_next(g, v);
+	}
+	// Print all the edges
+	edge_t *e = edge_next(g, NULL);
+	while( e ) {
+		fprintf(f, "%s -> %s [label = %d];\n", e->from->ref, e->to->ref, e->weight);
+		e = edge_next(g, e);
+	}
+
+	// done
+	fprintf(f, "}\n");
+}
+
diff --git a/sem3/algo/workshop2/dfs/graph.h b/sem3/algo/workshop2/dfs/graph.h
new file mode 100644
index 0000000..e169a8a
--- /dev/null
+++ b/sem3/algo/workshop2/dfs/graph.h
@@ -0,0 +1,45 @@
+#ifndef GRAPH_H_
+#define GRAPH_H_
+
+#define COLOR_WHITE 0
+#define COLOR_GRAY  1
+#define COLOR_BLACK 2
+
+#define HASHSIZE 128
+
+struct vertex_struct;
+
+// Linked list
+typedef struct edge_struct {
+	int weight;
+	struct vertex_struct *from;
+	struct vertex_struct *to;
+	// Linked list stuff
+	struct edge_struct *next;
+	struct edge_struct *prev;
+} edge_t;
+
+typedef struct vertex_struct {
+	char *ref;
+	int color;
+
+	int dtime;
+	int ftime;
+
+	edge_t *adj;
+
+	// Hash table stuff
+	struct vertex_struct *next;
+} vertex_t;
+
+typedef struct {
+	vertex_t *hashtable[128];
+} graph_t;
+
+int graph_to_dot(FILE *f, graph_t *g);
+int graph_print_adj(graph_t *g, char *ref);
+void graph_edge(graph_t *g, char *from, char *to, int weight);
+edge_t *edge_next(graph_t *g, edge_t *e);
+vertex_t *vertex_next(graph_t *g, vertex_t *v);
+
+#endif // GRAPH_H_
diff --git a/sem3/algo/workshop2/dijkstra/Makefile b/sem3/algo/workshop2/dijkstra/Makefile
new file mode 100644
index 0000000..7837354
--- /dev/null
+++ b/sem3/algo/workshop2/dijkstra/Makefile
@@ -0,0 +1,31 @@
+CC = gcc
+# Enable gdb and pull include files from current dir
+CFLAGS = -ggdb -I.
+LDFLAGS = 
+
+BINARY = dijkstra
+BUILD_DIR = build
+
+# Capture c files 
+c_files = $(wildcard *.c)
+
+# Convert c names to corrosponding o names
+OBJ = $(patsubst %.c, $(BUILD_DIR)/%.o, $(c_files))
+
+# $@ is the %.o file and $^ is the %.c file
+$(BUILD_DIR)/%.o: %.c
+	mkdir -p $(dir $@)
+	$(CC) -c -o $@ $^ $(CFLAGS)
+
+# $@ becomes left part thus linked
+$(BINARY): $(OBJ)
+	$(CC) -o $@ $^ $(LDFLAGS)
+
+.PHONY: clean run
+
+run: $(BINARY)
+	./$(BINARY)
+
+clean:
+	rm -f $(OBJ) $(BINARY)
+	rmdir $(BUILD_DIR)
diff --git a/sem3/algo/workshop2/dijkstra/dijkstra.c b/sem3/algo/workshop2/dijkstra/dijkstra.c
new file mode 100644
index 0000000..9609343
--- /dev/null
+++ b/sem3/algo/workshop2/dijkstra/dijkstra.c
@@ -0,0 +1,129 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include "graph.h"
+
+typedef struct list_item {
+	vertex_t *v;
+	struct list_item *next;
+	struct list_item *prev;
+} list_item_t;
+
+typedef struct {
+	int len;
+	struct list_item *begin;
+	struct list_item *end;
+} list_t;
+
+void list_push(list_t *s, vertex_t *v) {
+	// Create 
+	list_item_t *i = malloc(sizeof(list_item_t));
+	i->next = NULL;
+	i->prev = NULL;
+	i->v = v;
+
+	// Link
+	if( s->len == 0 ) {
+		s->begin = i;
+	} else {
+		s->end->next = i;
+		i->prev = s->end;
+	}
+
+	s->end = i;
+	s->len++;
+}
+
+vertex_t *list_pop_smallest(list_t *s) {
+	//printf("beginning %s(%d)\n", s->begin->v->ref, s->begin->v->dist);
+	list_item_t *smallest = s->begin;
+
+	// Search
+	list_item_t *i = s->begin;
+	while( i ) {
+		if( smallest->v->dist == -1 || (i->v->dist != -1 && i->v->dist < smallest->v->dist) ) {
+			smallest = i;
+		}
+		i = i->next;
+	}
+
+	if( smallest == s->begin ) {
+		s->begin = smallest->next;
+	} else {
+		smallest->prev->next = smallest->next;
+	}
+
+	if( smallest == s->end ) {
+		s->end = smallest->prev;
+	} else {
+		smallest->next->prev = smallest->prev;
+	}
+
+	vertex_t *v = smallest->v;
+	free(smallest);
+
+	s->len--;
+
+	return v;
+}
+
+graph_t g;
+
+// Assumes u has an edge to v
+void relax(vertex_t *u, vertex_t *v) {
+	// Get edge between these two guys
+	edge_t *e = u->adj;
+	while(e && e->next && strcmp(e->to->ref, v->ref)) { 
+		e = e->next; 
+	}
+
+	if( v->dist == -1 || v->dist > (u->dist + e->weight) ) {
+		v->dist = u->dist + e->weight;
+		v->p = u;
+	}
+}
+
+void dijkstra(graph_t *g, vertex_t *s) {
+	list_t list;
+	list.len = 0;
+	list.end = list.begin = 0;
+
+	s->dist = 0;
+
+	{
+		vertex_t *v = vertex_next(g, NULL);
+		while( v ) {
+			list_push(&list, v);
+			v = vertex_next(g, v);
+		}
+	}
+
+	while( list.len ) {
+		vertex_t *u = list_pop_smallest(&list);
+		edge_t *e = u->adj;
+		while( e ) {
+			relax(u, e->to );
+			e = e->next;
+		}
+	}
+}
+
+int main() {
+
+	int count = graph_from_dot(stdin, &g);
+
+	clock_t start, end;
+	double cpu_time_used;
+
+	start = clock();
+	dijkstra(&g, graph_vertex(&g, "0"));
+	end = clock();
+	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
+
+	printf("%d;%f\n", count, cpu_time_used);
+
+	//graph_to_dot(stdout, &g);
+
+	return 0;
+}
diff --git a/sem3/algo/workshop2/dijkstra/graph.c b/sem3/algo/workshop2/dijkstra/graph.c
new file mode 100644
index 0000000..3f24ccf
--- /dev/null
+++ b/sem3/algo/workshop2/dijkstra/graph.c
@@ -0,0 +1,219 @@
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "graph.h"
+
+// Hashtable
+static unsigned int hash(char *s) {
+	uint32_t hv = 0;
+	for( int i = 0; s[i] != '\0'; i++ ) {
+		// take MSB 6 bits of hv and xors with LSB of s[i]
+		uint32_t v = ( hv >> 26 ) ^ (s[i] & 0x3f);
+
+		// Push those back on hv
+		hv = (hv << 4) | v;
+	}
+	// Return appropriate size
+	return hv % HASHSIZE;
+}
+
+
+static void table_insert(graph_t *g, vertex_t *v, char *var) {
+	unsigned int index = hash(var);
+
+	// Save old value
+	vertex_t *oldSym = g->hashtable[index];
+
+	// Make new
+	g->hashtable[index] = v;
+
+	// Link old one
+	g->hashtable[index]->next = oldSym;
+}
+
+static vertex_t *table_lookup(graph_t *g, char *var) {
+	unsigned int index = hash(var);
+	vertex_t *n = g->hashtable[index];
+
+	// Look trough list
+	while(n != NULL && strcmp(n->ref, var) != 0) {
+		n = n->next;
+	}
+
+	return n;
+}
+
+static vertex_t *create_vertex(char *ref) {
+	// Get some space TODO check for null
+	vertex_t *v = malloc(sizeof(vertex_t));
+
+	// Set values
+	v->ref = strdup(ref);
+	v->color = COLOR_WHITE;
+	v->p = NULL;
+	v->dist = -1;
+	v->adj = NULL;
+	return v;
+}
+
+static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
+	edge_t *old = from->adj;
+
+	// Create new list node
+	edge_t *e = malloc(sizeof(edge_t));
+	e->weight = weight;
+	e->from = from;
+	e->to = to;
+
+	// Do new link
+	e->next = old;
+	if( old ) {
+		e->prev = old->prev;
+		old->prev = e;
+	} else { e->prev = NULL; }
+	
+	if( e->prev ) {
+		e->prev->next = e;
+	}
+
+	from->adj = e;
+
+	return e;
+}
+
+// For iterating edges
+edge_t *edge_next(graph_t *g, edge_t *e) {
+	if(e == NULL || e->next == NULL ) {
+		// Find next index
+		vertex_t *v = e ? e->from : NULL;
+
+		// Find next vertex
+		v = vertex_next(g, v);
+		while( v ) {
+			// Check if found
+			if( v->adj ) {
+				return v->adj;
+			}
+
+			v = vertex_next(g, v);
+		}
+
+		// No next vertex
+		return NULL;
+	}
+
+	// Not finished with this adj list
+	return e->next;
+}
+
+vertex_t *vertex_next(graph_t *g, vertex_t *v) {
+	if( v == NULL || v->next == NULL) {
+		// Go to next index in hashtable
+		int i = v ? hash(v->ref)+1 : 0;
+		for( ; i < HASHSIZE; i++) {
+			if( g->hashtable[i] ) {
+				return g->hashtable[i];
+			}
+		}
+
+		// No next
+		return NULL;
+	}
+
+	return v->next;
+}
+
+void graph_edge(graph_t *g, char *from, char *to, int weight) {
+	vertex_t *fromv, *tov;
+	// Does a exists
+	if( (fromv = table_lookup(g, from)) == NULL ) {
+		fromv = create_vertex(from);
+		table_insert(g, fromv, from);
+	}
+	// What about b
+	if( (tov = table_lookup(g, to)) == NULL ) {
+		tov = create_vertex(to);
+		table_insert(g, tov, to);
+	}
+
+	// Add edge
+	create_edge(fromv, tov, weight);
+}
+
+int graph_print_adj(graph_t *g, char *ref) {
+	vertex_t *v = table_lookup(g, ref);
+	if( v == NULL ) {
+		return 1;
+	}
+	
+	edge_t *e = v->adj;
+	printf("[ ");
+	while(e && e->from->ref == ref) {
+		printf("%s[%d] ", e->to->ref, e->weight);
+		e = e->next;
+	}
+	printf("]\n");
+
+	return 0;
+}
+
+int graph_to_dot(FILE *f, graph_t *g) {
+	// print pre stuff
+	fprintf(f, "digraph coolgraph {\n");
+
+	// Label all nodes
+	vertex_t *v = vertex_next(g, NULL);
+	while( v ) {
+		fprintf(f, "%s [label=\"%s(%d)\"];\n", v->ref, v->ref, v->dist);
+		v = vertex_next(g, v);
+	}
+	// Print all the edges
+	edge_t *e = edge_next(g, NULL);
+	while( e ) {
+		fprintf(f, "%s -> %s [label = %d%s];\n", e->from->ref, e->to->ref, e->weight, e->to->p == e->from ? " color=blue" : "");
+		e = edge_next(g, e);
+	}
+
+	// done
+	fprintf(f, "}\n");
+}
+
+// This was created in a hurry sorry
+int graph_from_dot(FILE *f, graph_t *g) {
+	char from[100], to[100];
+	int weight;
+	int count = 0;
+	// just fscanf it
+	for(;;) {
+		// Set first to zero
+		*from = 0;
+		*to = 0;
+		weight = 0;
+		int c = fscanf(f, "%s -> %s [label=%d];", from, to, &weight);
+		if( c <= 0 ) {
+			break;
+		}
+		if( *from == 0 || *to == 0 ) {
+			continue;
+		}
+		// Sorry i just want it to work
+		int tolen = strlen(to);
+		if( to[tolen-1] == ';' ) {
+			to[tolen-1] = 0;
+		}
+
+		weight = weight ? weight : 1;
+		//printf("Creating edge from %s to %s with w: %d\n", from, to, weight);
+
+		graph_edge(g, from, to, weight);
+		count++;
+	}
+
+	return count;
+}
+
+vertex_t *graph_vertex(graph_t *g, char *ref) {
+	return table_lookup(g, ref);
+}
diff --git a/sem3/algo/workshop2/dijkstra/graph.h b/sem3/algo/workshop2/dijkstra/graph.h
new file mode 100644
index 0000000..5c078b8
--- /dev/null
+++ b/sem3/algo/workshop2/dijkstra/graph.h
@@ -0,0 +1,47 @@
+#ifndef GRAPH_H_
+#define GRAPH_H_
+
+#define COLOR_WHITE 0
+#define COLOR_GRAY  1
+#define COLOR_BLACK 2
+
+#define HASHSIZE 128
+
+struct vertex_struct;
+
+// Linked list
+typedef struct edge_struct {
+	int weight;
+	struct vertex_struct *from;
+	struct vertex_struct *to;
+	// Linked list stuff
+	struct edge_struct *next;
+	struct edge_struct *prev;
+} edge_t;
+
+typedef struct vertex_struct {
+	char *ref;
+	int color;
+
+	int dist;
+	struct vertex_struct *p;
+
+	edge_t *adj;
+
+	// Hash table stuff
+	struct vertex_struct *next;
+} vertex_t;
+
+typedef struct {
+	vertex_t *hashtable[128];
+} graph_t;
+
+int graph_to_dot(FILE *f, graph_t *g);
+int graph_from_dot(FILE *f, graph_t *g);
+int graph_print_adj(graph_t *g, char *ref);
+void graph_edge(graph_t *g, char *from, char *to, int weight);
+edge_t *edge_next(graph_t *g, edge_t *e);
+vertex_t *vertex_next(graph_t *g, vertex_t *v);
+vertex_t *graph_vertex(graph_t *g, char *ref);
+
+#endif // GRAPH_H_