From 6db1a2cdd3b96731f2e092d55d8c2136eabc52d0 Mon Sep 17 00:00:00 2001 From: Julian T Date: Tue, 11 Feb 2020 12:24:56 +0100 Subject: Rename and cleanup --- sem1/algo/workshop2/dijkstra/Makefile | 31 ----- sem1/algo/workshop2/dijkstra/dijkstra.c | 120 ------------------ sem1/algo/workshop2/dijkstra/graph.c | 215 -------------------------------- sem1/algo/workshop2/dijkstra/graph.h | 47 ------- 4 files changed, 413 deletions(-) delete mode 100644 sem1/algo/workshop2/dijkstra/Makefile delete mode 100644 sem1/algo/workshop2/dijkstra/dijkstra.c delete mode 100644 sem1/algo/workshop2/dijkstra/graph.c delete mode 100644 sem1/algo/workshop2/dijkstra/graph.h (limited to 'sem1/algo/workshop2/dijkstra') 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 -#include -#include -#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 -#include -#include -#include - -#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_ -- cgit v1.2.3