#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
#define GRAPHSIZE 48

struct graphnode {
   struct edgenode* firstedgenode;
   // other vertex info here
   int color; // 0, 1, 2 = white, gray, black
   int d; // shortest dist to node in edges
   int pi; // predessesor
};

struct edgenode {
   int vertexnum;
   int edgedist;
   struct edgenode* nextedgenode;
   // other edge info here
};

void printgraph(struct graphnode* graph[], int);
struct graphnode* newgraphnode();
struct edgenode* newedgenode(int , struct edgenode* , int );
void breadthsearch(struct graphnode* graph[], int );

void insert(struct graphnode* [], int, int, int);

int main() {
   struct graphnode* graph[GRAPHSIZE];
   int i;
   int num1, num2, num;
   for(i = 0; i < GRAPHSIZE; i++) graph[i] = NULL;

   FILE *infile;
   infile = fopen("capsdistnum.txt", "r");
   if (infile == NULL) {
      fprintf(stderr, "Can't open %s\n", "source.txt");
      exit(1);
   }
   while (fscanf(infile, "%i %i %i",
            &num1, &num2, &num) != EOF) {
      insert(graph, num1, num2, num);
      insert(graph, num2, num1, num);
   }
   // printgraph(graph, GRAPHSIZE);
   breadthsearch(graph, 3); // WA
}

struct graphnode* newgraphnode(){
   struct graphnode* nnode = malloc(sizeof(struct graphnode));
   nnode -> firstedgenode = NULL;
   nnode -> color = 0; // white
   nnode -> d = 100000000;
   nnode -> pi = -1;
   return nnode;
}

struct edgenode* newedgenode(int num, struct edgenode* node,
      int dist) {
   struct edgenode* nnode = malloc(sizeof(struct edgenode));
   nnode -> vertexnum = num;
   nnode -> nextedgenode = node;
   nnode -> edgedist = dist;
   return nnode;
}
  
void insert(struct graphnode* graph[], int num1, int num2,
      int dist){
   struct graphnode* node = graph[num1];
   if (node == NULL) {
      struct graphnode* gnode = newgraphnode();
      graph[num1] = gnode;
      struct edgenode* enode = newedgenode(num2, NULL, dist);
      graph[num1] -> firstedgenode = enode;
   }
   else {
      struct edgenode* enode = newedgenode(num2,
         graph[num1] -> firstedgenode, dist);
      graph[num1] -> firstedgenode = enode;
   }
}
      
void printgraph(struct graphnode* graph[], int count) {
   int i;
   for (i = 0; i < GRAPHSIZE; i++) {
      printf("%2i: ", i);
      struct edgenode* node = graph[i] -> firstedgenode;
      while (node != NULL) {
          printf("[%2i,%3i]", node -> vertexnum,
             node -> edgedist);
          node = node -> nextedgenode;
          if (node != NULL) printf(",");
          else printf("\n");
      }
   }
}

void breadthsearch(struct graphnode* graph[], int s) {
   int u, v; // vertices used in loop
   graph[s] -> color = 1; // gray
   graph[s] -> d = 0;
   graph[s] -> pi = -1;
   enqueue(s);
   while (!isempty()) {
      u = dequeue();
      struct edgenode* vnode = graph[u] -> firstedgenode;
      v = vnode -> vertexnum;
      while(1) {
         if (graph[v] -> color == 0) {  // white
            graph[v] -> color = 1; // gray
            graph[v] -> d = graph[u] -> d + 1;
            graph[v] -> pi = u;
            enqueue(v);
         }
         vnode = vnode -> nextedgenode;
         if (vnode == NULL) break;
         else v = vnode -> vertexnum;
      }
      graph[u] -> color = 2; // black
   }
   int i;
   for (i = 0; i < GRAPHSIZE; i++) {
      if (i < 10) printf(" ");
      printf("%i: color:%i, d:%i, pi:%i\tEdge: (%i,%i)\n",
         i, graph[i] -> color, graph[i] -> d,
         graph[i] -> pi, graph[i] -> pi, i);
   }
}

