graph.java

graph.java

contents ::

  app.java
  graph.java
  node.java
  queue.java

/*
struct graphrec {
  int size;
  int **edges;
  struct v *vertices;
};
*/
class graph {
    int size;
    int [][] edges;
    node [] vertices;
    int time;
    final int BI = 0;
    final int ONE = 1;
    final int WHITE = 0;
    final int GREY = 1;
    final int BLACK = 2;

    graph(int size){
         int i,j;
         this.size = size;
         edges = new int[size][size];
         vertices = new node[size];

         for(i = 0; i<size; i++){
             vertices[i] = new node();
             vertices[i].pred = -1;
             vertices[i].dist = -1;
             vertices[i].color = WHITE;
             vertices[i].fin = 0;
         }

         for(i = 0; i<size; i++){
             for(j = 0; j<size; j++){
                  edges[i][j] = 0;   /* better initialise these puppies to 0 */
             }
         }
    }

    void graph_add_edge(int u, int v, int dir){
         if(dir == BI){
             edges[u][v] = 1;
             edges[v][u] = 1;
         } else
             edges[u][v] = 1;
    }

    void graph_print(){
         int i, j;
         for(i = 0; i<size; i++){
             for(j = 0; j<size; j++){
                  System.out.print(edges[i][j]+" ");
             }
                 System.out.print("\n");
         }
         System.out.print("\n");
    }

    /* for a vertex v, d[v] refers to the distance field,
       pi[v] refers to the predecessor field
    */
    void graph_breadth_first(int s){
         int u,v,j;
         queue q;


         for(u=0; u<size; u++){
             vertices[u].color = WHITE;
             vertices[u].dist = -1;
             vertices[u].pred = -1;
         }

         vertices[s].color = GREY;
         vertices[s].dist = 0;
         vertices[s].pred = -1;

         q = new queue(6);
         q.queue_enqueue(s);

         //while(!q.queue_empty()){
         for(j=0; j<size; j++){
             u = q.queue_dequeue();
             for(v=0; v<size; v++){
                  if(edges[u][v] == 1){
                      if(vertices[v].color == WHITE){
                           vertices[v].color = GREY;
                           vertices[v].dist = vertices[u].dist + 1;
                           vertices[v].pred = u;
                           q.queue_enqueue(v);
                      }
                  }
             }
             vertices[u].color = BLACK;
         }
    }


    void graph_depth_first_visit(int u){
         int v;
         vertices[u].color = GREY;
         vertices[u].dist = ++time;

         for(v=0; v<size; v++){
             if(edges[u][v] == 1){
                  if(vertices[v].color == WHITE){
                      vertices[v].pred = u;
                      graph_depth_first_visit(v);
                  }
             }
         }
         vertices[u].color = BLACK;
         vertices[u].fin =  ++time;
    }

    /* depth first search */
    void graph_depth_first(){
         int u;
         /* for each vertex u in G */
         for(u=0; u<size; u++){
             vertices[u].color = WHITE;
             vertices[u].pred = -1;
         }
         time = 0;

         for(u=0; u<size; u++){
             if(vertices[u].color == WHITE)
                  graph_depth_first_visit(u);
         }

    }

    void graph_print_stuff(){
         int i;
         for(i=0; i<size; i++){
             String stuff = (vertices[i].color == WHITE)?"white\n":
                  (vertices[i].color==GREY)?"grey\n": "black\n";
             System.out.print("node "+i+"\n");
             System.out.print("node color: "+stuff);
             System.out.print("node distance: "+vertices[i].dist+"\n");
             System.out.print("node predecessor: "+vertices[i].pred+"\n");
             System.out.print("node finish: "+vertices[i].fin+"\n\n");
         }
    }
}

James Little