// graph.c: set up data structure for graph
// Uses adjacency list representation
#include <stdio.h>
#include <stdlib.h>
#define GRAPHSIZE 48

struct graphnode {
   struct edgenode* firstedgenode;
   // other vertex info here
};

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

void printgraph(struct graphnode* graph[], int count);
struct graphnode* newgraphnode();
struct edgenode* newedgenode(int num, struct edgenode* node, int dist);
void insert(struct graphnode* graph[], int num1, int num2, int dist);
int edgedistance(struct graphnode* graph[], int v1, int v2);
int pathlength(struct graphnode* graph[], int path[], int len);

int main() {
   // three Hamiltonian paths
   int ham1[] =
       {47,45,42,44,46,43,41,40,39,37,33,38,
        34,28,29,24,21,16,10,15,20,23,27,32,
        26,36,35,31,30,25,22,18,17,11, 7,12,
         8,13,19,14, 9, 5, 4, 0, 2, 1, 6, 3};
   int ham2[] =
       {47,45,42,44,46,43,41,40,38,39,37,32,
        36,35,31,30,25,22,17,11,12,18,26,27,
        33,34,29,28,23,19,13,14,20,24,21,15,
        16,10, 6, 5, 9, 8, 7, 4, 1, 0, 2, 3};
   int ham3[] =
       {47,45,42,44,46,43,41,40,39,37,33,32,
        36,35,31,30,25,26,27,28,23,20,19,18,
        22,17,11,12,13,14,15, 9, 8, 7, 4, 5,
         1, 0, 2, 3, 6,10,16,21,24,29,34,38};

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

   FILE *infile;
   infile = fopen("capsdist.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);
   printf("Path length: %i\n", pathlength(graph, ham2, 48));

}

struct graphnode* newgraphnode(){
   struct graphnode* nnode = malloc(sizeof(struct graphnode));
   nnode -> firstedgenode = NULL;
   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){
   if (graph[num1] -> firstedgenode == NULL) {
      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 < count; 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");
      }
   }
}

int edgedistance(struct graphnode* graph[], int v1, int v2) {
   if (v1 < 0 || v1 > GRAPHSIZE-1) return -1;
   if (graph[v1] == NULL) return -1;
   struct edgenode* node = graph[v1] -> firstedgenode;
   while (node != NULL) {
      if (node -> vertexnum == v2) return node -> edgedist;
      node = node -> nextedgenode;
   }
   return -1;
}

int pathlength(struct graphnode* graph[], int path[], int len) {
   int dist = 0, i;
   for (i = 0; i < len-1; i++) {
      int temp = edgedistance(graph, path[i], path[i+1]);
      if (temp == -1) return -1;
      dist += temp;
   }
   return dist;
}