graph.c

graph.c

contents ::

  app.c
  graph.c
  graph.h
  mylib.c
  mylib.h
  queue.c
  queue.h

#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