aboutsummaryrefslogtreecommitdiff
path: root/sem3/algo/workshop2/dijkstra/graph.c
diff options
context:
space:
mode:
Diffstat (limited to 'sem3/algo/workshop2/dijkstra/graph.c')
-rw-r--r--sem3/algo/workshop2/dijkstra/graph.c340
1 files changed, 171 insertions, 169 deletions
diff --git a/sem3/algo/workshop2/dijkstra/graph.c b/sem3/algo/workshop2/dijkstra/graph.c
index 51206c4..4f2e88f 100644
--- a/sem3/algo/workshop2/dijkstra/graph.c
+++ b/sem3/algo/workshop2/dijkstra/graph.c
@@ -8,224 +8,226 @@
// 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;
+ 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);
+ unsigned int index = hash(var);
- // Save old value
- vertex_t *oldSym = g->hashtable[index];
+ // Save old value
+ vertex_t *oldSym = g->hashtable[index];
- // Make new
- g->hashtable[index] = v;
+ // Make new
+ g->hashtable[index] = v;
- // Link old one
- g->hashtable[index]->next = oldSym;
+ // 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];
+ 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;
- }
+ // Look trough list
+ while (n != NULL && strcmp(n->ref, var) != 0) {
+ n = n->next;
+ }
- return n;
+ 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;
+ // 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;
+ 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;
+ 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;
+ 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);
+ 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;
+ 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");
+ // 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;
- int count = 0;
- // 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);
- count++;
- }
-
- return count;
+ char from[100], to[100];
+ int weight;
+ int count = 0;
+ // 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);
+ count++;
+ }
+
+ return count;
}
vertex_t *graph_vertex(graph_t *g, char *ref)
{
- return table_lookup(g, ref);
+ return table_lookup(g, ref);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-26 18:49:25 +0000