aboutsummaryrefslogtreecommitdiff
path: root/sem3/algo/mm12/dijkstra.c
diff options
context:
space:
mode:
authorJulian T <julian@jtle.dk>2020-10-12 16:26:42 +0200
committerJulian T <julian@jtle.dk>2020-10-12 16:54:48 +0200
commit4e05a55e373bd315e721d534a1711fec4c0054c5 (patch)
tree4fc0141760c2730ed79aaa4c7aa60ea45cc66cc0 /sem3/algo/mm12/dijkstra.c
parentb7f9cf43c8a9ab3400cbb30d5e1cadb0c6c2cf23 (diff)
Moved to linux kernel inspired clang-format
Diffstat (limited to 'sem3/algo/mm12/dijkstra.c')
-rw-r--r--sem3/algo/mm12/dijkstra.c195
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;
}