graph.c |
| #include <stdio.h> #include <stdlib.h> #include "graph.h" #include "mylib.h" #include "queue.h" struct linkrec { int key; list next; }; typedef struct v { int pred; int dist; color_t color; int fin; } node; struct graphrec { int size; int **edges; int **transpose_edges; node *vertices; list l; }; static int time; graph graph_new(int size){ int i,j; graph g = emalloc(sizeof *g); g->l = emalloc(sizeof *g->l); g->l->next = NULL; g->size = size; g->edges = emalloc(size * sizeof g->edges[0]); g->transpose_edges = emalloc(size * sizeof g->transpose_edges[0]); g->vertices = emalloc(size * sizeof g->vertices[0]); g->size = size; time = 0; for(i = 0; i<size; i++){ g->edges[i] = emalloc(size * sizeof g->edges[0][0]); g->transpose_edges[i] = emalloc(size * sizeof g->transpose_edges[0][0]); g->vertices[i].pred = -1; g->vertices[i].dist = -1; g->vertices[i].color = WHITE; g->vertices[i].fin = 0; } for(i = 0; i<size; i++){ for(j = 0; j<size; j++){ g->edges[i][j] = 0; /* better initialise these puppies to 0 */ } } return g; } static list list_new(int k, list next){ list l = emalloc(sizeof *l); l->key = k; l->next = next; return l; } void graph_add_edge(graph g, int u, int v, dir_t dir){ if(dir == BI){ g->edges[u][v] = 1; g->edges[v][u] = 1; } else g->edges[u][v] = 1; } void graph_print(graph g){ int i, j; for(i = 0; i<g->size; i++){ for(j = 0; j<g->size; j++){ printf("%d ",g->edges[i][j]); } printf("\n"); } printf("\n"); } void graph_transpose(graph g){ int i, j; for(i = 0; i<g->size; i++){ for(j = 0; j<g->size; j++){ g->transpose_edges[j][i]= g->edges[i][j]; } } } /* for a vertex v, d[v] refers to the distance field, pi[v] refers to the predecessor field */ void graph_breadth_first(graph g, int s){ int u,v; queue q; for(u=0; u<g->size; u++){ g->vertices[u].color = WHITE; g->vertices[u].dist = -1; g->vertices[u].pred = -1; } g->vertices[s].color = GREY; g->vertices[s].dist = 0; g->vertices[s].pred = -1; q = queue_new(6); queue_enqueue(q, s); while(queue_size(q)){ u = queue_dequeue(q); for(v=0; v<g->size; v++){ if(g->edges[u][v]){ if(g->vertices[v].color == WHITE){ g->vertices[v].color = GREY; g->vertices[v].dist = g->vertices[u].dist + 1; g->vertices[v].pred = u; queue_enqueue(q, v); } } } g->vertices[u].color = BLACK; } } void graph_depth_first_visit(graph g, int u){ int v; g->vertices[u].color = GREY; g->vertices[u].dist = ++time; for(v=0; v<g->size; v++){ if(g->edges[u][v]){ if(g->vertices[v].color == WHITE){ g->vertices[v].pred = u; graph_depth_first_visit(g, v); } } } g->vertices[u].color = BLACK; g->vertices[u].fin = ++time; g->l =list_new(u, g->l); } void graph_print_node(graph g, int i){ printf("print node function\n"); printf("node %d\n",i); printf("node color: %s\n", (g->vertices[i].color == WHITE)?"white": (g->vertices[i].color==GREY)?"grey": "black"); printf("node distance: %d\n", g->vertices[i].dist); printf("node predecessor: %d\n", g->vertices[i].pred); printf("node finish: %d\n%s\n", g->vertices[i].fin, "**************************"); } void graph_transpose_depth_first_visit(graph g, int u, int *i){ int v; g->vertices[u].color = GREY; g->vertices[u].dist = ++time; for(v=0; v<g->size; v++){ if(g->transpose_edges[u][v]){ if(g->vertices[v].color == WHITE){ g->vertices[v].pred = u; graph_transpose_depth_first_visit(g, v, i); } } } g->vertices[u].color = BLACK; g->vertices[u].fin = ++time; (*i)++; graph_print_node(g, u); } /* depth first search */ void graph_depth_first(graph g){ int u; /* for each vertex u in G */ for(u=0; u<g->size;u++){ g->vertices[u].color = WHITE; g->vertices[u].pred = -1; } time = 0; for(u=0; u<g->size; u++){ if(g->vertices[u].color == WHITE) graph_depth_first_visit(g, u); } } void graph_strongly(graph g){ int u; list ln; graph_depth_first(g); graph_transpose(g); /* for each vertex u in G */ for(u=0; u<g->size; u++){ g->vertices[u].color = WHITE; g->vertices[u].pred = -1; } time = 0; ln = g->l; for(u=0; u<g->size; ){ graph_transpose_depth_first_visit(g, ln->key, &u); if(ln->next == NULL){ break; } ln = ln->next; } /* if(g->vertices[u].color == WHITE) graph_depth_first_visit(g, u); }*/ } void graph_shortest_path(graph g, int u, int v){ int i; graph_breadth_first(g,u); printf("Print shortest path from %d to %d\n", u, v); for(i = v; i!=-1; ){ printf("vertex: %d\n",i); i = g->vertices[i].pred; } } void graph_print_stuff(graph g){ int i; for(i=0; i<g->size; i++){ printf("node %d\n",i); printf("node color: %s\n", (g->vertices[i].color == WHITE)?"white": (g->vertices[i].color==GREY)?"grey": "black"); printf("node distance: %d\n", g->vertices[i].dist); printf("node predecessor: %d\n", g->vertices[i].pred); printf("node finish: %d\n%s\n", g->vertices[i].fin, "**************************"); } } |
James Little |