// queue.h: header file
int dequeue();
void enqueue(int );
int isempty();
int isfull();
int getfront();
void dumpq();
// queue.c: queue definition
#include <stdio.h>
#include "queue.h"
#define QSIZE 100

int q[QSIZE];
int head = 0;
int tail = 0;
int size = 0;

void enqueue(int x) {
   if (!isfull()) {
      size++;
      q[tail] = x;
      if (tail == QSIZE - 1) tail = 0;
      else tail++;
   }
   else printf("Overflow\n");
}
   
int dequeue() {
   int x;
   if (isempty()) {
      printf("Underflow\n");
      return -1;
   }
   size--;
   x = q[head];
   if (head == QSIZE - 1) head = 0;
   else head++;
   return x;
}
   
int isempty() {
   return size == 0;
}

int isfull() {
   return size == QSIZE;
}

int getfront() {
   if (!isempty())
      return q[head];
   else return -1;
}

void dumpq(int n) {
   printf("n:%i, size:%i, head:%i,\
      tail:%i, frontitem:%i\n", 
      n, size, head, tail, getfront());
}

 0: color:2, d:2, pi:2  Edge: (2,0)
 1: color:2, d:2, pi:6  Edge: (6,1)
 2: color:2, d:1, pi:3  Edge: (3,2)
 3: color:2, d:0, pi:-1 Edge: (-1,3)
 4: color:2, d:3, pi:5  Edge: (5,4)
 5: color:2, d:2, pi:6  Edge: (6,5)
 6: color:2, d:1, pi:3  Edge: (3,6)
 7: color:2, d:4, pi:8  Edge: (8,7)
 8: color:2, d:3, pi:9  Edge: (9,8)
 9: color:2, d:2, pi:6  Edge: (6,9)
10: color:2, d:2, pi:6  Edge: (6,10)
11: color:2, d:5, pi:12 Edge: (12,11)
12: color:2, d:4, pi:8  Edge: (8,12)
13: color:2, d:4, pi:14 Edge: (14,13)
14: color:2, d:3, pi:9  Edge: (9,14)
15: color:2, d:3, pi:10 Edge: (10,15)
16: color:2, d:3, pi:10 Edge: (10,16)
17: color:2, d:6, pi:18 Edge: (18,17)
18: color:2, d:5, pi:19 Edge: (19,18)
19: color:2, d:4, pi:14 Edge: (14,19)
20: color:2, d:4, pi:15 Edge: (15,20)
21: color:2, d:4, pi:16 Edge: (16,21)
22: color:2, d:6, pi:26 Edge: (26,22)
23: color:2, d:5, pi:20 Edge: (20,23)

24: color:2, d:5, pi:21 Edge: (21,24)
25: color:2, d:6, pi:26 Edge: (26,25)
26: color:2, d:5, pi:19 Edge: (19,26)
27: color:2, d:5, pi:19 Edge: (19,27)
28: color:2, d:6, pi:23 Edge: (23,28)
29: color:2, d:6, pi:24 Edge: (24,29)
30: color:2, d:7, pi:31 Edge: (31,30)
31: color:2, d:6, pi:26 Edge: (26,31)
32: color:2, d:6, pi:27 Edge: (27,32)
33: color:2, d:6, pi:27 Edge: (27,33)
34: color:2, d:6, pi:27 Edge: (27,34)
35: color:2, d:7, pi:36 Edge: (36,35)
36: color:2, d:6, pi:26 Edge: (26,36)
37: color:2, d:7, pi:33 Edge: (33,37)
38: color:2, d:7, pi:34 Edge: (34,38)
39: color:2, d:8, pi:38 Edge: (38,39)
40: color:2, d:8, pi:38 Edge: (38,40)
41: color:2, d:8, pi:38 Edge: (38,41)
42: color:2, d:9, pi:41 Edge: (41,42)
43: color:2, d:9, pi:41 Edge: (41,43)
44: color:2, d:9, pi:41 Edge: (41,44)
45: color:2, d:10,pi:42 Edge: (42,45)
46: color:2, d:10,pi:44 Edge: (44,46)
47: color:2, d:11,pi:45 Edge: (45,47)