diff options
author | Julian T <julian@jtle.dk> | 2020-10-12 16:26:42 +0200 |
---|---|---|
committer | Julian T <julian@jtle.dk> | 2020-10-12 16:54:48 +0200 |
commit | 4e05a55e373bd315e721d534a1711fec4c0054c5 (patch) | |
tree | 4fc0141760c2730ed79aaa4c7aa60ea45cc66cc0 /sem3/algo/mm12/dijkstra.c | |
parent | b7f9cf43c8a9ab3400cbb30d5e1cadb0c6c2cf23 (diff) |
Moved to linux kernel inspired clang-format
Diffstat (limited to 'sem3/algo/mm12/dijkstra.c')
-rw-r--r-- | sem3/algo/mm12/dijkstra.c | 195 |
1 files changed, 97 insertions, 98 deletions
diff --git a/sem3/algo/mm12/dijkstra.c b/sem3/algo/mm12/dijkstra.c index b4f0f94..b4f0063 100644 --- a/sem3/algo/mm12/dijkstra.c +++ b/sem3/algo/mm12/dijkstra.c @@ -3,68 +3,68 @@ #include "graph.h" typedef struct list_item { - vertex_t *v; - struct list_item *next; - struct list_item *prev; + 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; + 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++; + // 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) { - list_item_t *smallest = s->begin; - - // Search - list_item_t *i = s->begin; - while ( i ) { - if ( 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; + list_item_t *smallest = s->begin; + + // Search + list_item_t *i = s->begin; + while (i) { + if (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; @@ -72,66 +72,65 @@ 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 && 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; - } + // Get edge between these two guys + edge_t *e = u->adj; + while (e && e->next && 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; - } - } + 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_edge(&g, 'a', 'b', 2); + graph_edge(&g, 'a', 'f', 1); - graph_edge(&g, 'a', 'b', 2); - graph_edge(&g, 'a', 'f', 1); + graph_edge(&g, 'b', 'd', 3); + graph_edge(&g, 'b', 'c', 4); - graph_edge(&g, 'b', 'd', 3); - graph_edge(&g, 'b', 'c', 4); + graph_edge(&g, 'd', 'b', 1); + graph_edge(&g, 'd', 'e', 8); - graph_edge(&g, 'd', 'b', 1); - graph_edge(&g, 'd', 'e', 8); + graph_edge(&g, 'c', 'a', 7); + graph_edge(&g, 'c', 'd', 7); + graph_edge(&g, 'c', 'f', 2); - graph_edge(&g, 'c', 'a', 7); - graph_edge(&g, 'c', 'd', 7); - graph_edge(&g, 'c', 'f', 2); + graph_edge(&g, 'e', 'c', 2); + graph_edge(&g, 'e', 'f', 2); - graph_edge(&g, 'e', 'c', 2); - graph_edge(&g, 'e', 'f', 2); + dijkstra(&g, g.vertexes['a']); - dijkstra(&g, g.vertexes['a']); + graph_to_dot(stdout, &g); - graph_to_dot(stdout, &g); - - return 0; + return 0; } |