aboutsummaryrefslogtreecommitdiff
path: root/sem3/algo/workshop2/dijkstra
diff options
context:
space:
mode:
Diffstat (limited to 'sem3/algo/workshop2/dijkstra')
-rw-r--r--sem3/algo/workshop2/dijkstra/dijkstra.c36
-rw-r--r--sem3/algo/workshop2/dijkstra/graph.c76
2 files changed, 64 insertions, 48 deletions
diff --git a/sem3/algo/workshop2/dijkstra/dijkstra.c b/sem3/algo/workshop2/dijkstra/dijkstra.c
index 9609343..c112c6d 100644
--- a/sem3/algo/workshop2/dijkstra/dijkstra.c
+++ b/sem3/algo/workshop2/dijkstra/dijkstra.c
@@ -16,7 +16,8 @@ typedef struct {
struct list_item *end;
} list_t;
-void list_push(list_t *s, vertex_t *v) {
+void list_push(list_t *s, vertex_t *v)
+{
// Create
list_item_t *i = malloc(sizeof(list_item_t));
i->next = NULL;
@@ -24,7 +25,7 @@ void list_push(list_t *s, vertex_t *v) {
i->v = v;
// Link
- if( s->len == 0 ) {
+ if ( s->len == 0 ) {
s->begin = i;
} else {
s->end->next = i;
@@ -35,26 +36,27 @@ void list_push(list_t *s, vertex_t *v) {
s->len++;
}
-vertex_t *list_pop_smallest(list_t *s) {
+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) ) {
+ 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 ) {
+ if ( smallest == s->begin ) {
s->begin = smallest->next;
} else {
smallest->prev->next = smallest->next;
}
- if( smallest == s->end ) {
+ if ( smallest == s->end ) {
s->end = smallest->prev;
} else {
smallest->next->prev = smallest->prev;
@@ -71,20 +73,22 @@ vertex_t *list_pop_smallest(list_t *s) {
graph_t g;
// Assumes u has an edge to v
-void relax(vertex_t *u, vertex_t *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)) {
+ while (e && e->next && strcmp(e->to->ref, v->ref)) {
e = e->next;
}
- if( v->dist == -1 || v->dist > (u->dist + e->weight) ) {
+ 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) {
+void dijkstra(graph_t *g, vertex_t *s)
+{
list_t list;
list.len = 0;
list.end = list.begin = 0;
@@ -93,24 +97,24 @@ void dijkstra(graph_t *g, vertex_t *s) {
{
vertex_t *v = vertex_next(g, NULL);
- while( v ) {
+ while ( v ) {
list_push(&list, v);
v = vertex_next(g, v);
}
}
- while( list.len ) {
+ while ( list.len ) {
vertex_t *u = list_pop_smallest(&list);
edge_t *e = u->adj;
- while( e ) {
+ while ( e ) {
relax(u, e->to );
e = e->next;
}
}
}
-int main() {
-
+int main()
+{
int count = graph_from_dot(stdin, &g);
clock_t start, end;
diff --git a/sem3/algo/workshop2/dijkstra/graph.c b/sem3/algo/workshop2/dijkstra/graph.c
index 3f24ccf..51206c4 100644
--- a/sem3/algo/workshop2/dijkstra/graph.c
+++ b/sem3/algo/workshop2/dijkstra/graph.c
@@ -6,9 +6,10 @@
#include "graph.h"
// Hashtable
-static unsigned int hash(char *s) {
+static unsigned int hash(char *s)
+{
uint32_t hv = 0;
- for( int i = 0; s[i] != '\0'; i++ ) {
+ 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);
@@ -20,7 +21,8 @@ static unsigned int hash(char *s) {
}
-static void table_insert(graph_t *g, vertex_t *v, char *var) {
+static void table_insert(graph_t *g, vertex_t *v, char *var)
+{
unsigned int index = hash(var);
// Save old value
@@ -33,19 +35,21 @@ static void table_insert(graph_t *g, vertex_t *v, char *var) {
g->hashtable[index]->next = oldSym;
}
-static vertex_t *table_lookup(graph_t *g, char *var) {
+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) {
+ while (n != NULL && strcmp(n->ref, var) != 0) {
n = n->next;
}
return n;
}
-static vertex_t *create_vertex(char *ref) {
+static vertex_t *create_vertex(char *ref)
+{
// Get some space TODO check for null
vertex_t *v = malloc(sizeof(vertex_t));
@@ -58,7 +62,8 @@ static vertex_t *create_vertex(char *ref) {
return v;
}
-static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
+static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight)
+{
edge_t *old = from->adj;
// Create new list node
@@ -69,12 +74,12 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
// Do new link
e->next = old;
- if( old ) {
+ if ( old ) {
e->prev = old->prev;
old->prev = e;
} else { e->prev = NULL; }
- if( e->prev ) {
+ if ( e->prev ) {
e->prev->next = e;
}
@@ -84,16 +89,17 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
}
// For iterating edges
-edge_t *edge_next(graph_t *g, edge_t *e) {
- if(e == NULL || e->next == NULL ) {
+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 ) {
+ while ( v ) {
// Check if found
- if( v->adj ) {
+ if ( v->adj ) {
return v->adj;
}
@@ -108,12 +114,13 @@ edge_t *edge_next(graph_t *g, edge_t *e) {
return e->next;
}
-vertex_t *vertex_next(graph_t *g, vertex_t *v) {
- if( v == NULL || v->next == NULL) {
+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] ) {
+ for ( ; i < HASHSIZE; i++) {
+ if ( g->hashtable[i] ) {
return g->hashtable[i];
}
}
@@ -125,15 +132,16 @@ vertex_t *vertex_next(graph_t *g, vertex_t *v) {
return v->next;
}
-void graph_edge(graph_t *g, char *from, char *to, int weight) {
+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 ) {
+ 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 ) {
+ if ( (tov = table_lookup(g, to)) == NULL ) {
tov = create_vertex(to);
table_insert(g, tov, to);
}
@@ -142,15 +150,16 @@ void graph_edge(graph_t *g, char *from, char *to, int weight) {
create_edge(fromv, tov, weight);
}
-int graph_print_adj(graph_t *g, char *ref) {
+int graph_print_adj(graph_t *g, char *ref)
+{
vertex_t *v = table_lookup(g, ref);
- if( v == NULL ) {
+ if ( v == NULL ) {
return 1;
}
edge_t *e = v->adj;
printf("[ ");
- while(e && e->from->ref == ref) {
+ while (e && e->from->ref == ref) {
printf("%s[%d] ", e->to->ref, e->weight);
e = e->next;
}
@@ -159,19 +168,20 @@ int graph_print_adj(graph_t *g, char *ref) {
return 0;
}
-int graph_to_dot(FILE *f, graph_t *g) {
+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 ) {
+ 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 ) {
+ 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);
}
@@ -181,26 +191,27 @@ int graph_to_dot(FILE *f, graph_t *g) {
}
// This was created in a hurry sorry
-int graph_from_dot(FILE *f, graph_t *g) {
+int graph_from_dot(FILE *f, graph_t *g)
+{
char from[100], to[100];
int weight;
int count = 0;
// just fscanf it
- for(;;) {
+ 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 ) {
+ if ( c <= 0 ) {
break;
}
- if( *from == 0 || *to == 0 ) {
+ if ( *from == 0 || *to == 0 ) {
continue;
}
// Sorry i just want it to work
int tolen = strlen(to);
- if( to[tolen-1] == ';' ) {
+ if ( to[tolen-1] == ';' ) {
to[tolen-1] = 0;
}
@@ -214,6 +225,7 @@ int graph_from_dot(FILE *f, graph_t *g) {
return count;
}
-vertex_t *graph_vertex(graph_t *g, char *ref) {
+vertex_t *graph_vertex(graph_t *g, char *ref)
+{
return table_lookup(g, ref);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-27 10:24:01 +0000