4 files changed, 0 insertions, 413 deletions

diff --git a/sem1/algo/workshop2/dijkstra/Makefile b/sem1/algo/workshop2/dijkstra/Makefile
deleted file mode 100644
index 7837354..0000000
--- a/sem1/algo/workshop2/dijkstra/Makefile
+++ /dev/null
@@ -1,31 +0,0 @@
-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/sem1/algo/workshop2/dijkstra/dijkstra.c b/sem1/algo/workshop2/dijkstra/dijkstra.c
deleted file mode 100644
index 555a125..0000000
--- a/sem1/algo/workshop2/dijkstra/dijkstra.c
+++ /dev/null
@@ -1,120 +0,0 @@
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.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() {
-
-	graph_from_dot(stdin, &g);
-
-	dijkstra(&g, graph_vertex(&g, "0"));
-
-	graph_to_dot(stdout, &g);
-
-	return 0;
-}
diff --git a/sem1/algo/workshop2/dijkstra/graph.c b/sem1/algo/workshop2/dijkstra/graph.c
deleted file mode 100644
index 8f62981..0000000
--- a/sem1/algo/workshop2/dijkstra/graph.c
+++ /dev/null
@@ -1,215 +0,0 @@
-#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;
-	// 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);
-	}
-}
-
-vertex_t *graph_vertex(graph_t *g, char *ref) {
-	return table_lookup(g, ref);
-}
diff --git a/sem1/algo/workshop2/dijkstra/graph.h b/sem1/algo/workshop2/dijkstra/graph.h
deleted file mode 100644
index 5c078b8..0000000
--- a/sem1/algo/workshop2/dijkstra/graph.h
+++ /dev/null
@@ -1,47 +0,0 @@
-#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_