aboutsummaryrefslogtreecommitdiff
path: root/sem3/algo/mm12
diff options
context:
space:
mode:
Diffstat (limited to 'sem3/algo/mm12')
-rw-r--r--sem3/algo/mm12/dijkstra.c195
-rw-r--r--sem3/algo/mm12/graph.c198
-rw-r--r--sem3/algo/mm12/graph.h22
3 files changed, 208 insertions, 207 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;
}
diff --git a/sem3/algo/mm12/graph.c b/sem3/algo/mm12/graph.c
index e478103..f4039ec 100644
--- a/sem3/algo/mm12/graph.c
+++ b/sem3/algo/mm12/graph.c
@@ -4,127 +4,129 @@
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 = ref;
- v->dist = -1;
- v->p = NULL;
- v->adj = NULL;
- return v;
+ // Get some space TODO check for null
+ vertex_t *v = malloc(sizeof(vertex_t));
+
+ // Set values
+ v->ref = ref;
+ v->dist = -1;
+ v->p = NULL;
+ 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;
+ 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
-
- // Chose starting index 0 if NULL e
- unsigned char i = e ? e->from->ref+1 : 0;
- for ( ; i < 128; i++ ) {
- if ( g->vertexes[i] && g->vertexes[i]->adj ) {
- return g->vertexes[i]->adj;
- }
- }
- // No next vertex
- return NULL;
- }
-
- // Not finished with this adj list
- return e->next;
+ if (e == NULL || e->next == NULL) {
+ // Find next index
+
+ // Chose starting index 0 if NULL e
+ unsigned char i = e ? e->from->ref + 1 : 0;
+ for (; i < 128; i++) {
+ if (g->vertexes[i] && g->vertexes[i]->adj) {
+ return g->vertexes[i]->adj;
+ }
+ }
+ // No next vertex
+ return NULL;
+ }
+
+ // Not finished with this adj list
+ return e->next;
}
vertex_t *vertex_next(graph_t *g, vertex_t *v)
{
- unsigned char ref = v ? v->ref+1 : 0;
- for ( ; ref < 128; ref++ ) {
- if ( g->vertexes[ref] ) {
- return g->vertexes[ref];
- }
- }
-
- return NULL;
+ unsigned char ref = v ? v->ref + 1 : 0;
+ for (; ref < 128; ref++) {
+ if (g->vertexes[ref]) {
+ return g->vertexes[ref];
+ }
+ }
+
+ return NULL;
}
void graph_edge(graph_t *g, char from, char to, int weight)
{
- // Does a exists
- if ( g->vertexes[from] == NULL ) {
- g->vertexes[from] = create_vertex(from);
- }
- // What about b
- if ( g->vertexes[to] == NULL ) {
- g->vertexes[to] = create_vertex(to);
- }
-
- // Add edge
- create_edge(g->vertexes[from], g->vertexes[to], weight);
+ // Does a exists
+ if (g->vertexes[from] == NULL) {
+ g->vertexes[from] = create_vertex(from);
+ }
+ // What about b
+ if (g->vertexes[to] == NULL) {
+ g->vertexes[to] = create_vertex(to);
+ }
+
+ // Add edge
+ create_edge(g->vertexes[from], g->vertexes[to], weight);
}
int graph_print_adj(graph_t *g, char ref)
{
- if ( g->vertexes[ref] == NULL ) {
- return 1;
- }
-
- edge_t *e = g->vertexes[ref]->adj;
- printf("[ ");
- while (e && e->from->ref == ref) {
- printf("%c[%d] ", e->to->ref, e->weight);
- e = e->next;
- }
- printf("]\n");
-
- return 0;
+ if (g->vertexes[ref] == NULL) {
+ return 1;
+ }
+
+ edge_t *e = g->vertexes[ref]->adj;
+ printf("[ ");
+ while (e && e->from->ref == ref) {
+ printf("%c[%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, "%c [label=\"%c(%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, "%c -> %c [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");
+ // print pre stuff
+ fprintf(f, "digraph coolgraph {\n");
+
+ // Label all nodes
+ vertex_t *v = vertex_next(g, NULL);
+ while (v) {
+ fprintf(f, "%c [label=\"%c(%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, "%c -> %c [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");
}
-
diff --git a/sem3/algo/mm12/graph.h b/sem3/algo/mm12/graph.h
index e957c4d..f4f2c8f 100644
--- a/sem3/algo/mm12/graph.h
+++ b/sem3/algo/mm12/graph.h
@@ -5,23 +5,23 @@ 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;
+ 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 dist;
- struct vertex_struct *p;
- edge_t *adj;
+ char ref;
+ int dist;
+ struct vertex_struct *p;
+ edge_t *adj;
} vertex_t;
typedef struct {
- vertex_t *vertexes[128];
+ vertex_t *vertexes[128];
} graph_t;
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-27 08:43:26 +0000